8.6 Elliptic curve method for integer factorization

The elliptic curve method (ECM) is a powerful integer factorization algorithm that uses elliptic curves to find factors of large composite numbers. It's particularly effective for finding small factors, making it a great preprocessing step before applying other factoring methods like the quadratic sieve or number field sieve.

ECM exploits the group structure of elliptic curves over finite fields to detect factors of the input number. Introduced by Hendrik Lenstra in 1987, the algorithm works by randomly selecting elliptic curves and points, then computing scalar multiples to find factors. It's especially useful for factors up to 30-40 digits long.

Elliptic curve method overview

• The elliptic curve method (ECM) is a fast integer factorization algorithm that uses elliptic curves to find factors of large composite numbers
• ECM is particularly effective for finding small factors and is often used as a preprocessing step before applying other factoring methods like the quadratic sieve or number field sieve
• The key idea behind ECM is to exploit the group structure of elliptic curves over finite fields to detect factors of the input number

Lenstra's elliptic curve factorization algorithm

Top images from around the web for Lenstra's elliptic curve factorization algorithm

• 

  Category:Elliptic curves - Wikimedia Commons View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

• 

  Annotated curve E with points P, Q, R, R' and line L labeled. View original

  Is this image relevant?

• 

  Category:Elliptic curves - Wikimedia Commons View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

1 of 3

Top images from around the web for Lenstra's elliptic curve factorization algorithm

• 

  Category:Elliptic curves - Wikimedia Commons View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

• 

  Annotated curve E with points P, Q, R, R' and line L labeled. View original

  Is this image relevant?

• 

  Category:Elliptic curves - Wikimedia Commons View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

1 of 3

• Hendrik Lenstra introduced the elliptic curve factorization algorithm in 1987 as a generalization of Pollard's $p-1$ method
• Lenstra's algorithm works by randomly selecting elliptic curves and points on those curves, then computing scalar multiples of the points in an attempt to find a factor of the input number
• If a non-trivial factor is found during the scalar multiplication process, the algorithm terminates and returns the factor
• If no factor is found after a certain number of iterations, a new elliptic curve and point are chosen and the process repeats

Comparison vs other factoring methods

• ECM is particularly effective for finding small factors (up to around 30-40 digits) of large composite numbers
• For larger factors, other methods like the quadratic sieve and number field sieve are generally more efficient
• ECM has a heuristic runtime of $O(e^{\sqrt{2\log p \log \log p}})$ for finding a prime factor $p$, which is subexponential in the size of $p$
• In practice, ECM is often used in conjunction with other factoring methods, serving as a preprocessing step to remove small factors before applying more powerful algorithms

Elliptic curves over finite fields

• To apply elliptic curves to integer factorization, we work with elliptic curves defined over finite fields, specifically the ring of integers modulo $n$ (where $n$ is the number we want to factor)
• An elliptic curve over a finite field is a set of points $(x, y)$ satisfying an equation of the form $y^2 = x^3 + ax + b$, along with a special point called the "point at infinity"
• The coefficients $a$ and $b$ are chosen such that the discriminant $\Delta = 4a^3 + 27b^2$ is nonzero modulo $n$ to ensure the curve is smooth

Elliptic curves modulo n

• When working with elliptic curves modulo $n$, the points on the curve are represented by pairs $(x, y)$ where $x$ and $y$ are integers in the range $[0, n-1]$
• The point at infinity serves as the identity element for the group law on the elliptic curve
• If $n$ is composite, the elliptic curve modulo $n$ may have a different structure than the curves over the prime factors of $n$, which is exploited by the ECM algorithm

Group law for elliptic curves mod n

• The points on an elliptic curve form an abelian group under a well-defined group law
• The group law for elliptic curves is defined geometrically:
  • To add two points $P$ and $Q$, draw a line through $P$ and $Q$ and find the third point of intersection with the curve, then reflect that point across the $x$-axis to obtain $P + Q$
  • If $P = Q$, the line is taken to be the tangent line at $P$
  • The point at infinity serves as the identity element, so $P + O = P$ for any point $P$ on the curve
