Large Integer Factorization Algorithm and Its Practice
08/02/2023
Large Integer Factorization
In 1977, RSA (Rivest–Shamir–Adleman), a cryptosystem based on factorizing large integers was born. It was named after its three creators, Ron Rivest, Adi Shamir, and Leonard Adleman, using their surnames' initials.
With the significant contributions of the RSA algorithm to public-key cryptography and its profound impact worldwide, the three creators were then awarded the Turing Award in 2002.
Until today, the integer factorization problem remains one of the most crucial subjects in almost all aspects of public-key cryptography security.
The security of the RSA algorithm depends on large number factorization, which is
to factorize a large integer into a product of several large prime factors.
Some typical large integer factorization algorithms targeting small factors are:
Pollard's rho algorithm
Pollard’s p-1 algorithm
ECM algorithm (known as Lenstra elliptic curve factorization or elliptic-curve factorization method)
In this article, we will first introduce Pollard's p-1 algorithm and the ECM algorithm. Additionally, we will present a specific implementation of the ECM algorithm called GMP-ECM.
Pollard’s p-1 Algorithm
STEPS
Definition
Calculation
ECM Algorithm
To improve this method, the ECM (Elliptic Curve Method) introduces random elliptic curves to transform the original multiplicative group into a group consisting of points on the elliptic curve.
The elliptic curve method is a number-theoretic algorithm that utilizes the properties and arithmetic rules of points on an elliptic curve to search for factors that satisfy certain conditions.
Overview of ECM Algorithm
GMP-ECM: An Implementation of ECM Algorithm
The GMP-ECM implementation makes optimizations based on the original ECM method.
Stage 1
In Stage 1, GMP-ECM has optimized the selection and calculation of the elliptic curve.
Random Elliptic Curve Generation
In GMP-ECM, certain methods are employed for elliptic curve generation to ensure that the order of the generated elliptic curve satisfies certain properties, for example:
Elliptic Curve Operation
In GMP-ECM, the Montgomery curve is used, and the multiplication or addition of points follows the following rules:
Stage 2
The main idea of Stage 2 is the meet-in-the-middle strategy:
Algorithm Complexity
Example
Use the tool which uses GMP-ECM to factorize:
Then, we successfully find the prime factor 1021791499165844943393503.
Last updated