SchnorrGate

Testing Schnorr's factoring Claim in SageMath [Sage]

[Sch21]
Fast Factoring Integers by SVP Algorithms
Claus Peter Schnorr
https://eprint.iacr.org/2021/232

Note: This follows the version of March 3, not the one of March 1. This version is much easier to implement with existing lattice reduction software, as it only requires solving SVP in dimension 48 for a 400 bits number to be factored (the previous version mentioned dimensions unreachable by currently known techniques).

Command Line Interface

sage fac.sage b n t

where b is the bit-size of the number to be factored, n the number of elements in the factor basis, and t the number of trials. Passing no parameters or invalid integers will results in default values b=400, n=47, t=100 following the claim of Schnorr.

Experimental results (modulo implementation mistakes): Running b=400, n=47, t=1000, we obtained 0 Factoring Relation found out of 1000 trials. Closer inspection of typical shortest showed that the vector e is typically very sparse, say a single 1 and a single -1.

Running b=10, n=47, t=1000, we obtained 353 Factoring Relation found out of 1000 trials.
Running b=20, n=47, t=1000, we obtained 65 Factoring Relation found out of 1000 trials.
Running b=40, n=47, t=1000, we obtained 0 Factoring Relation found out of 1000 trials.

This suggest that the approach may be sensible, but that not all short vectors give rise to factoring relations, and that obtaining a sufficient success rate requires much larger lattice dimension than claimed in [Sch21]. This corroborates various counter-analysis of the lattice volume computation.

Personal study (unfortunately, never written down cleanly) of this approach suggested me that this approach requires solving SVP in dimensions beyond reasonable, leading to a factorization algorithm much slower than the state of the art. My impression is that this is the consensus among experts having spent some time on it as well.

History and Related works

I wish to recall that this claim of polynomial time factoring is not particularly new: it was announced at Eurocrypt 2009 [Sch09]. This claim has so far not been published at a peer-reviewed conference or journal.

The approach itself is even older, dating from 1991, already from Schnorr [Sch91] (Schnorr even makes mention of an article of Brillhard and Morrison [MB75]). It has been very influential (and hence, seriously explored, e.g. [Ver10]), but successful applications are in fact outside the realm of factoring. It is an inspiring serendipity story.

The particular construction of lattice was further explored by Adleman [Adl95], attempting to prove that some lattice problems (SVP, the Shortest Vector Problem) are at least as hard as factoring. Ajtai [Ajt98], while attempting to complete the initial goal of Adleman, instead found a proof of a much stronger statement: namely that SVP is NP-hard.

This construction made other appearances, for example in relation to the abc conjecture [Bri14]. A variant over number fields is also central to some recent study of reduction algorithm for module lattices [LPSW19].

Another interesting variant of this lattice construction is the following: replace real logarithm by discrete logarithm. Chor and Rivest constructed a cryptosystem based on such lattices [CR88]. Stripping out all the crypto, and studying asymptotic, Cecile Pierrot and I [DP18] reinterpreted their algorithm as a lattice decoding algorithm (BDD). It is based on the reciprocal of Schnorr's idea, namely use an easy factoring instance to solve lattice problems.

Acknowledgments: There is not much work behind the script itself. Most of the credit for this implementation goes to SageMath [Sage] developers and maintainers, and to the FPLLL team [fplll] for the underlying lattice reduction software. I'm also grateful to Daniele Micciancio, Curtis Bright, Damien Stehle, and Dima Pasechnik, for precious comments and references. We should also thank Len Adleman for sharing his draft [Adl95].

References

[CR88]
A knapsack-type public key cryptosystem based on arithmetic in finite fields
B. Chor, R.L. Rivest
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.9452&rep=rep1&type=pdf

[MB75]
A method of factoring and the factorization of F7
J. Brillhart, MA Morrison
Math. Comp, 1975.

[Sch91]
Factoring integers and computing discrete logarithms via diophantine approximation
C. P. Schnorr
https://link.springer.com/chapter/10.1007/3-540-46416-6_24

[Adl95]
Factoring and Lattice Reduction
L. Adleman
https://raw.githubusercontent.com/lducas/SchnorrGate/main/LATFAC.pdf

[Ajt98]
The shortest vector problem in L2 is NP-hard for randomized reductions
M. Ajtai
https://dl.acm.org/doi/pdf/10.1145/276698.276705

[Sch09]
Average Time Fast SVP and CVP Algorithms: Factoring Integers in Polynomial Time
C. P. Schnorr
https://eurocrypt2009rump.cr.yp.to/e074d37e10ad1ad227200ea7ba36cf73.pdf

[Ver10]
A note on integer factorization using lattices
A. Vera
https://arxiv.org/pdf/1003.5461.pdf

[Bri14]
Extremal examples in the abc conjecture
C. Bright
https://cs.uwaterloo.ca/~cbright/talks/pmath944-talk.pdf

[DP18]
Polynomial Time Bounded Distance Decoding near Minkowski’s Bound in Discrete Logarithm Lattices
L. Ducas and C. Pierrot
https://eprint.iacr.org/2018/146

[LPSW19]
An LLL algorithm for module lattices
C. Lee, A. Pellet-Mary, D. Stehlé, and A. Wallet
https://eprint.iacr.org/2019/1035

[Sage]
SageMath, the Sage Mathematics Software System (Version 9.0.0)
The Sage Developers
https://www.sagemath.org

[fplll]
FPLLL, a lattice reduction library
The FPLLL development team
https://www.sagemath.org

Acknowledgments

This work was supported by the European Union Horizon 2020 Research and Innovation Program Grant 780701 (PROMETHEUS).