Saturday, June 06, 2009

random curve with point

If you just need any short form weierstrass curve at random with a random point the easiest way is to create the point first, then the curve.
suitable for lenstra.
Given a composite you would like to factor.
toy example:
given N= 1289
random point P=(x,y)=(235,156)
random A= 21
calculate B as
B=y^2 -x^3 - A*x mod N
156^2-235^3-21*235 mod 1289 gives B=-157
then you got your random curve:
Y^2=X^3 + 21X-157 with a point P that by construction is on the curve.

the solution for B ofcourse can be plus/minus any multiplication of N. equivalence class: B + Z/ZN
More about lenstra later

No comments: