[Cado-nfs-discuss] 795-bit factoring and discrete logarithms

Dear cado-nfs-discuss subscribers,


We are pleased to announce the factorization of RSA-240, from RSA's challenge
list, and the computation of a discrete logarithm of the same size (795 bits):

RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099
        = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517
        * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447

Let p = RSA-240 + 49204 be the first safe prime above RSA-240. We chose
as a target the encoding of the sentence "The magic words are still
Squeamish Ossifrage" (in reference to the factorization of RSA-129 [1]):

target_str="The magic words are still Squeamish Ossifrage"
target_hex=`echo -n $target_str | xxd -p -c 256`
target_hex=${target_hex^^}
target=`echo "ibase=16; $target_hex" | BC_LINE_LENGTH=0 bc`

target = 774356626343973985966622216006087686926705588649958206166317147722421706101723470351970238538755049093424997

we have with generator g = 5:

log(target) = 92603135928144195363094955331732855502961099191437611616729420475898744562365366788100548099072093487548258752802923326447367244150096121629264809207598195062213366889859186681126928982506005127728321426751244111412371767375547225045851716

which can be checked with 5^926...716 = target mod p.

The previous records were RSA-768 (768 bits) in December 2009 [2], and
a 768-bit prime discrete logarithm in June 2016 [3].

It is the first time that two records for integer factorization and discrete
logarithm are broken together, moreover with the same hardware and software.

Both computations were performed with the Number Field Sieve algorithm,
using the open-source CADO-NFS software [4].

The sum of the computation time for both records is roughly 4000
core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz).
A rough breakdown of the time spent in the main computation steps is as
follows.
    RSA-240 sieving:  800 physical core-years
    RSA-240 matrix:   100 physical core-years
    DLP-240 sieving: 2400 physical core-years
    DLP-240 matrix:   700 physical core-years

The computation times above are well below the time that was spent with
the previous 768-bit records. To measure how much of this can be
attributed to Moore's law, we ran our software on machines that are
identical to those cited in the 768-bit DLP computation [3], and reach
the conclusion that sieving for our new record size on these old machines
would have taken 25% less time than the reported sieving time of the
768-bit DLP computation.

Another estimation can be made with the rough complexity ratio given by
the L_N(1/3,(64/9)^(1/3)) formula that, up to (1+o(1)) factors in the
exponent, is customarily taken as an estimation of the expected hardness
increase from one computation to the next. This would suggest that
795-bit computations should be 2.25 times harder than 768-bit
computations. Taking this into account, and still using identical
hardware, our computation was 3 times faster than the expected time that
would have been extrapolated from previous records.

The acceleration can be attributed to various algorithmic improvements
that were implemented for these computations.  The CADO-NFS
implementation was also vastly improved.

We used computer resources of the Grid'5000 experimental testbed in
France (INRIA, CNRS, and partner institutions) [5], of the EXPLOR
computing center at Université de Lorraine, Nancy, France [6], an
allocation of computing hours on the PRACE research infrastructure using
resources at the Juelich supercomputing center in Germany [7], as well as
computer equipment gifted by Cisco Systems, Inc. to the University of
Pennsylvania.

More details will be given in a forthcoming scientific publication.

Fabrice Boudot, Éducation Nationale and Université de Limoges, France
Pierrick Gaudry, CNRS, Nancy, France
Aurore Guillevic, INRIA, Nancy, France
Nadia Heninger, University of Pennsylvania and University of California, San Diego, United States
Emmanuel Thomé, INRIA, Nancy, France
Paul Zimmermann, INRIA, Nancy, France