Category: Mathematics

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.

(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∈ℂⁿ 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(v₁, v₂, .. v_k), A-invariant (this is trivial, but see Appendix A)

then W⊥ is A-invariant, then A is restricted to subspace W^⊥

A_W^⊥: W^⊥ → W^⊥

Then ∃ v∈W^⊥, an eigenvector of A_W^⊥.

But since A_W^⊥v = A_v, 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 {v₁, v₂, .. ,v_k, 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

If λ₁≠λ₂,〈v₁,v₂〉must be 0

Here is how: Av₁=λ₁v₁, Av₂=λ₂v₂

Given that: λ₁〈v₁,v₂〉 = 〈λ₁v₁,v₂〉= 〈Av₁,v₂〉= 〈v₁,Av₂〉= 〈v₁,λ₂v₂〉=λ₂〈v₁,v₂〉⇒ λ₁〈v₁,v₂〉= λ₂〈v₁,v₂〉

Since λ₁≠λ₂, 〈v₁,v₂〉=0

.

QED

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?