[Cado-nfs-discuss] Factorization of RSA-250

paul zimmermann Paul.Zimmermann at inria.fr
Fri Feb 28 16:48:03 CET 2020


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:

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 Université 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, Éducation Nationale and Université de Limoges, France
Pierrick Gaudry, CNRS, Nancy, France
Aurore Guillevic, INRIA, Nancy, France
Nadia Heninger, University of California, San Diego, United States
Emmanuel Thomé, 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/



More information about the Cado-nfs-discuss mailing list