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

  1. Definition

  2. 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

N = 0xA2862FB145AC7CE580E0BFF3CEFF42646050F8C611D36A3026E6EFB433B5CDD9EEFBA893E3F25C23A4951BA20992680162934CBDB6876CC791738C140C6EA6EC82938F7E18C5F0760367CF20883DCAB1D6885E222BBC7A1B5D434FD9FC148E387FA9AD69CE708FDDDE3E963F9AB2AF2046A37D7DBA21BC92E6F2A631C3E7770C77C95FAD6F1DC60D9F0645AEF2CC5D03D2151E35443FE0F90F1E2EAE58489C4450C8281EDCC58DDB409C306797C616954ACABCE4881E40ABDD2689A9F7596F29CD5CB42C752DA9306E7DB87CAC8957E3CA165421CF9E1B7220759A10588B386E33FD8E762E92C9F79D50150EF5FCA5F411DE23B8DFFE47A95D48ADDCF4797565

Use the tool which uses GMP-ECM to factorize:

ecm -c 2  25e4 1.3e8 -mpzmod threads: 2 mod: 1
A2862FB145AC7CE580E0BFF3CEFF42646050F8C611D36A3026E6EFB433B5CDD9EEFBA893E3F25C23A4951BA20992680162934CBDB6876CC791738C140C6EA6EC82938F7E18C5F0760367CF20883DCAB1D6885E222BBC7A1B5D434FD9FC148E387FA9AD69CE708FDDDE3E963F9AB2AF2046A37D7DBA21BC92E6F2A631C3E7770C77C95FAD6F1DC60D9F0645AEF2CC5D03D2151E35443FE0F90F1E2EAE58489C4450C8281EDCC58DDB409C306797C616954ACABCE4881E40ABDD2689A9F7596F29CD5CB42C752DA9306E7DB87CAC8957E3CA165421CF9E1B7220759A10588B386E33FD8E762E92C9F79D50150EF5FCA5F411DE23B8DFFE47A95D48ADDCF4797565
********** Factor found in step 2: 1021791499165844943393503 21 52761ms

Then, we successfully find the prime factor 1021791499165844943393503.

Last updated