MATH 470 Lecture 27

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

End Exam 2 content

From the Practice Final

Prime Fields

Find 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 \frac{1}{t}} , 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 \frac{1}{t+1}} , 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 \frac{1}{t^2}} in 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 \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 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 t^2 + 1 + \frac{1}{t} = 0} 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 \frac{1}{t} = -1 - t^2 = 6+6t^2} .

What if we can do the same thing with 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 \frac{1}{t+1}} ?

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

Second Way

Easier way to figure out 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 \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 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 \frac{1}{t^2}} (Extended Euclidean Algorithm):

Look for polynomials 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 p,q \in \mathbb{F}_7\left[ t \right]} with 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 p(t) \, t^2 + q(t) \, \left( t^3 + t + 1 \right) = 1}

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 \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 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 \frac{1}{t^2} = 1 + 6t + t^2}

Note: EEA is the safer method for more complicated inverses, e.g. 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 \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 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 (210 + a, y) \in E} , where 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 a \in \left\{ 0, \ldots, 9 \right\}} .

Which 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 a} would work?

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

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

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 [12,252,240](2,1)} on 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 y^2 = x^3 + 254x-515 \pmod{n}} with 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 = 1,713,761,513}

In particular, you observe

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 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 $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)