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)

We want to find a point $(210+a,y)\in E$, where $a\in \left\{0,\ldots ,9\right\}$.

Which $a$ would work?

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

$a$	$210+a$	$\left(210+a\right)^{3}+7\left(210+a\right)+15$	$\left({\frac {\Box }{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{\pmod {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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [2^4+2^6+\ldots+2^{21}(2,1) \oplus [2^{23}](2,1) = (390104967,128395638) \oplus (520835552, 974225979)}

Suppose the last addition is undefined mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . Find a non-trivial factor of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 520835552-390104967} is non-invertible mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

In other words, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{gcd}(520835552-390104967, n) > 1} , so one of the factors of the difference is a factor of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , namely 26927 (or 63719)