Content deleted Content added
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5) (Whoop whoop pull up - 15814 |
|||
Line 8:
==Algorithm==
The Lenstra elliptic-curve factorization method to find a factor of a given natural number <math>n</math> works as follows:
# Pick a random [[elliptic curve]] over <math>\mathbb{Z}/n\mathbb{Z}</math> (the integers modulo <math>n</math>, with equation of the form <math>y^2 = x^3 + ax + b \pmod n</math> together with a non-trivial [[Point (geometry)|point]] <math>P(x_0,y_0)</math> on it.
#:This can be done by first picking random <math>x_0,y_0,a \in \mathbb{Z}/n\mathbb{Z}</math>, and then setting <math>b = y_0^2 - x_0^3 - ax_0\pmod n</math> to assure the point is on the curve.
# One can define ''Addition'' of two points on the curve, to define a [[Group (mathematics)|group]]. The addition laws are given in the [[elliptic curve#The group law|article on elliptic curves]].
| |||