MATH 470 Lecture 25

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

Last Time

We worked with the field $\mathbb {F} _{9}$ realized as $\mathbb {F} _{3}\left[t\right]/\left\langle t^{2}+1\right\rangle$.

We also looked at $E:y^{2}=x^{3}+x+1$.

Note: $E$ is an elliptic curve because its discriminant is non-zero: $\Delta {=}4b^{3}+27c^{2}{=}31\equiv 1{\pmod {3}}$

Recall the addition law (for this elliptic curve)

${\begin{aligned}(x,y)\oplus (x',y')&=(\mathbb {X} ,\mathbb {Y} )\\\mathbb {X} &=m^{2}-x-x'\\\mathbb {Y} &=m(x-\mathbb {X} )-y\\m&={\begin{cases}{\frac {y'-y}{x'-x}}&(x,y)\neq (x',y')\\{\frac {3x^{2}+1}{2y}}&(x,y)=(x',y')\end{cases}}\end{aligned}}$

If $x=x'$ but $y\neq y'$, $(x,y)\oplus (x',y')$ is the point at infinity

Surprise Quiz

Compute the following:

1. $\left[2\right]\left(0,\pm 1\right)=\left(1,0\right)$
2. $\left[2\right]\left(2,\pm T\right)=\left(1,0\right)$
3. $\left[2\right]\left(T,\pm 1\right)=\left(1+T,0\right)$
4. $\left[2\right]\left(T+2,\pm T\right)=\left(1+T,0\right)$
5. $\left[2\right]\left(2T,\pm 1\right)=\left(1+2T,0\right)$
6. $\left[2\right]\left(2T+2,\pm T\right)=\left(1+2T,0\right)$

All of the RHS points have order 2 because if you add these points to themselves, you get the point at infinity.

All of the LHS points have order 4 because the RHS has order 2 ( $(p\oplus p)\oplus (p\oplus p)$ )

Lagrange's theorem states that the order must divide the number of points on the curve.

Factoring Using Groups

Suppose we want to factor $N=1,715,761,513$.

We can easily compute $2^{N-1}\equiv 93,082,891{\pmod {N}}$ and find that $N$ is composite.

Lenstra's Method

1. Pick a random point $p=(x,y)$, with small integer coordinates $x$ and $y$.
2. Pick a random $b$, then solve for $c$ with $p$ lying on $E:y^{2}=x^{3}+b\,x+c$
3. Pick a "moderate" $k$ and compute $\mathbb {K} =\mathrm {lcm} (1,2,3,\ldots ,k)$. For example, $k=17$ gives $\mathbb {K} =12252240$
4. Compute (if you can) $\left[\mathbb {K} \right]\,p{\pmod {N}}$
   • If this succeeds, you've "failed" (go back and pick new $b$ or new $k$.
   • If this fails, you will have found a non-trivial factor of $N$!

For example, let's choose $p=(1,2)$, $b=1$, which gives $c=-9$:

$y^{2}=x^{3}+x-9$

Choose $k=17$, so $\mathbb {K} =12252240=101110101111010001010000_{2}$

So now we have to compute $[12252240](1,2)$... use analogue of recursive squaring (hence binary expansion above) with only 24 doublings and 12 additions

it turns out that $[12252240](1,2)$ is well-defined, so it tells us nothing about the factorization of $N$.

• Retry with $b=2$, same well-defined result
• Retry with $b=3$, same well-defined result
• …
• Retry with $b=254$, something interesting happens:

$b=254$, $c=-515$: $y^{2}=x^{3}+254x-515$

What happens is in the addition formula, you wind up computing ${\frac {\text{large integer}}{2\cdot {\text{bottom integer}}}}{\pmod {n}}$, and it turns out that $\mathrm {gcd} ({\text{bottom}},N)$ is our factor:

$1,715,761,513=26,927\cdot 63,719$