Incubator escapee wiki

Lenstra elliptic-curve factorization

Article Discussion
Revision as of 15:42, 1 May 2025 by imported>MrSwedishMeatballs (→‎Example usage)
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Template:Short description {{safesubst:#invoke:Unsubst||date=__DATE__|$B= Template:Ambox }}

The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra.

Practically speaking, ECM is considered a special-purpose factoring algorithm, as it is most suitable for finding small factors. Template:As of, it is still the best algorithm for divisors not exceeding 50 to 60 digits, as its running time is dominated by the size of the smallest factor p rather than by the size of the number n to be factored. Frequently, ECM is used to remove small factors from a very large integer with many factors; if the remaining integer is still composite, then it has only large factors and is factored using general-purpose techniques. The largest factor found using ECM so far has 83 decimal digits and was discovered on 7 September 2013 by R. Propper.<ref>50 largest factors found by ECM.</ref> Increasing the number of curves tested improves the chances of finding a factor, but they are not linear with the increase in the number of digits.

AlgorithmEdit

The Lenstra elliptic-curve factorization method to find a factor of a given natural number <math>n</math> works as follows:

  1. 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 <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.
  2. One can define Addition of two points on the curve, to define a group. The addition laws are given in the article on elliptic curves.
    We can form repeated multiples of a point <math>P</math>: <math>[k]P = P + \ldots + P \text{ (k times)}</math>. The addition formulae involve taking the modular slope of a chord joining <math>P</math> and <math>Q</math>, and thus division between residue classes modulo <math>n</math>, performed using the extended Euclidean algorithm. In particular, division by some <math>v \bmod n</math> includes calculation of the <math>\gcd(v,n)</math>.
    Assuming we calculate a slope of the form <math>u/v</math> with <math>\gcd(u,v)=1</math>, then if <math>v = 0 \bmod n</math>, the result of the point addition will be <math>\infty</math>, the point "at infinity" corresponding to the intersection of the "vertical" line joining <math>P(x,y), P'(x,-y)</math> and the curve. However, if <math>\gcd(v,n) \neq 1, n</math>, then the point addition will not produce a meaningful point on the curve; but, more importantly, <math>\gcd(v,n)</math> is a non-trivial factor of <math>n</math>.
  3. Compute <math>[k]P</math> on the elliptic curve (<math>\bmod n</math>), where <math>k</math> is a product of many small numbers: say, a product of small primes raised to small powers, as in the p-1 algorithm, or the factorial <math>B!</math> for some not too large <math>B</math>. This can be done efficiently, one small factor at a time. Say, to get <math>[B!]P</math>, first compute <math>[2]P</math>, then <math>[3]([2]P)</math>, then <math>[4]([3!]P)</math>, and so on. <math>B</math> is picked to be small enough so that <math>B</math>-wise point addition can be performed in reasonable time.
    • If we finish all the calculations above without encountering non-invertible elements (<math>\bmod n</math>), it means that the elliptic curves' (modulo primes) order is not smooth enough, so we need to try again with a different curve and starting point.
    • If we encounter a <math>\gcd(v,n) \neq 1,n</math> we are done: it is a non-trivial factor of <math>n</math>.

The time complexity depends on the size of the number's smallest prime factor and can be represented by Template:Math, where p is the smallest factor of n, or <math>L_p\left[\frac{1}{2},\sqrt{2}\right]</math>, in L-notation.

ExplanationEdit

If p and q are two prime divisors of n, then Template:Math Template:Math implies the same equation also Template:Math and Template:Math These two smaller elliptic curves with the <math>\boxplus</math>-addition are now genuine groups. If these groups have Np and Nq elements, respectively, then for any point P on the original curve, by Lagrange's theorem, Template:Math is minimal such that <math>kP=\infty</math> on the curve modulo p implies that k divides Np; moreover, <math>N_p P=\infty</math>. The analogous statement holds for the curve modulo q. When the elliptic curve is chosen randomly, then Np and Nq are random numbers close to Template:Math and Template:Math respectively (see below). Hence it is unlikely that most of the prime factors of Np and Nq are the same, and it is quite likely that while computing eP, we will encounter some kP that is ∞ Template:Math but not Template:Math or vice versa. When this is the case, kP does not exist on the original curve, and in the computations we found some v with either Template:Math or Template:Math but not both. That is, Template:Math gave a non-trivial factor Template:Math

ECM is at its core an improvement of the older [[Pollard's p − 1 algorithm|Template:Math algorithm]]. The Template:Math algorithm finds prime factors p such that Template:Math is b-powersmooth for small values of b. For any e, a multiple of Template:Math and any a relatively prime to p, by Fermat's little theorem we have Template:Math. Then Template:Math is likely to produce a factor of n. However, the algorithm fails when Template:Math has large prime factors, as is the case for numbers containing strong primes, for example.

ECM gets around this obstacle by considering the group of a random elliptic curve over the finite field Zp, rather than considering the multiplicative group of Zp which always has order Template:Math

The order of the group of an elliptic curve over Zp varies (quite randomly) between Template:Math and Template:Math by Hasse's theorem, and is likely to be smooth for some elliptic curves. Although there is no proof that a smooth group order will be found in the Hasse-interval, by using heuristic probabilistic methods, the Canfield–Erdős–Pomerance theorem with suitably optimized parameter choices, and the L-notation, we can expect to try Template:Math curves before getting a smooth group order. This heuristic estimate is very reliable in practice.

Example usageEdit

The following example is from Template:Harvtxt, with some details added.

We want to factor Template:Math Let's choose the elliptic curve Template:Math with the point Template:Math on it, and let's try to compute Template:Math

The slope of the tangent line at some point A=(x, y) is Template:Math. Using s we can compute 2A. If the value of s is of the form a/b where b > 1 and gcd(a,b) = 1, we have to find the modular inverse of b. If it does not exist, gcd(n,b) is a non-trivial factor of n.

First we compute 2P. We have Template:Math so the coordinates of Template:Math are Template:Math and Template:Math Template:Math all numbers understood Template:Math Just to check that this 2P is indeed on the curve: Template:Nowrap

Then we compute 3(2P). We have Template:Math Using the Euclidean algorithm: Template:Nowrap then Template:Nowrap then Template:Nowrap then Template:Nowrap then Template:Nowrap then Template:Nowrap Hence Template:Nowrap and working backwards (a version of the extended Euclidean algorithm): Template:Nowrap Template:Nowrap Hence Template:Nowrap and Template:Nowrap Given this s, we can compute the coordinates of 2(2P), just as we did above: Template:Math Just to check that this is indeed a point on the curve: Template:Math After this, we can compute <math>3(2P) = 4P \boxplus 2P</math>.

We can similarly compute 4!P, and so on, but 8!P requires inverting Template:Nowrap The Euclidean algorithm gives that 455839 is divisible by 599, and we have found a Template:Nowrap

The reason that this worked is that the curve Template:Nowrap has Template:Nowrap points, while Template:Nowrap it has Template:Nowrap points. Moreover, 640 and 777 are the smallest positive integers k such that Template:Math on the curve Template:Nowrap and Template:Math respectively. Since Template:Nowrap is a multiple of 640 but not a multiple of 777, we have Template:Math on the curve Template:Nowrap but not on the curve Template:Nowrap hence the repeated addition broke down here, yielding the factorization.

The algorithm with projective coordinatesEdit

Before considering the projective plane over <math>(\Z/n\Z)/\sim,</math> first consider a 'normal' projective space over <math>\mathbb{R}</math>: Instead of points, lines through the origin are studied. A line may be represented as a non-zero point <math>(x,y,z)</math>, under an equivalence relation ~ given by: <math>(x,y,z)\sim(x',y',z')</math> ⇔ ∃ c ≠ 0 such that x' = cx, y' = cy and z' = cz. Under this equivalence relation, the space is called the projective plane <math>\mathbb{P}^2</math>; points, denoted by <math>(x:y:z)</math>, correspond to lines in a three-dimensional space that pass through the origin. Note that the point <math>(0:0:0)</math> does not exist in this space since to draw a line in any possible direction requires at least one of x',y' or z' ≠ 0. Now observe that almost all lines go through any given reference plane - such as the (X,Y,1)-plane, whilst the lines precisely parallel to this plane, having coordinates (X,Y,0), specify directions uniquely, as 'points at infinity' that are used in the affine (X,Y)-plane it lies above.

In the algorithm, only the group structure of an elliptic curve over the field <math>\mathbb{R}</math> is used. Since we do not necessarily need the field <math>\mathbb{R}</math>, a finite field will also provide a group structure on an elliptic curve. However, considering the same curve and operation over <math>(\Z/n\Z)/\sim</math> with Template:Mvar not a prime does not give a group. The Elliptic Curve Method makes use of the failure cases of the addition law.

We now state the algorithm in projective coordinates. The neutral element is then given by the point at infinity <math>(0:1:0)</math>. Let Template:Mvar be a (positive) integer and consider the elliptic curve (a set of points with some structure on it) <math>E(\Z/n\Z)=\{(x:y:z) \in \mathbb{P}^2\ |\ y^2z=x^3+axz^2+bz^3\}</math>.

  1. Pick <math>x_P,y_P,a \in \Z/n\Z</math> with Template:Mvar ≠ 0.
  2. Calculate <math>b = y_P^2 - x_P^3 - ax_P</math>. The elliptic curve Template:Mvar is then in Weierstrass form given by <math>y^2 = x^3 + ax + b</math> and by using projective coordinates the elliptic curve is given by the homogeneous equation <math>ZY^2=X^3+aZ^2X+bZ^3</math>. It has the point <math>P=(x_P:y_P:1)</math>.
  3. Choose an upperbound <math>B \in \Z</math> for this elliptic curve. Remark: You will only find factors Template:Mvar if the group order of the elliptic curve Template:Mvar over <math>\Z/p\Z</math> (denoted by <math>\#E(\Z/p\Z)</math>) is B-smooth, which means that all prime factors of <math>\#E(\Z/p\Z)</math> have to be less or equal to Template:Mvar.
  4. Calculate <math>k={\rm lcm}(1,\dots ,B)</math>.
  5. Calculate <math>k P := P + P + \cdots + P </math> (k times) in the ring <math>E(\Z/n\Z)</math>. Note that if <math>\#E(\Z/n\Z)</math> is Template:Mvar-smooth and Template:Mvar is prime (and therefore <math>\Z/n\Z</math> is a field) that <math>kP = (0:1:0)</math>. However, if only <math>\#E(\Z/p\Z)</math> is B-smooth for some divisor Template:Mvar of Template:Mvar, the product might not be (0:1:0) because addition and multiplication are not well-defined if Template:Mvar is not prime. In this case, a non-trivial divisor can be found.
  6. If not, then go back to step 2. If this does occur, then you will notice this when simplifying the product <math>kP.</math>

In point 5 it is said that under the right circumstances a non-trivial divisor can be found. As pointed out in Lenstra's article (Factoring Integers with Elliptic Curves) the addition needs the assumption <math>\gcd(x_1-x_2,n)=1</math>. If <math>P,Q</math> are not <math>(0:1:0)</math> and distinct (otherwise addition works similarly, but is a little different), then addition works as follows:

  • To calculate: <math> R = P + Q;</math> <math>P = (x_1:y_1:1), Q = (x_2:y_2:1)</math>,
  • <math>\lambda =(y_1-y_2) (x_1-x_2)^{-1}</math>,
  • <math> x_3 = \lambda^2 - x_1 - x_2</math>,
  • <math> y_3 = \lambda(x_1-x_3) - y_1</math>,
  • <math> R = P + Q = (x_3:y_3:1)</math>.

If addition fails, this will be due to a failure calculating <math>\lambda.</math> In particular, because <math>(x_1-x_2)^{-1}</math> can not always be calculated if Template:Mvar is not prime (and therefore <math>\Z/n\Z</math> is not a field). Without making use of <math>\Z/n\Z</math> being a field, one could calculate:

  • <math>\lambda'=y_1-y_2</math>,
  • <math> x_3' = {\lambda'}^2 - x_1(x_1-x_2)^2 - x_2(x_1-x_2)^2</math>,
  • <math> y_3' = \lambda'(x_1(x_1-x_2)^2-x_3') - y_1(x_1-x_2)^3</math>,
  • <math> R = P + Q = (x_3'(x_1-x_2):y_3':(x_1-x_2)^3)</math>, and simplify if possible.

This calculation is always legal and if the gcd of the Template:Mvar-coordinate with Template:Mvar ≠ (1 or Template:Mvar), so when simplifying fails, a non-trivial divisor of Template:Mvar is found.

Twisted Edwards curvesEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} The use of Edwards curves needs fewer modular multiplications and less time than the use of Montgomery curves or Weierstrass curves (other used methods). Using Edwards curves you can also find more primes.

Definition. Let <math>k</math> be a field in which <math>2 \neq 0</math>, and let <math>a,d \in k\setminus\{0\}</math> with <math>a\neq d</math>. Then the twisted Edwards curve <math>E_{E,a,d}</math> is given by <math>ax^2+y^2=1+dx^2y^2.</math> An Edwards curve is a twisted Edwards curve in which <math>a=1</math>.

There are five known ways to build a set of points on an Edwards curve: the set of affine points, the set of projective points, the set of inverted points, the set of extended points and the set of completed points.

The set of affine points is given by:

<math>\{(x,y)\in \mathbb{A}^2 : ax^2+y^2=1+dx^2y^2\}</math>.

The addition law is given by

<math>(e,f),(g,h) \mapsto \left(\frac{eh+fg}{1+ degfh},\frac{fh-aeg}{1-degfh}\right).</math>

The point (0,1) is its neutral element and the inverse of <math>(e,f)</math> is <math>(-e,f)</math>.

The other representations are defined similar to how the projective Weierstrass curve follows from the affine.

Any elliptic curve in Edwards form has a point of order 4. So the torsion group of an Edwards curve over <math>\Q</math> is isomorphic to either <math>\Z/4\Z, \Z/8\Z, \Z/12\Z,\Z/2\Z \times \Z/4\Z</math> or <math>\Z/2\Z\times \Z/8\Z</math>.

The most interesting cases for ECM are <math>\Z/12\Z</math> and <math>\Z/2\Z\times \Z/8\Z</math>, since they force the group orders of the curve modulo primes to be divisible by 12 and 16 respectively. The following curves have a torsion group isomorphic to <math>\Z/12\Z</math>:

  • <math>x^2+y^2=1+dx^2y^2</math> with point <math>(a,b) </math> where <math>b \notin\{-2,-1/2,0,\pm1\}, a^2=-(b^2+2b) </math> and <math>d=-(2b+1)/(a^2b^2) </math>
  • <math>x^2+y^2=1+dx^2y^2</math> with point <math>(a,b) </math> where <math>a=\frac{u^2-1}{u^2+1}, b=-\frac{(u-1)^2}{u^2+1}</math> and <math>d=\frac{(u^2+1)^3(u^2-4u+1)}{(u-1)^6(u+1)^2}, u\notin\{0,\pm1\}.</math>

Every Edwards curve with a point of order 3 can be written in the ways shown above. Curves with torsion group isomorphic to <math>\Z/2\Z\times \Z/8\Z</math> and <math>\Z/2\Z\times \Z/4\Z</math> may be more efficient at finding primes.<ref name=Bernstein2008>{{#invoke:citation/CS1|citation |CitationClass=web }} (see top of page 30 for examples of such curves)</ref>

Stage 2Edit

The above text is about the first stage of elliptic curve factorisation. There one hopes to find a prime divisor Template:Mvar such that <math>sP</math> is the neutral element of <math>E(\mathbb{Z}/p\mathbb{Z})</math>. In the second stage one hopes to have found a prime divisor Template:Mvar such that <math>sP</math> has small prime order in <math>E(\mathbb{Z}/q\mathbb{Z})</math>.

We hope the order to be between <math>B_1</math> and <math>B_2</math>, where <math>B_1</math> is determined in stage 1 and <math>B_2</math> is new stage 2 parameter. Checking for a small order of <math>sP</math>, can be done by computing <math>(ls)P</math> modulo Template:Mvar for each prime Template:Mvar.

GMP-ECM and EECM-MPFQEdit

The use of Twisted Edwards elliptic curves, as well as other techniques were used by Bernstein et al<ref name=Bernstein2008 /> to provide an optimized implementation of ECM. Its only drawback is that it works on smaller composite numbers than the more general purpose implementation, GMP-ECM of Zimmermann.

Hyperelliptic-curve method (HECM)Edit

There are recent developments in using hyperelliptic curves to factor integers. Cosset shows in his article (of 2010) that one can build a hyperelliptic curve with genus two (so a curve <math>y^2 = f(x)</math> with Template:Mvar of degree 5), which gives the same result as using two "normal" elliptic curves at the same time. By making use of the Kummer surface, calculation is more efficient. The disadvantages of the hyperelliptic curve (versus an elliptic curve) are compensated by this alternative way of calculating. Therefore, Cosset roughly claims that using hyperelliptic curves for factorization is no worse than using elliptic curves.

Quantum version (GEECM)Edit

Bernstein, Heninger, Lou, and Valenta suggest GEECM, a quantum version of ECM with Edwards curves.<ref>Bernstein D.J., Heninger N., Lou P., Valenta L. (2017) Post-quantum RSA. In: Lange T., Takagi T. (eds), Post-Quantum Cryptography. PQCrypto 2017. Lecture Notes in Computer Science, vol 10346. Springer, Cham</ref> It uses Grover's algorithm to roughly double the length of the primes found compared to standard EECM, assuming a quantum computer with sufficiently many qubits and of comparable speed to the classical computer running EECM.

ReferencesEdit

Template:Reflist

External linksEdit

Template:Number theoretic algorithms

Retrieved from "https://zalansite.site/mediawiki/index.php?title=Lenstra_elliptic-curve_factorization&oldid=112488"