RSA Factoring Challenge

The RSA Factoring Challenge is a challenge put forward by RSA Laboratories on March 18 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers. They published a list of semiprimes (numbers with exactly two prime factors) known as the RSA numbers, with a cash prize for the successful factorization of some of them. The smallest of them, a 100 decimal digit number called RSA-100 was factored in a few days, but many of the bigger numbers have still not been factored and are expected to remain so for quite some time.

This challenge is intended to track the state of the art in integer factorisation. A primary application is for choosing the key length of the RSA public-key encryption scheme. Progress in this challenge should give an insight into which key sizes are still safe and for how long. As RSA Laboratories is a provider of RSA-based products, the challenge is used by them as an incentive for the academic community to attack the core of their solutions — in order to prove its strength.

The first RSA numbers generated, from RSA-100 to RSA-500, were labeled according to their number of decimal digits; later, however, beginning with RSA-576, binary digits are counted instead. An exception to this is RSA-617, which was created prior to the change in the numbering scheme.

Contents

The mathematics

Let n be a RSA Number. There are prime numbers p and q such that

<math>n=pq.<math>

The problem is to find these two primes, given only n.

Let s be <math>p+q<math>; then the values of some basic arithmetic functions are

<math>d(n) = 2<math>
<math>\phi(n)=(p-1)(q-1) = n + 1 - s<math>
<math>\sigma(n)=(p+1)(q+1) = n + 1 + s.<math>

The prizes and records

The following table gives an overview over all RSA numbers.

The challenge numbers in pink lines are numbers expressed in base 10, while the challenge numbers in orange lines are numbers expressed in base 2, and for which a cash prize is still assigned.
RSA Number Decimal digits Binary digits Cash prize offered Factored on Factored by
RSA-100 100 330   April 1991  
RSA-110 110 364   April 1992  
RSA-120 120 397   June 1993  
RSA-129 129 426 $100 USD April 1994 Arjen K. Lenstra et al.
RSA-130 130 430   April 10 1996 Arjen K. Lenstra et al.
RSA-140 140 463   February 2 1999 Herman J. J. te Riele et al.
RSA-150 150 496   withdrawn but factored in 2004
RSA-155 155 512   August 22 1999 Herman J. J. te Riele et al.
RSA-160 160 530   April 1 2003 Jens Franke et al., University of Bonn
RSA-170 170 563   open
RSA-576 174 576 $10,000 USD December 3, 2003 Jens Franke et al., University of Bonn
RSA-180 180 596   open
RSA-190 190 629   open
RSA-640 193 640 $20,000 USD open
RSA-200 200 663   May 9 2005 Jens Franke et al., University of Bonn
RSA-210 210 696   open
RSA-704 212 704 $30,000 USD open
RSA-220 220 729   open
RSA-230 230 762   open
RSA-232 232 768   open
RSA-768 232 768 $50,000 USD open
RSA-240 240 795   open
RSA-250 250 829   open
RSA-260 260 862   open
RSA-270 270 895   open
RSA-896 270 896 $75,000 USD open
RSA-280 280 928   open
RSA-290 290 962   open
RSA-300 300 995   open
RSA-309 309 1024   open
RSA-1024 309 1024 $100,000 USD open
RSA-310 310 1028   open
RSA-320 320 1061   open
RSA-330 330 1094   open
RSA-340 340 1128   open
RSA-350 350 1161   open
RSA-360 360 1194   open
RSA-370 370 1227   open
RSA-380 380 1261   open
RSA-390 390 1294   open
RSA-400 400 1327   open
RSA-410 410 1360   open
RSA-420 420 1393   open
RSA-430 430 1427   open
RSA-440 440 1460   open
RSA-450 450 1493   open
RSA-460 460 1526   open
RSA-1536 463 1536 $150,000 USD open
RSA-470 470 1559   open
RSA-480 480 1593   open
RSA-490 490 1626   open
RSA-500 500 1659   open
RSA-617 617 2048   open
RSA-2048 617 2048 $200,000 USD open

See also

External links

Navigation

  • Art and Cultures
    • Art (https://academickids.com/encyclopedia/index.php/Art)
    • Architecture (https://academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (https://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (https://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools