Go Back > Factoring Projects > Factoring

Thread Tools
Old 2021-03-03, 06:44   #1
kubus's Avatar
May 2003

3·5 Posts
Default RSA cracked by SVP algorithms? (claim is disputed)

Claus Peter Schnorr just posted a paper in which he claims to have broken RSA. Has anyone looked into it?
Fast Factoring Integers by SVP Algorithms
kubus is offline   Reply With Quote
Old 2021-03-03, 15:00   #2
ccorn's Avatar
Apr 2010

5·31 Posts

Better look at the more recent draft. I do not consider it likely that Schnorr himself would have posted such an outdated (and apparently haphazardly edited) version.
ccorn is offline   Reply With Quote
Old 2021-03-03, 15:21   #3
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

2×17×47 Posts

An early slide from him:

Forums about these claims:
R. Gerbicz is offline   Reply With Quote
Old 2021-03-03, 17:25   #4
xilman's Avatar
May 2003
Down not across

3×17×227 Posts

Someone whom I respect greatly told me that he had received that information from several others to whom it was new, including me.

His view is that it is unlikely to pan out in reality any time soon, being yet another elaboration of one of Schnorr's ideas.

But who knows?
xilman is offline   Reply With Quote
Old 2021-03-03, 17:29   #5
ccorn's Avatar
Apr 2010

15510 Posts

Here is my superficial impression, gathered from the PDFs linked at the university's lattice algorithms course page. I might be wrong. Better consult the linked resources directly.

There is a known construction of a close-enough-lattice-vector problem that helps generate smooth integers \(u\) and \(v\) such that \(u/v\) is close to the to-be-factored integer \(N\). Then \(|u-vN|\) is (relatively) small and, if smooth, gives rise to a relation mod \(N\). Enough such relations can be combined in the usual way, using linear algebra over GF(2) on the exponent vectors, to construct congruent squares mod \(N\), which are then used to find a (probably nontrivial) factor of \(N\).

I find it worth remarking that the method does not require proven shortest or closest lattice vectors to be found; in fact it needs to find and examine several close-enough lattice vectors in order to gather enough relations. It does so by looking at many (but not too many) enumerated lattice vectors and by tweaking the lattice.
Thus, keywords like SVP or CVP are a bit misleading; their presence is justified merely by the fact that algorithms for those problems have been adapted to solve a related problem.
Anyway, the factor base size and thus the number of relations needed are claimed to be far lower than for typical NFS scenarios. The crux is then to do the close-vectors search efficiently.

Over the last decade, progress has been made in the lattice methods used, reducing the computational effort per relation found. The latest version of the method is claimed to use far less arithmetic operations than QS or NFS for 400-bit and 800-bit numbers. The abstract says that that means "much faster", but the body text cautions that the bit length of the operands is much larger. If I interpret that correctly, this means that the number of machine-word arithmetic operations is not something to brag about yet.
In any case, I'd like to see the method demonstrated with a solution to some \(n\)-bit factorization challenge with \(n\) between 400 and 800.

There is also a polynomial-complexity claim, but that seems to refer to the part that finds close-enough lattice vectors, subject to some assumptions. If I am not mistaken, that estimate does not cover the smoothness filter that produces relations, so there might still be a more-than-polynomial slowdown (which I consider likely as Dickman's rho function will have a say there).
ccorn is offline   Reply With Quote
Old 2021-03-03, 19:08   #6
CRGreathouse's Avatar
Aug 2006

10111011000112 Posts

I think it's really exciting to see someone trying (slightly) new things in this space -- since the 90s all we've been doing is tweaking the number field sieve. But he's pretty straightforward about the benefits, as corn points put above:

The number of arithmetic steps of our factorisation is quite small compared with QS and NFS factorisation but the bit length of integers is large.
That is, there's no claim that the number of bit operations stays the same let alone decreases. So I think this is better thought of as a jumping-off point for research than as a useable method. But who knows, I could be wrong! Maybe a careful implementation could beat other algorithms in some ranges, perhaps even in a neighborhood including \infty.

Last fiddled with by CRGreathouse on 2021-03-03 at 19:09
CRGreathouse is offline   Reply With Quote
Old 2021-03-03, 21:15   #7
6809 > 6502
Uncwilly's Avatar
Aug 2003
101ร—103 Posts

10,799 Posts

Originally Posted by xilman View Post
Someone whom I respect greatly
Uncwilly is offline   Reply With Quote
Old 2021-03-04, 15:20   #8
ThiloHarich's Avatar
Nov 2005

22·33 Posts

There is a german statement on
ThiloHarich is offline   Reply With Quote
Old 2021-03-05, 00:00   #9

6,197 Posts

Originally Posted by CRGreathouse View Post
.. since the 90s all we've been doing is tweaking the number field sieve..
No. We've not all been doing that, tweaking a sieving a process then "black-boxing" it..focusing on and optimizing black box processes.

Good thread with good links!

Last fiddled with by jwaltos on 2021-03-05 at 00:01
  Reply With Quote
Old 2021-03-05, 07:10   #10

3×7×53 Posts

Originally Posted by jwaltos View Post
Here's a link to some older papers. Perhaps some of these may help in correlating past results within the present paper. I'm trying to understand what the breakthrough is. I have some familiarity with
the subset sum problem, LLL and variants and computational complexity. Instead of clarity I'm navigating inscrutability. This paper and its antecedents remind me of some papers regarding the resolution of the abc conjecture by another distinguished professional, Shinichi Mochizuki.

Last fiddled with by jwaltos on 2021-03-05 at 07:22
  Reply With Quote
Old 2021-03-05, 09:46   #11
ThiloHarich's Avatar
Nov 2005

1548 Posts

Somebody tried to implement it
ThiloHarich is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
AMD hardware level debugger cracked dans Hardware 3 2010-12-02 02:23
EFF claim(s) bearnol Miscellaneous Math 58 2010-09-05 17:48
GIMPS may not claim $100,000 Mindnar Lounge 28 2008-08-27 16:22
ECDLP cracked mathematically acc. Bearnol bearnol Miscellaneous Math 2 2006-08-12 09:17
Ramanujan math puzzle cracked at last Jeff Gilchrist Math 1 2005-03-24 02:31

All times are UTC. The time now is 19:09.

Tue Nov 29 19:09:45 UTC 2022 up 103 days, 16:38, 0 users, load averages: 1.12, 0.99, 0.92

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”