mersenneforum.org RSA-250
 Register FAQ Search Today's Posts Mark Forums Read

2020-02-28, 16:16   #1
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41·229 Posts
RSA-250

via NMBRTHRY list

Quote:
 Date: February 28, 2020 For the past three months, ever since the DLP-240 record announced in December 2019 [1], we have been in a historically unique state of affairs: the discrete logarithm record (in a prime field) has been larger than the integer factorization record. We are pleased to rectify this situation with the factorization of RSA-250 from the RSA challenge list: Code: RSA-250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937 = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367 * 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711 This computation was performed with the Number Field Sieve algorithm, using the open-source CADO-NFS software [2]. The total computation time was roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz): RSA-250 sieving: 2450 physical core-years RSA-250 matrix: 250 physical core-years Here are the factors of p+/-1 and q+/-1: p-1 = 2 * 6213239 * 101910617047160921359 * 4597395223158209096147 * p77 p+1 = 2^3 * 3 * 7 * 223 * 587131 * 6071858568668069951281 * p93 q-1 = 2 * 5 * 13 * 440117350342384303 * 8015381692860102796237 * p83 q+1 = 2^3 * 3^3 * 23 * 2531 * 11171 * 2100953 * p108 We used computer resources of the Grid'5000 experimental testbed in France (INRIA, CNRS, and partner institutions) [3], of the EXPLOR computing center at Universite de Lorraine, Nancy, France [4], an allocation of computing hours on the PRACE research infrastructure using resources at the Juelich supercomputing center in Germany [5], as well as computer equipment gifted by Cisco Systems, Inc. at UCSD. We would like to dedicate this computation to Peter L. Montgomery, who passed away on February 18, 2020. Fabrice Boudot, Education Nationale and Universite de Limoges, France Pierrick Gaudry, CNRS, Nancy, France Aurore Guillevic, INRIA, Nancy, France Nadia Heninger, University of California, San Diego, United States Emmanuel Thome, INRIA, Nancy, France Paul Zimmermann, INRIA, Nancy, France [1] https://caramba.loria.fr/dlp240-rsa240.txt [2] http://cado-nfs.gforge.inria.fr/ [3] https://www.grid5000.fr [4] http://explor.univ-lorraine.fr/ [5] http://www.prace-ri.eu/prace-in-a-few-words/

 2020-03-06, 08:41 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 222318 Posts Yay! Nice work.
 2020-03-06, 14:26 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 13×491 Posts So it's still a factor three more runtime for ten more digits at the 240-digit level; interesting to know. Maybe slightly lower for the linear algebra. (800/100 X6130-core-years for RSA240; 2450/250 for RSA250) Grid5000 is now at 15k CPU cores, so it would take a large chunk of it to do RSA260; on the other hand there is a 2048-core chunk at INRIA which might conceivably be used 24/7 for 700 core-years of linear algebra. 1.5 million core-years still feels acceptably out of reach for the casual factorisation of RSA1024
2020-03-10, 19:27   #4
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by fivemack So it's still a factor three more runtime for ten more digits at the 240-digit level; interesting to know. Maybe slightly lower for the linear algebra. (800/100 X6130-core-years for RSA240; 2450/250 for RSA250) Grid5000 is now at 15k CPU cores, so it would take a large chunk of it to do RSA260; on the other hand there is a 2048-core chunk at INRIA which might conceivably be used 24/7 for 700 core-years of linear algebra. 1.5 million core-years still feels acceptably out of reach for the casual factorisation of RSA1024
Not to mention the (approx) petabyte DRAM needed for the LA.