A recent paper, “Fast Factoring Integers by SVP Algorithms” by Claus P. Schnorr, claims significant improvements in factoring that “destroys the RSA cryptosystem”. If true, it would be practical to demonstrate on well known RSA factoring challenges.

No such demonstration has been made. Without this, assessing the correctness of the paper will have to wait for reviewers to wade through the details and give their feedback.

Image for postImage for postImage for post
Image for post

This paper drew the attention of mny cryptographers because Schnorr, notable for Schnorr signatures, is an accomplished cryptographer who has worked on factoring problems for at least a decade. There have been significant improvements in factoring over the last 20 years, so a big new result from a known researcher is at least plausible.

Initial misspellings and version inconsistencies led to speculation that the submission was a prank. However, the provenance of the paper has been confirmed: it is indeed Schnorr.

Schnorr’s paper claims to factor 400-bit moduli in 4.2·10⁹ operations and 800-bit moduli in 8.4·10¹⁰ operations. The 800-bit claims would be 36 bits of work.

That would be demonstrable on commodity hardware.

For comparison, the two most recent factoring records using CADO-NFS are:

The Crypto 2020 paper “Comparing the Difficulty of Factorization and Discrete Logarithm: a 240-digit Experiment” covers some of these results.

According to the claims in Schnorr’s paper, it should be practical to set significant new factoring records. There is a convenient 862-bit RSA challenge that has not been factored yet. Posting its factors, as done for the CADO-NFS team’s records, would lend credence to Schnorr’s paper and encourage more review of the methodology.