• The group law can be expressed algebraically using explicit formulas involving the coordinates of the points

Calculating multiples of points

• A key operation in ECM is computing scalar multiples of points on the elliptic curve, i.e., calculating $kP$ for a positive integer $k$ and a point $P$
• Scalar multiplication can be efficiently computed using the double-and-add algorithm, which is analogous to the square-and-multiply algorithm for modular exponentiation
• The double-and-add algorithm works by expressing $k$ in binary and iteratively doubling and adding points based on the binary representation of $k$
• Optimizations like the sliding window method and signed-digit representations can further speed up scalar multiplication

Factorization process

• The ECM algorithm attempts to find a factor of a composite number $n$ by randomly selecting elliptic curves and points, then computing scalar multiples of the points in the hope of encountering a non-trivial factor

Choosing random elliptic curves and points

• To start the factorization process, a random elliptic curve $E$ and a random point $P$ on that curve are selected
• The curve coefficients $a$ and $b$ are typically chosen uniformly at random from the range $[0, n-1]$, subject to the constraint that the discriminant is nonzero modulo $n$
• The point $P$ is selected by choosing a random $x$-coordinate in the range $[0, n-1]$ and solving for the corresponding $y$-coordinate using the curve equation

Computing scalar multiples

• Once a curve $E$ and a point $P$ have been selected, the algorithm computes the scalar multiple $kP$ for a suitably chosen integer $k$
• The choice of $k$ is critical to the success of the algorithm; it should be smooth (i.e., have only small prime factors) and not too large
• Common choices for $k$ include prime powers, factorials, and products of small primes up to a certain bound
• The scalar multiple $kP$ is computed using the double-and-add algorithm or one of its optimized variants

Detecting non-trivial factors

• As the scalar multiple $kP$ is being computed, the algorithm checks for the occurrence of a non-trivial factor of $n$
• This is done by computing the greatest common divisor (GCD) of the difference of the $x$-coordinates of certain intermediate points encountered during the scalar multiplication process
• If the GCD is not 1 or $n$, then a non-trivial factor has been found, and the algorithm terminates successfully

Handling trivial factors and failure cases

• If the GCD computed during the scalar multiplication process is 1, then no factor has been found, and the algorithm proceeds to the next iteration with a new curve and point
• If the GCD is equal to $n$, then the chosen curve was singular modulo $n$, and a new curve must be selected
• After a certain number of iterations (determined by a heuristic based on the size of the smallest prime factor), if no factor has been found, the algorithm terminates unsuccessfully

Optimizing curve and point selection

• The success of ECM depends heavily on the choice of elliptic curves and points
• Various strategies have been proposed to optimize the selection process, such as:
  • Using curves with small coefficients to reduce the cost of curve arithmetic
  • Selecting curves with a large number of points modulo small primes to increase the chances of finding a factor
  • Using a "second phase" with a different choice of $k$ to find factors that may have been missed in the first phase
• Implementing these optimizations can significantly improve the performance of ECM in practice

ECM runtime analysis

• The runtime of ECM depends on various factors, including the size of the input number, the size of the smallest prime factor, and the choice of parameters used in the algorithm

Heuristic runtime of ECM

• The heuristic runtime of ECM for finding a prime factor $p$ of a composite number $n$ is $O(e^{\sqrt{2\log p \log \log p}})$
• This runtime is subexponential in the size of $p$, making ECM particularly effective for finding small prime factors
• The heuristic assumes that the elliptic curve group orders modulo the prime factors of $n$ behave like random integers, which is supported by empirical evidence

Comparison vs quadratic sieve and NFS

• For finding small prime factors (up to around 30-40 digits), ECM is generally faster than other factoring methods like the quadratic sieve and number field sieve
• However, for larger prime factors, the quadratic sieve and number field sieve become more efficient due to their subexponential runtime in the size of $n$
• In practice, ECM is often used as a preprocessing step to remove small prime factors before applying more powerful factoring algorithms

