mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-02-28, 16:16   #1
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×43×71 Posts
Lightbulb 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/
Batalov is offline   Reply With Quote
Old 2020-03-06, 08:41   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×11×29 Posts
Default

Yay!
Nice work.
LaurV is offline   Reply With Quote
Old 2020-03-06, 14:26   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,323 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2020-03-10, 19:27   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 08:43.

Fri Nov 27 08:43:12 UTC 2020 up 78 days, 5:54, 4 users, load averages: 0.83, 1.18, 1.26

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.