RSA numbers
In-game article clicks load inline without leaving the challenge.
In mathematics, the RSA numbers are a set of large semiprimes (numbers with exactly two prime factors) that were part of the RSA Factoring Challenge. The challenge was to find the prime factors of each number. It was created by RSA Laboratories in March 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers. The challenge was ended in 2007.
RSA Laboratories (which is an initialism of the creators of the technique, Rivest, Shamir and Adleman) published a number of semiprimes with 100 to 617 decimal digits. Cash prizes of varying size, up to US$200,000 (and prizes up to $20,000 awarded), were offered for factorization of some of them. The smallest RSA number was factored in a few days. Most of the numbers have still not been factored and many of them are expected to remain unfactored for many years to come. As of February 2020[update], the smallest 23 of the 54 listed numbers have been factored.
While the RSA challenge officially ended in 2007, people are still attempting to find the factorizations. According to RSA Laboratories, "Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common symmetric-key and public-key algorithms, these challenges are no longer active." Some of the smaller prizes had been awarded at the time. The remaining prizes were retracted.
The first RSA numbers generated, from RSA-100 to RSA-500, were labeled according to their number of decimal digits. Later, beginning with RSA-576, binary digits are counted instead. An exception to this is RSA-617, which was created before the change in the numbering scheme. The numbers (sequence A391940 in the OEIS) are listed in increasing order below.
| name | dec digits | first solver | |||
|---|---|---|---|---|---|
| date | algorithm | compute power | calendar time | ||
| RSA-100 | 1991-04-01 | ppmpqs by Mark Manasse and Arjen K. Lenstra | approx. 7 MIP-Years | ||
| RSA-110 | 1992-04-14 | ppmpqs by Arjen K. Lenstra | one month on 5/8 of a 16K MasPar | ||
| RSA-120 | 1993-06-09 | ppmpqs | 835 mips years run by Arjen K. Lenstra (45.503%), Bruce Dodson (30.271%), Thomas Denny (22.516%), Mark Manasse (1.658%), and Walter Lioen and Herman te Riele (0.049%) | ||
| RSA-129 | 129 | 1994-04-26 | ppmpqs | approximately 5000 mips years run by Derek Atkins, Michael Graff, Arjen K. Lenstra, Paul Leyland, and more than 600 volunteers | |
| RSA-130 | 1996-04-10 | General Number Field Sieve with lattice sieving implementations by Bellcore, CWI, and Saarbruecken; and blocked Lanczos and square root by Peter L. Montgomery | sieving: estimated 500 mips years, run by Bruce Dodson (28.37%), Peter L. Montgomery and Marije Elkenbracht-Huizing (27.77%), Arjen K. Lenstra (19.11%), WWW contributors (17.17% ), Matt Fante (4.36%), Paul Leyland (1.66%), Damian Weber and Joerg Zayer (1.56%) matrix (67.5 hours on the Cray-C90 at SARA, Amsterdam) and square root (48 hours per dependency on an SGI Challenge processor) run by Peter L. Montgomery and Marije Elkenbracht-Huizing | ||
| RSA-140 | 1999-02-02 | GNFS with line (by CWI; 45%) and lattice (by Arjen K. Lenstra; 55%) sieving, and a polynomial selection method by Brian Murphy and Peter L. Montgomery; and blocked Lanczos and square root by Peter L. Montgomery | polynomial selection: 2000 CPU hours on four 250 MHZ SGI Origin 2000 processors at CWI sieving: 8.9 CPU-years on about 125 SGI and Sun workstations running at 175 MHZ on average, and on about 60 PCs running at 300 MHZ on average; approximately equivalent to 1500 mips years; run by Peter L. Montgomery, Stefania Cavallar, Herman J.J. te Riele, and Walter M. Lioen (36.8%), Paul Leyland (28.8%), Bruce Dodson (26.6%), Paul Zimmermann (5.4%), and Arjen K. Lenstra (2.5%).matrix: 100 hours on the Cray-C916 at SARA, Amsterdamsquare root: four different dependencies were run in parallel on four 250 MHZ SGI Origin 2000 processors at CWI; three of them found the factors of RSA-140 after 14.2, 19.0 and 19.0 CPU-hours | eleven weeks (including four weeks for polynomial selection, one month for sieving, one week for data filtering and matrix construction, five days for the matrix, and 14.2 hours to find the factors using the square root) | |
| RSA-155 | 1999-08-22 | GNFS with line (29%) and lattice (71%) sieving, and a polynomial selection method written by Brian Murphy and Peter L. Montgomery, ported by Arjen Lenstra to use his multiple precision arithmetic code (LIP); and blocked Lanczos and square root by Peter L. Montgomery | polynomial selection run by Brian Murphy, Peter Montgomery, Arjen Lenstra and Bruce Dodson; Dodson found the one that was used sieving: 35.7 CPU-years in total, on about one hundred and sixty 175-400 MHz SGI and Sun workstations, eight 250 MHz SGI Origin 2000 processors, one hundred and twenty 300-450 MHz Pentium II PCs, and four 500 MHz Digital/Compaq boxes; approximately equivalent to 8000 mips years; run by Alec Muffett (20.1% of relations, 3057 CPU days), Paul Leyland (17.5%, 2092 CPU days), Peter L. Montgomery and Stefania Cavallar (14.6%, 1819 CPU days), Bruce Dodson (13.6%, 2222 CPU days), Francois Morain and Gerard Guillerm (13.0%, 1801 CPU days), Joel Marchand (6.4%, 576 CPU days), Arjen K. Lenstra (5.0%, 737 CPU days), Paul Zimmermann (4.5%, 252 CPU days), Jeff Gilchrist (4.0%, 366 CPU days), Karen Aardal (0.65%, 62 CPU days), and Chris and Craig Putnam (0.56%, 47 CPU days)matrix: 224 hours on one CPU of the Cray-C916 at SARA, Amsterdam square root: four 300 MHz R12000 processors of a 24-processor SGI Origin 2000 at CWI; the successful one took 39.4 CPU-hours and the others took 38.3, 41.9, and 61.6 CPU-hours | 9 weeks for polynomial selection, plus 5.2 months for the rest (including 3.7 months for sieving, about 1 month for data filtering and matrix construction, and 10 days for the matrix) |
| Contents | |||||
|---|---|---|---|---|---|
| RSA-100 RSA-110 RSA-120 RSA-129 RSA-130 RSA-140 RSA-150 RSA-155 RSA-160 | RSA-170 RSA-576 RSA-180 RSA-190 RSA-640 RSA-200 RSA-210 RSA-704 RSA-220 | RSA-230 RSA-232 RSA-768 RSA-240 RSA-250 RSA-260 RSA-270 RSA-896 RSA-280 | RSA-290 RSA-300 RSA-309 RSA-1024 RSA-310 RSA-320 RSA-330 RSA-340 RSA-350 | RSA-360 RSA-370 RSA-380 RSA-390 RSA-400 RSA-410 RSA-420 RSA-430 RSA-440 | RSA-450 RSA-460 RSA-1536 RSA-470 RSA-480 RSA-490 RSA-500 RSA-617 RSA-2048 |
| See also Notes References External links |
RSA-100
RSA-100 has 100 decimal digits (330 bits). Its factorization was announced on April 1, 1991, by Arjen K. Lenstra. Reportedly, the factorization took a few days using the multiple-polynomial quadratic sieve algorithm on a MasPar parallel computer.
The value and factorization of RSA-100 are as follows:
RSA-100 is often used to benchmark new factorization software or new hardware.
As of December 2009, it took four hours to repeat this factorization using the program Msieve on a 2200 MHz Athlon 64 processor.
As of June 2015, the number could be factorized in 72 minutes on overclocked to 3.5 GHz Intel Core2 Quad q9300, using GGNFS and Msieve binaries running by distributed version of the factmsieve Perl script.
As of June 2025, the number was factored in 108 seconds on 32 Epyc 9174 server cores using YAFU's implementation of the self initializing quadratic sieve.
As of January 2026, the number was reported to have been factored in 4 minutes and 57 seconds on an NVIDIA RTX 5070 Ti, the first such factorization on a complete quadratic sieve factorization pipeline on GPU.
RSA-110
RSA-110 has 110 decimal digits (364 bits), and was factored in April 1992 by Arjen K. Lenstra and Mark S. Manasse in approximately one month.
The number can be factorized in less than four hours on overclocked to 3.5 GHz Intel Core2 Quad q9300, using GGNFS and Msieve binaries running by distributed version of the factmsieve Perl script.
The value and factorization are as follows:
RSA-120
RSA-120 has 120 decimal digits (397 bits), and was factored in June 1993 by Thomas Denny, Bruce Dodson, Arjen K. Lenstra, and Mark S. Manasse. The computation took under three months of actual computer time.
The value and factorization are as follows:
RSA-129
RSA-129, having 129 decimal digits (426 bits), was not part of the 1991 RSA Factoring Challenge, but rather related to Martin Gardner's Mathematical Games column in the August 1977 issue of Scientific American.
RSA-129 was factored in April 1994 by a team led by Derek Atkins, Michael Graff, Arjen K. Lenstra and Paul Leyland, using approximately 1600 computers from around 600 volunteers connected over the Internet. A US$100 token prize was awarded by RSA Security for the factorization, which was donated to the Free Software Foundation.
The value and factorization are as follows:
The factorization was found using the Multiple Polynomial Quadratic Sieve algorithm.
The factoring challenge included a message encrypted with RSA-129. When decrypted using the factorization the message was revealed to be "The Magic Words are Squeamish Ossifrage".
In 2015, RSA-129 was factored in about one day, with the CADO-NFS open source implementation of number field sieve, using a commercial cloud computing service for about $30.
RSA-130
RSA-130 has 130 decimal digits (430 bits), and was factored on April 10, 1996, by a team led by Arjen K. Lenstra and composed of Jim Cowie, Marije Elkenbracht-Huizing, Wojtek Furmanski, Peter L. Montgomery, Damian Weber and Joerg Zayer.
The factorization was found in the third trial.
The value and factorization are as follows:
The factorization was found using the Number Field Sieve algorithm and the polynomial
which has a root of 12574411168418005980468 modulo RSA-130.
RSA-140
RSA-140 has 140 decimal digits (463 bits), and was factored on February 2, 1999, by a team led by Herman te Riele and composed of Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Paul Leyland, Walter Lioen, Peter L. Montgomery, Brian Murphy and Paul Zimmermann.
The value and factorization are as follows:
The factorization was found using the Number Field Sieve algorithm and an estimated 2000 MIPS-years of computing time.
The matrix had 4671181 rows and 4704451 columns and weight 151141999 (32.36 nonzeros per row)
RSA-150
RSA-150 has 150 decimal digits (496 bits), and was withdrawn from the challenge by RSA Security. RSA-150 was eventually factored into two 75-digit primes by Aoki et al. in 2004 using the general number field sieve (GNFS), years after bigger RSA numbers that were still part of the challenge had been solved.
The value and factorization are as follows:
RSA-155
RSA-155 has 155 decimal digits (512 bits), and was factored on August 22, 1999, in a span of six months, by a team led by Herman te Riele and composed of Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Walter Lioen, Peter L. Montgomery, Brian Murphy, Karen Aardal, Jeff Gilchrist, Gerard Guillerm, Paul Leyland, Joel Marchand, François Morain, Alec Muffett, Craig Putnam, Chris Putnam and Paul Zimmermann.
The value and factorization are as follows:
The factorization was found using the general number field sieve algorithm and an estimated 8000 MIPS-years of computing time.
The polynomials were 119377138320*x^5 - 80168937284997582*y*x^4 - 66269852234118574445*y^2*x^3 + 11816848430079521880356852*y^3*x^2 + 7459661580071786443919743056*y^4*x - 40679843542362159361913708405064*y^5 and x - 39123079721168000771313449081*y (this pair has a yield of relations approximately 13.5 times that of a random polynomial selection); 124722179 relations were collected in the sieving stage; the matrix had 6699191 rows and 6711336 columns and weight 417132631 (62.27 nonzeros per row).
RSA-160
RSA-160 has 160 decimal digits (530 bits), and was factored on April 1, 2003, by a team from the University of Bonn and the German Federal Office for Information Security (BSI). The team contained J. Franke, F. Bahr, T. Kleinjung, M. Lochter, and M. Böhm.
The value and factorization are as follows:
The factorization was found using the general number field sieve algorithm.
RSA-170
RSA-170 has 170 decimal digits (563 bits) and was first factored on December 29, 2009, by D. Bonenberger and M. Krone from Fachhochschule Braunschweig/Wolfenbüttel. An independent factorization was completed by S. A. Danilov and I. A. Popovyan two days later.
The value and factorization are as follows:
The factorization was found using the general number field sieve algorithm.
RSA-576
RSA-576 has 174 decimal digits (576 bits), and was factored on December 3, 2003, by J. Franke and T. Kleinjung from the University of Bonn. A cash prize of $10,000 was offered by RSA Security for a successful factorization.
The value and factorization are as follows:
The factorization was found using the general number field sieve algorithm.
RSA-180
RSA-180 has 180 decimal digits (596 bits), and was factored on May 8, 2010, by S. A. Danilov and I. A. Popovyan from Moscow State University, Russia.
The factorization was found using the general number field sieve algorithm implementation running on three Intel Core i7 PCs.
RSA-190
RSA-190 has 190 decimal digits (629 bits), and was factored on November 8, 2010, by I. A. Popovyan from Moscow State University, Russia, and A. Timofeev from CWI, Netherlands.
RSA-640
RSA-640 has 193 decimal digits (640 bits). A cash prize of US$20,000 was offered by RSA Security for a successful factorization. On November 2, 2005, F. Bahr, M. Boehm, J. Franke and T. Kleinjung of the German Federal Office for Information Security announced that they had factorized the number using GNFS as follows:
The computation took five months on 80 2.2 GHz AMD Opteron CPUs.
The slightly larger RSA-200 was factored in May 2005 by the same team.
RSA-200
RSA-200 has 200 decimal digits (663 bits), and factors into the two 100-digit primes given below.
On May 9, 2005, F. Bahr, M. Boehm, J. Franke, and T. Kleinjung announced that they had factorized the number using GNFS as follows:
The CPU time spent on finding these factors by a collection of parallel computers amounted – very approximately – to the equivalent of 75 years work for a single 2.2 GHz Opteron-based computer. Note that while this approximation serves to suggest the scale of the effort, it leaves out many complicating factors; the announcement states it more precisely.
RSA-210
RSA-210 has 210 decimal digits (696 bits) and was factored in September 2013 by Ryan Propper:
RSA-704
RSA-704 has 212 decimal digits (704 bits), and was factored by Shi Bai, Emmanuel Thomé and Paul Zimmermann. The factorization was announced July 2, 2012. A cash prize of US$30,000 was previously offered for a successful factorization.
RSA-220
RSA-220 has 220 decimal digits (729 bits), and was factored by S. Bai, P. Gaudry, A. Kruppa, E. Thomé and P. Zimmermann. The factorization was announced on May 13, 2016.
RSA-230
RSA-230 has 230 decimal digits (762 bits), and was factored by Samuel S. Gross on August 15, 2018.
RSA-232
RSA-232 has 232 decimal digits (768 bits), and was factored on February 17, 2020, by N. L. Zamarashkin, D. A. Zheltkov and S. A. Matveev.
RSA-768
RSA-768 has 232 decimal digits (768 bits), and was factored on December 12, 2009, over the span of two years, by Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Joppe W. Bos, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, and Paul Zimmermann.
The CPU time spent on finding these factors by a collection of parallel computers amounted approximately to the equivalent of almost 2000 years of computing on a single-core 2.2 GHz AMD Opteron-based computer.
RSA-240
RSA-240 has 240 decimal digits (795 bits), and was factored in November 2019 by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann.
The CPU time spent on finding these factors amounted to approximately 900 core-years on a 2.1 GHz Intel Xeon Gold 6130 CPU. Compared to the factorization of RSA-768, the authors estimate that better algorithms sped their calculations by a factor of 3–4 and faster computers sped their calculation by a factor of 1.25–1.67.
RSA-250
RSA-250 has 250 decimal digits (829 bits), and was factored in February 2020 by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann. The announcement of the factorization occurred on February 28, 2020.
The factorisation of RSA-250 utilised approximately 2700 CPU core-years, using a 2.1 GHz Intel Xeon Gold 6130 CPU as a reference. The computation was performed with the Number Field Sieve algorithm, using the open source CADO-NFS software.
The team dedicated the computation to Peter Montgomery, an American mathematician known for his contributions to computational number theory and cryptography who died on February 18, 2020, and had contributed to factoring RSA-768.
RSA-260
RSA-260 has 260 decimal digits (862 bits), and has not been factored so far.
RSA-270
RSA-270 has 270 decimal digits (895 bits), and has not been factored so far.
RSA-896
RSA-896 has 270 decimal digits (896 bits), and has not been factored so far. A cash prize of $75,000 was previously offered for a successful factorization.
RSA-280
RSA-280 has 280 decimal digits (928 bits), and has not been factored so far.
RSA-290
RSA-290 has 290 decimal digits (962 bits), and has not been factored so far.
RSA-300
RSA-300 has 300 decimal digits (995 bits), and has not been factored so far.
RSA-309
RSA-309 has 309 decimal digits (1,024 bits), and has not been factored so far.
RSA-1024
RSA-1024 has 309 decimal digits (1,024 bits), and has not been factored so far. $100,000 was previously offered for factorization.
RSA-310
RSA-310 has 310 decimal digits (1,028 bits), and has not been factored so far.
RSA-320
RSA-320 has 320 decimal digits (1,061 bits), and has not been factored so far.
RSA-330
RSA-330 has 330 decimal digits (1,094 bits), and has not been factored so far.
RSA-340
RSA-340 has 340 decimal digits (1,128 bits), and has not been factored so far.
RSA-350
RSA-350 has 350 decimal digits (1,161 bits), and has not been factored so far.
RSA-360
RSA-360 has 360 decimal digits (1,194 bits), and has not been factored so far.
RSA-370
RSA-370 has 370 decimal digits (1,227 bits), and has not been factored so far.
RSA-380
RSA-380 has 380 decimal digits (1,261 bits), and has not been factored so far.
RSA-390
RSA-390 has 390 decimal digits (1,294 bits), and has not been factored so far.
RSA-400
RSA-400 has 400 decimal digits (1,327 bits), and has not been factored so far.
RSA-410
RSA-410 has 410 decimal digits (1,360 bits), and has not been factored so far.
RSA-420
RSA-420 has 420 decimal digits (1,393 bits), and has not been factored so far.
RSA-430
RSA-430 has 430 decimal digits (1,427 bits), and has not been factored so far.
RSA-440
RSA-440 has 440 decimal digits (1,460 bits), and has not been factored so far.
RSA-450
RSA-450 has 450 decimal digits (1,493 bits), and has not been factored so far.
RSA-460
RSA-460 has 460 decimal digits (1,526 bits), and has not been factored so far.
RSA-1536
RSA-1536 has 463 decimal digits (1,536 bits), and has not been factored so far. $150,000 was previously offered for successful factorization.
RSA-470
RSA-470 has 470 decimal digits (1,559 bits), and has not been factored so far.
RSA-480
RSA-480 has 480 decimal digits (1,593 bits), and has not been factored so far.
RSA-490
RSA-490 has 490 decimal digits (1,626 bits), and has not been factored so far.
RSA-500
RSA-500 has 500 decimal digits (1,659 bits) and has not been factored so far.
RSA-617
RSA-617 has 617 decimal digits (2,048 bits) and has not been factored so far.
RSA-2048
RSA-2048 has 617 decimal digits (2,048 bits). It is the largest of the RSA numbers and carried the largest cash prize for its factorization, $200,000.
See also
- Integer factorization records
- RSA Factoring Challenge (includes table with size and status of all numbers)
- RSA Secret-Key Challenge
Notes
- RSA Factoring Challenge Administrator (1997-10-12),
- RSA Laboratories, (archived by the Internet Archive in 2006, before the RSA challenge ended)
- RSA Laboratories, . Archived from on May 21, 2013.
- Kazumaro Aoki, Yuji Kida, Takeshi Shimoyama, Hiroki Ueda, , Cryptology ePrint Archive, Report 2004/095, 2004
External links
- Steven Levy (March 1996), in Wired News. coverage on RSA-129