Asymptotic complexity of ECM

• The asymptotic complexity of ECM is subexponential in the size of the smallest prime factor $p$, but exponential in the size of the input number $n$
• This means that ECM is not a polynomial-time algorithm for integer factorization, and its effectiveness diminishes as the size of the prime factors increases
• Despite its exponential worst-case complexity, ECM remains a valuable tool in practice due to its efficiency in finding small prime factors

Optimal ECM parameters for various sizes

• The choice of parameters, such as the bound on the prime factors of $k$ and the number of iterations, can significantly impact the performance of ECM
• Optimal parameter choices depend on the size of the input number and the desired trade-off between runtime and success probability
• Heuristics and empirical data are used to determine suitable parameter values for different input sizes
• In general, larger input numbers require larger bounds on the prime factors of $k$ and more iterations to achieve a high success probability

ECM implementation considerations

• Implementing ECM efficiently requires careful consideration of various aspects, such as the representation of elliptic curve points, the choice of coordinate system, and the optimization of curve arithmetic

Representing points and curves

• The choice of coordinate system can significantly impact the performance of ECM implementations
• Common coordinate systems include:
  • Affine coordinates: Points are represented as $(x, y)$ pairs satisfying the curve equation
  • Projective coordinates: Points are represented as $(X : Y : Z)$ triples, allowing for more efficient curve arithmetic
  • Montgomery coordinates: A special form of projective coordinates that simplifies the scalar multiplication process
• The choice of coordinate system depends on the specific requirements of the implementation, such as memory constraints and the relative costs of different field operations

Optimizing curve arithmetic

• Efficient implementation of elliptic curve arithmetic is crucial for the performance of ECM
• Various techniques can be used to optimize curve operations, such as:
  • Using fast reduction algorithms for modular arithmetic, like Montgomery reduction or Barrett reduction
  • Employing specialized field arithmetic algorithms for specific prime moduli, such as primes of the form $2^k \pm c$
  • Exploiting the structure of the curve equation to simplify point addition and doubling formulas
• Implementing these optimizations can significantly reduce the cost of curve arithmetic and improve the overall performance of ECM

Techniques for speeding up scalar multiplication

• Scalar multiplication is the most computationally expensive part of ECM, so optimizing this operation is critical for efficient implementations
• Various techniques can be used to speed up scalar multiplication, such as:
  • Using window-based methods, like the sliding window or fixed window algorithms, to reduce the number of point additions
  • Employing signed-digit representations, such as the non-adjacent form (NAF), to minimize the weight of the scalar
  • Precomputing frequently used scalar multiples to avoid redundant computations
• Combining these techniques can lead to significant speedups in the scalar multiplication process

Parallelization of ECM

• ECM is well-suited for parallelization, as the curve and point selection process can be performed independently across multiple threads or processors
• Parallelization strategies for ECM include:
  • Distributing the selection of curves and points across multiple threads, with each thread performing its own scalar multiplications
  • Using a master-slave model, where a central master process distributes curves and points to slave processes and collects the results
  • Employing a sieving approach, where multiple threads cooperate to find suitable curves and points based on certain criteria
• Effective parallelization can significantly reduce the runtime of ECM, especially for large input numbers

ECM in practice vs theory

• While the theoretical analysis of ECM provides valuable insights into its asymptotic behavior, the practical performance of the algorithm can vary significantly depending on the implementation and the specific input numbers
• In practice, ECM implementations often incorporate various optimizations and heuristics that are not captured by the theoretical analysis, such as:
  • Using a second phase with a different choice of $k$ to find factors missed in the first phase
  • Employing early abort strategies to detect singular curves or unlikely success cases
  • Adapting the parameter choices based on the size and structure of the input number
• Practical implementations of ECM also need to account for factors like memory constraints, cache effects, and the relative costs of different field operations, which can impact the optimal choice of parameters and implementation strategies
• Despite these differences between theory and practice, ECM remains a powerful and widely-used factoring algorithm, particularly for finding small prime factors of large composite numbers