整数分解的世界纪录
https://members.loria.fr/PZimmermann/records/factor.htmlInteger Factoring Records
See also the nice FactorWorld page from Scott Contini, and that of Paul Leyland.
General-purpose Algorithms: the largest integer factored with a general-purpose algorithm is RSA768 (232 decimal digits), which was factored on December 12, 2009, by Kleinjung, Aoki, Franke, Lenstra, Thomé, Bos, Gaudry, Kruppa, Montgomery, Osvik, te Riele, Timofeev and Zimmermann.
The previous record was RSA200 (200 digits), which was factored on May 9, 2005 by Bahr, Boehm, Franke and Kleinjung.
The previous record was 11281+1 (176 digits), which was factored on May 2nd, 2005 by Aoki, Kida, Shimoyama and Ueda.
The previous record was RSA-576 (174 digits), which was factored on December 3rd, 2003 into two 87-digit factors using GNFS by Franke, Kleinjung, Montgomery, te Riele, Bahr, Leclair, Leyland, Wackerbarth.
.
ECM. The largest factor found by the Elliptic Curve method has 83 digits, found by Ryan Propper on September 8, 2013.
The previous record had 79 digits, found by Sam Wagstaff on August 12, 2012.
The previous record had 75 digits, found by Sam Wagstaff on August 2, 2012.
The previous record had 73 digits, found by J. Bos, T. Kleinjung, A. Lenstra, P. Montgomery on March 6, 2010.
The previous record had 68 digits, found by yoyo@home/M. Thompson on December 28, 2009.
The previous record had 67 digits, found by B. Dodson on August 24, 2006.
.
Using Hardware. The very first GNFS factorization using hardware is that of 7352+1 c128 done by a Fujitsu LTD group headed by Shimoyama Takeshi.
Special Numbers. With the special number field sieve, the record is 320 digits, with 21061-1, factored by NFS@home on August 4, 2012 (report). The previous record was 313 digits, with 21039-1, factored by Aoki, Franke, Kleinjung, Lenstra and Osvik on May 21, 2007 (report). The previous record was 274 digits, with (6353-1)/5 factored by Aoki/Kida/Shimoyama/Ueda on January 23, 2006.
Free implementations. Jens Franke has an implementation of PPMPQS. Another implementation for the discrete logarithm problem is due to Chris Studholme. Jason Papadopoulos's MSIEVE is claimed to be "faster than any other code implementing any other algorithm [...] for completely factoring general inputs between 40 and 100 digits", but Ben Buhrow's YAFU is a new challenger. For NFS, the following implementations exist:
GGNFS, developed by Chris Monico (also on SourceForge),
MSIEVE, developed by Jason Papadopoulos,
CADO-NFS, developed by Emmanuel Thomé, Lionel Muller, Alexander Kruppa, Pierrick Gaudry, Franĉois Morain, Jérémie Detrey and Paul Zimmermann.
Test Numbers: try your favorite factoring algorithm or implementation on these numbers. 椭圆曲线分解的大整数因子纪录
https://members.loria.fr/PZimmermann/records/top50.html https://members.loria.fr/PZimmermann/records/rsa.html
这人有意思，让别人用RSA的办法与他交流，推荐分解算法
Once you have solved the above challenges, to really convince me you have found an efficient factoring algorithm, please do the following:
pick up a large unfactored publicly known integer, say N (RSA-1024 should be enough to convince me and many other people);
from the factorization N=pq you have, deduce the private key d = 1/e mod (p-1)(q-1) corresponding to the public key e=65537;
compute c = 3d mod N;
send the integer c to me (or publish it on some web page);
on my side, I will compute m = c65537 mod N and check that m=3.
This algorithm is secure for both you and me:
you cannot cheat since for that you need to extract an e-th root of N; this is known as the RSA problem;
I cannot deduce the factorization of N from the value of c.
Thanks to my colleagues Guillaume Hanrot, Pierrick Gaudry and Emmanuel Thomé, who helped me improving this page. 他网页上的
rsa-59 = 71641520761751435455133616475667090434063332228247871795429
=20042 92181 20815 55426 97436 35437 × 35744 05041 01388 36561 07853 89017
rsa-79 =7293469445285646172092483905177589838606665884410340391954917800303813280275279
=848184382919488993608481009313734808977<39> * 8598919753958678882400042972133646037727<40>
rsa-99 = 256724393281137036243618548169692747168133997830674574560564321074494892576105743931776484232708881
=4868376167980921239824329271069101142472222111193<49> · 52733064254484107837300974402288603361507691060217<50>
rsa-119 = 55519750778717908277109380212290093527311630068956900635648324635249028602517209502369255464843035183207399415841257091
=106582741029862212583249815536611312249501518146343497063387*
520907515065337429500108915077818773621294300970429704758393
页:
[1]