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

Given:〈Ax,w) =〈x,Aw〉 ⇐ Self-Adjoint

Aw∈W ⇐ W is A-invariant

then〈x∈W⊥, Aw∈W〉= 0

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


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.


HTML is really not suited for doing math.

Appendix A

If λ1≠λ2,〈v1,v2〉must be 0

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

Given that: λ1〈v1,v2〉 = 〈λ1v1,v2〉= 〈Av1,v2〉= 〈v1,Av2〉= 〈v1,λ2v2〉=λ2〈v1,v2〉⇒ λ1〈v1,v2〉= λ2〈v1,v2〉

Since λ1≠λ2, 〈v1,v2〉=0



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”.


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
stany@Gilva:~[11:14 PM]$ 

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

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

ans =



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


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.