MATH 470 Lecture 27

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

End Exam 2 content

From the Practice Final

Prime Fields

Find $\frac{1}{t}$, $\frac{1}{t+1}$, $\frac{1}{t^2}$ in ${\mathbb{𝔽}}_{7^3}={\mathbb{𝔽}}_{343}$ realized as ${\mathbb{𝔽}}_7\left[t\right]/⟨t^3+t+1⟩$

First Way

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

Key: $t^3+t+1=0$, therefore $t^2+1+\frac{1}{t}=0$ and $\frac{1}{t}=-1-t^2=6+6t^2$.

What if we can do the same thing with $\frac{1}{t+1}$?

$\begin{array}{rl}{t}^3+t+1& =0\\ t+1& =-t^3\\ \frac{1}{t+1}& =-\frac{1}{t^3}\\ & =-\frac{1}{t}\left(\frac{1}{t^2}\right)\\ & =-(6+6t^2)\left(\frac{1}{t^2}\right)\\ & =(1+t^2)\left(\frac{1}{t^2}\right)\\ & =\frac{1}{t^2}+1\\ & ={\left(\frac{1}{t}\right)}^2+1\\ & ={(-1-t^2)}^2+1\\ & =(1+2t^2+t^4)+1\\ & =(1+2t^2+(-t-t^2))+1\\ & =(1+6t+t^2)+1\\ & =2+6t+t^2\end{array}$

Second Way

Easier way to figure out $\frac{1}{t^2}$:

$\begin{array}{rl}{t}^3+t+1& =0\\ t+\frac{1}{t}+\frac{1}{t^2}& =0\\ \frac{1}{t^2}& =-\frac{1}{t}-t\\ & =1+t^2-t\\ & =1+6t+t^2\end{array}$

Third Way

Third way to find $\frac{1}{t^2}$ (Extended Euclidean Algorithm):

Look for polynomials $p,q\in {\mathbb{𝔽}}_7\left[t\right]$ with $p(t)t^2+q(t)(t^3+t+1)=1$

$\left[\begin{array}{cc}1& 0\\ 0& 1\\ t^2& t^3+t+1\end{array}\right]\to \left[\begin{array}{cc}1& -t\\ 0& 1\\ t^2& t+1\end{array}\right]\to \left[\begin{array}{cc}1+t^2& -t\\ -t& 1\\ -t& t+1\end{array}\right]\to \left[\begin{array}{cc}1+t^2& 1-t+t^2\\ -t& 1-t\\ -t& 1\end{array}\right]$

Therefore $(1-t+t^2)t^2+(1-t)(t^3+t+1)=1$ and our inverse $\frac{1}{t^2}=1+6t+t^2$

Note: EEA is the safer method for more complicated inverses, e.g. $\frac{1}{3-t+2t^2}$

Elliptic Curve Cryptography

Suppose you would like to transmit "21" in an elliptic curve cipher via the elliptic curve $E:y^2=x^3+7x+15/{\mathbb{𝔽}}_{593}$. In particular, you will transmit the point. (note: 593 is prime)

We want to find a point $(210+a,y)\in E$, where $a\in \{0,\dots ,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$	$\left(\frac{◻}{593}\right)$
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 $y^2=x^3+254x-515(\mathrm{mod}n)$ with $n=1,713,761,513$

In particular, you observe

$12,252,240=2^4+2^6+\dots +2^{20}+2^{21}+2^{33}$

and

$[2^4+2^6+\dots +2^{21}(2,1)\oplus [2^{23}](2,1)=(390104967,128395638)\oplus (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, $\mathrm{g}\mathrm{c}\mathrm{d}(520835552-390104967,n)>1$, so one of the factors of the difference is a factor of $n$, namely 26927 (or 63719)