MATH 470 Lecture 25

From Notes
Jump to navigation Jump to search

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


Last Time

We worked with the field 𝔽9 realized as 𝔽3[t]/⟨t2+1⟩.

We also looked at E:y2=x3+x+1.

Note: E is an elliptic curve because its discriminant is non-zero: Δ=4b3+27c2=31≡1(mod3)


Recall the addition law (for this elliptic curve)

(x,y)⊕(x′,y′)=(𝕏,𝕐)𝕏=m2−x−x′𝕐=m(x−𝕏)−ym={y′−yx′−x(x,y)≠(x′,y′)3x2+12y(x,y)=(x′,y′)

If x=x′ but y≠y′, (x,y)⊕(x′,y′) is the point at infinity

Surprise Quiz

Compute the following:

  1. [2](0,±1)=(1,0)
  2. [2](2,±T)=(1,0)
  3. [2](T,±1)=(1+T,0)
  4. [2](T+2,±T)=(1+T,0)
  5. [2](2T,±1)=(1+2T,0)
  6. [2](2T+2,±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⊕p)⊕(p⊕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 2N−1≡93,082,891(modN) 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:y2=x3+bx+c
  3. Pick a "moderate" k and compute 𝕂=lcm(1,2,3,…,k). For example, k=17 gives 𝕂=12252240
  4. Compute (if you can) [𝕂]p(modN)
    • 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:

y2=x3+x−9

Choose k=17, so 𝕂=12252240=1011101011110100010100002

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: y2=x3+254x−515

What happens is in the addition formula, you wind up computing large integer2⋅bottom integer(modn), and it turns out that gcd(bottom,N) is our factor:

1,715,761,513=26,927⋅63,719