Concluding RemarksFactoring 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
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:
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?
AcknowledgementsFirst 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 :)
|