## Elliptic Cryptography textbook

Looked some more at AACS specs. Realized that I don’t know jack about elliptic cryptography. Asked Yuly Billig what he recommends as a gentle introduction to elliptic cryptography for dummies with limited algebra skills.

He recommended “A Course in Number Theory and Cryptography” by N. Koblitz, QA 241.K672. Carleton library has two copies, so next time I am on campus, I shall sign one out. I guess we’ll find out how much of a dummy with limited algebra skills I am.

It’s all about copious spare time.

## Proof that any self-adjoint matrix is diagonalizable.

(Sorry. If you don’t know what this is, please ignore it. It’s not important. Really.)

Setup: If A is self-adjoint, and W is an A-invariant subspace â‡’ WâŠ¥ is A-invariant.

Want: âˆ€ xâˆˆWâŠ¥, Ax âˆˆ WâŠ¥âŒ©Ax,wâŒª = 0 âˆ€ w âˆˆ W â‡ Orthonormal

AwâˆˆW â‡ W is A-invariant

Since any self-adjoint matrix is ortho-diagonalizable, if A is self-adjoint, then âˆƒ an orthonormal basis Bâˆˆâ„‚n made out of eigenvectors such that [A]B

Want: k=n (that is, an orthonormal basis made out of eigenvectors).

Proof by contradiction: Suppose k less then n

Given:

W=span(v1, v2, .. vk), A-invariant (this is trivial, but see Appendix A)

then WâŠ¥ is A-invariant, then A is restricted to subspace WâŠ¥

AWâŠ¥: WâŠ¥ â†’ WâŠ¥

Then âˆƒ vâˆˆWâŠ¥, an eigenvector of AWâŠ¥.

But since AWâŠ¥v = Av, v is an eignevector to of A perpendicular to W.

We assumed that S is maximal, but we ended up with a contradiction, since the set {v1, v2, .. ,vk, v/ ||v||} is an orthogonal set of eigenvectors.

So k must be equal to n. As a result, A is orthodiagonalizable.

### Conclusion

HTML is really not suited for doing math.

Appendix A

Here is how: Av1=Î»1v1, Av2=Î»2v2

.

QED

## Show that if b âˆˆ R, R is a Eucledian domain and a is a non-zero non-unit, then bR/aR = {r + Ra : r âˆˆ bR} is an ideal in R/aR.

Suppose that R is a Euclidean domain and a âˆˆ R is a non-zero non-unit.

For an element b âˆˆ R consider the subset bR/aR = {r + Ra : r âˆˆ bR} of R/aR.

Let r + Ra, s + Ra âˆˆ bR/aR so that r, s âˆˆ bR, then r + s âˆˆ bR which gives (r + Ra) + (s + Ra) = (r + s) + Ra âˆˆ bR/aR.

Let r âˆˆ Ra âˆˆ R/aR and s + Ra âˆˆ bR/aR so that s âˆˆ bR, then rs âˆˆ bR implies that (r + Ra) Â· (s + Ra) = (rs) + Ra âˆˆ bR/aR.

Hence bR/aR is an ideal in R/aR

Just in case you weren’t sure that it was.

It’s almost 2 am, what do you expect?

Oh, and I goofed while writing a game theory midterm last week, and only got 92/100.

I forgot to do part II of question 1, inspite of the note on the test paper saying “Don’t forget to do part (ii) below”.

Argh!

Oh, and should I do a blurb on the math behind error correction, specifically, as it’s implemented on CDs?

## Floating Point numbers Part I

Here is an easy example to see if your mathematical software deals with floating point correctly.

You want to divide two thirds by five sixths. So you use GNU bc

```stany@Gilva:~[11:13 PM]\$ echo  "(2/3) / (5/6)" | bc -l
.79999999999999999999
stany@Gilva:~[11:14 PM]\$
```

Matlab, which is arguably better at math then bc is, gives me this:

```EDU>> (2/3) / (5/6)

ans =

0.8000

EDU>>
```

2*6 / 3*5 = 12/15 = 4/5 = 0.8 so Matlab is correct, and bc is wrong.

## JFLAP

Mental note: If for some really bizzare reason I might need to draw lines pointing at circles, or try to figure out if
S -> aSb|aS|Îµ actually matches L={a^ib^j| i>=j}, I will try to solve the problem by hand first. However, in event I am really lazy, and forgot how to convert an NFA to DFA or actually want to trace the stack of a PDA matching a CFG, I will download JFLAP and use it.

Now, why did I discover this thing after I wrote my final exam? So that I could learn how to do it by hand, that’s why. It would have rocked my world about 3 months ago, but I probably would have failed the exams, relaying on it to do everything for me.

Oh, and notation it uses for CFG/PDA is somewhat different from one used in Sipser (Which is a damn fine book, BTW. Unlike Lawson it actually covers CFLs.).

P.S Mark Lawson actually makes reasonably good notes available on his page about basic automata. It still doesn’t go into CFLs/PDAs.