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 {F} _{7^{3}}=\mathbb {F} _{343}$ realized as $\mathbb {F} _{7}\left[t\right]/\left\langle t^{3}+t+1\right\rangle$

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{aligned}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)\\&=-\left(6+6t^{2}\right)\,\left({\frac {1}{t^{2}}}\right)\\&=\left(1+t^{2}\right)\,\left({\frac {1}{t^{2}}}\right)\\&={\frac {1}{t^{2}}}+1\\&=\left({\frac {1}{t}}\right)^{2}+1\\&=\left(-1-t^{2}\right)^{2}+1\\&=\left(1+2t^{2}+t^{4}\right)+1\\&=\left(1+2t^{2}+\left(-t-t^{2}\right)\right)+1\\&=\left(1+6t+t^{2}\right)+1\\&=2+6t+t^{2}\end{aligned}}$

Second Way

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

${\begin{aligned}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{aligned}}$

Third Way

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

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

${\begin{bmatrix}1&0\\0&1\\t^{2}&t^{3}+t+1\end{bmatrix}}\rightarrow {\begin{bmatrix}1&-t\\0&1\\t^{2}&t+1\end{bmatrix}}\rightarrow {\begin{bmatrix}1+t^{2}&-t\\-t&1\\-t&t+1\end{bmatrix}}\rightarrow {\begin{bmatrix}1+t^{2}&1-t+t^{2}\\-t&1-t\\-t&1\end{bmatrix}}$

Therefore $\left(1-t+t^{2}\right)\,t^{2}+\left(1-t\right)\,\left(t^{3}+t+1\right)=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 {F} _{593}$ . In particular, you will transmit the point. (note: 593 is prime)