# 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**

**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**

**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