Special Purpose Factoring Devices

   A journey from Bicycle to Quantum Computers

Computational Number Theory Project
Math 583e, University of Washington
Spring 2009

Concluding Remarks

Factoring integers: A mathematical sport turned into one of the biggest sought after problems in number theory. Let us take a look at the current standings and a brief timeline.

Using general purpose algorithms. Largest integer factored with a general-purpose algorithm is RSA-200 (200 digits), by Bahr, Boehm, Franke and Kleinjung in 2005.

Using Hardware. The very first GNFS factorization using hardware is that of 7352 + 1 done by a Fujitsu LTD group headed by Shimoyama Takeshi in 2006.

ECM. The largest factor found by the Elliptic Curve method has 67 digits, found by B. Dodson in 2006.

Special Numbers. With the special number field sieve, the record is 313 digits, with 21039-1, factored by Aoki, Franke, Kleinjung, Lenstra and Osvik in 2007.

 

Timeline till date

What Digits Who When
7141075053842 13 Carissan (Machine à Congruences) 1919
9999000099990001 16 Lehmer (Bicycle Sieve) 1926
293 + 1 28 Lehmer (Gear Sieve) 1932
RSA-129 129 600 volunteers all over the world (MPQS) 1994
RSA-130 130 Lenstra and group (GNFS) 1996
RSA-140 140 Montgomery, Leyland, Dodson, Zimmermann, Lenstra (GNFS) 1999
RSA-155 155 Muffet, Leyland, Montgomery, Dodson, Morain, Guillerm,Marchand, Lenstra, Zimmermann, Gilchrist, Aardal, Putnam (GNFS) 1999
2953+1 158 Bahr, Boehm, Franke, Kleinjung (GNFS) 2002
RSA-160 160 Bundesamt für Sicherheit in der Informationstechnik (BSI) Researchers (GNFS) 2002
RSA-576 174 Franke, Kleinjung, Montgomery, te Riele, Bahr, Leclair, Leyland, Wackerbarth (GNFS) 2003
11281+1 176 Aoki, Kida, Shimoyama and Ueda (GNFS) 2005
RSA-640 193 Bahr, Boehm, Franke, Kleinjung (GNFS) 2005
RSA-200 200 Bahr, Boehm, Franke, Kleinjung (GNFS) 2005

 

Goal. To factor the general RSA-1024 bit key (308 digits)

A lot of people think that RSA-1024 bit key is completely invulnerable to the current technology. It will be at stake only with the practical advent of quantum machines, which is not expected to happen in the near future. But if we consider the following facts:

  • We do not have any information about any new factoring algorithms, performance improvements or any SPDs since 2006-07.
  • We do not generally have access to the confidential information regarding government research in this field.
  • There exists some SPD proposals which are technologically viable, but requires a huge fund to build.
  • There are some proposals for SPDs which are cost effective for RSA-1024 but technologically advanced.
  • Last but not the least, we have Moore's law for technological advancement.
  • The funniest fact: RSA Challenge for RSA-704 (212 digits) and higher (including RSA-1024) have been cancelled and prize have been retracted.

Given these facts, and the incredibly fast progress in factoring as shown in the timeline, I think it is time to consider the special purpose devices improving the performance of NFS to be a threat to RSA-1024 keys. What do you think?

 

Acknowledgements

First and foremost, I will like to thank William Stein for offering the wonderful course in Computational Number Theory (583e) and William B. Hart for the awesome lectures on Number Field Sieve during the first half of Spring 2009. I would also like to thank all the researchers in the field of SPDs for factoring, whom I have referred to in this document and have gathered invaluable information from. My sincere thanks to everyone who contributes towards the Wikipedia to make it such a great bank of knowledge. Last but not the least, I should thank my 'special' general purpose device (my laptop) for supporting (and bearing) my typing for 20 hours straight. Lol :)

 

<< Prev: SPDs of Future Next: References >>