Lenstra’s Elliptic Curve Factorization Method

In December 2019, a team led by Paul Zimmermann of INRIA announced the factorization of the largest ever RSA modulus (RSA-240):

RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099
RSA-240 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517
        × 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447

The factorization involved factorizing a 795-bit integer into its prime number factors. It caused industry experts to define that RSA would only be safe with at least 2,048-bit keys.

The security of several public key methods rely on the difficulty in factorizing a modulus created from the multiplication of large prime numbers. RSA is a good example of this, and where we take two large prime numbers (p and q), and multiply them to create a modulus (N). The difficulty is then to be able to find p and q, if we know N. The two core methods we can use for this factorization are the general number field sieve (GNFS) method and ECM (Elliptic Curve Method).