MATH 470 Lecture 27

From Notes
Jump to navigation Jump to search

« previous | Thursday, April 25, 2013 | next »

End Exam 2 content


From the Practice Final

Prime Fields

Find 1t, 1t+1, 1t2 in 𝔽73=𝔽343 realized as 𝔽7[t]/⟨t3+t+1⟩

First Way

Tricks: While you can use Extended Euclidean Algorithm, you can do some faster trickery:

Key: t3+t+1=0, therefore t2+1+1t=0 and 1t=−1−t2=6+6t2.

What if we can do the same thing with 1t+1?

t3+t+1=0t+1=−t31t+1=−1t3=−1t(1t2)=−(6+6t2)(1t2)=(1+t2)(1t2)=1t2+1=(1t)2+1=(−1−t2)2+1=(1+2t2+t4)+1=(1+2t2+(−t−t2))+1=(1+6t+t2)+1=2+6t+t2

Second Way

Easier way to figure out 1t2:

t3+t+1=0t+1t+1t2=01t2=−1t−t=1+t2−t=1+6t+t2

Third Way

Third way to find 1t2 (Extended Euclidean Algorithm):

Look for polynomials p,q∈𝔽7[t] with p(t)t2+q(t)(t3+t+1)=1

[1001t2t3+t+1]→[1−t01t2t+1]→[1+t2−t−t1−tt+1]→[1+t21−t+t2−t1−t−t1]

Therefore (1−t+t2)t2+(1−t)(t3+t+1)=1 and our inverse 1t2=1+6t+t2

Note: EEA is the safer method for more complicated inverses, e.g. 13−t+2t2


Elliptic Curve Cryptography

Suppose you would like to transmit "21" in an elliptic curve cipher via the elliptic curve E:y2=x3+7x+15/𝔽593. In particular, you will transmit the point. (note: 593 is prime)

We want to find a point (210+a,y)∈E, where a∈{0,…,9}.

Which a would work?

Nothing more than a Jacobi square-root question in disguise!

a 210+a (210+a)3+7(210+a)+15 (◻593)
0 210 228 -1
1 211 432 -1
2 212 123 1
3 213 493
… … … …

So a=2 works

Elliptic Curves

(Not on practice final... yet)

Suppose you are trying to compute

[12,252,240](2,1) on y2=x3+254x−515(modn) with n=1,713,761,513

In particular, you observe

12,252,240=24+26+…+220+221+233

and

[24+26+…+221(2,1)⊕[223](2,1)=(390104967,128395638)⊕(520835552,974225979)

Suppose the last addition is undefined mod n. Find a non-trivial factor of n.

...what? (Sherlock Holmes moment where an addition is undefined and therefore we find a non-trivial factor)

If the addition is undefined, we must have 520835552−390104967 is non-invertible mod n.

In other words, gcd(520835552−390104967,n)>1, so one of the factors of the difference is a factor of n, namely 26927 (or 63719)