MATH 470 Lecture 25

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

Last Time

We worked with the field ${\mathbb{𝔽}}_9$ realized as ${\mathbb{𝔽}}_3\left[t\right]/⟨t^2+1⟩$.

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

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

Recall the addition law (for this elliptic curve)

$\begin{array}{rl}(x,y)\oplus (x^{\prime },y^{\prime })& =(\mathbb{𝕏},\mathbb{𝕐})\\ \mathbb{𝕏}& =m^2-x-x^{\prime }\\ \mathbb{𝕐}& =m(x-\mathbb{𝕏})-y\\ m& =\{\begin{array}{ll}\frac{y^{\prime }-y}{x^{\prime }-x}& (x,y)\ne (x^{\prime },y^{\prime })\\ \frac{3x^2+1}{2y}& (x,y)=(x^{\prime },y^{\prime })\end{array}\end{array}$

If $x=x^{\prime }$ but $y\ne y^{\prime }$, $(x,y)\oplus (x^{\prime },y^{\prime })$ is the point at infinity

Surprise Quiz

Compute the following:

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

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(\mathrm{mod}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+bx+c$
3. Pick a "moderate" $k$ and compute $\mathbb{𝕂}=\mathrm{l}\mathrm{c}\mathrm{m}(1,2,3,\dots ,k)$. For example, $k=17$ gives $\mathbb{𝕂}=12252240$
4. Compute (if you can) $\left[\mathbb{𝕂}\right]p(\mathrm{mod}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{𝕂}=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}}(\mathrm{mod}n)$, and it turns out that $\mathrm{g}\mathrm{c}\mathrm{d}(\text{bottom},N)$ is our factor:

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