RSA cracked by SVP algorithms? (claim is disputed) - Page 2

Drdmitry · 2021-03-08, 01:28

I tried to look into the paper I found that it looks more like a draft rather than a finalised paper.
Firstly, after the first submission on 1st of March, a revised version was submitted on 3rd of March. These two versions are drastically different.
Secondly, the last version contains too many mistakes (perhaps, not crucial, but it is hard to tell). For example, the matrix $\mathbf{R}_{n,f}$ on page 2 should definitely be different, otherwise all the arguments in Section 3 are false. I guess that the matrix should have terms $\mathrm{ln} p_i$ on the main diagonal and the last row should contain terms $N\mathrm{ln}p_{f(i)}$ . But I am not sure.

After reading the paper, I am skeptical that Schnorr indeed provides a breakthrough factoring algorithm but who knows...

jwaltos · 2021-03-08, 05:15

Quote:

Originally Posted by ThiloHarich

Somebody tried to implement it
https://github.com/lducas/SchnorrGate

Thanks for posting this. I'm aware of one of the people named in the acknowledgements, Curtis Bright (who studied under J. Shallit). As I recall, Bright found an interesting partial solution in one of Shallit's open problems within a particular course. The links provided within the github site are also spot on..even Sage has its uses.

The one thing that bugs me about this whole thing are statements like .. "But who knows?".." but who knows.... ." Bullshit! Papers aren't supposed to be presented in the form of "abstracted" or obfuscated code where you need to puzzle your way through a labyrinth of jargon (however well anyone is versed within that "code"). If something isn't "Euler" clear [literally and/or figuratively] within number theoretic expositions then something's wrong. I'd like to interpose a comic sketch by ~~Gary Larson~~ Sidney Harris here but the attachment link isn't visible. Perhaps if the name Schnorr wasn't associated with this paper and the author listed himself as "Student-T, anonymous ..etc..) that these papers would have received an appropriate critique/review rather than the kowtowing displayed.

jwaltos · 2021-03-08, 05:43

Here's the sketch I was thinking of:

retina · 2021-07-09, 20:31

https://eprint.iacr.org/2021/933

Quote:

... much faster then the quadratic sieve and the number field sieve and using much smaller primes $p_n$. This destroys the RSA cryptosystem.

I'll put this in Misc. Math for the time being, and move later if appropriate.

Quote:

Contact author: schnorr at cs uni-frankfurt de

paulunderwood · 2021-07-09, 21:14

Quote:

Originally Posted by retina

https://eprint.iacr.org/2021/933 I'll put this in Misc. Math for the time being, and move later if appropriate.

An update to https://mersenneforum.org/showthread.php?t=26557 I suppose.

RomanM · 2021-07-09, 21:18

Too many of Extremely Clever Math words and no tiny sample i.e. factoring of 2^128-1... or at least O() notation) RSA is dead for sure, its only matter of time, but i guess, not today.

retina · 2021-07-09, 21:22

Quote:

Originally Posted by paulunderwood

An update to https://mersenneforum.org/showthread.php?t=26557 I suppose.

Thanks. That seems appropriate. So now moved as promised.

charybdis · 2021-07-09, 22:02

I think the only change to the previous version of the paper, which Schnorr withdrew in June, is to Lemma 3.1 on page 3. As detailed here, this lemma does not prove what Schnorr wanted to prove, due to confusion between N (the number to be factored) and the much smaller N'.

Schnorr has seemingly "fixed" this by changing the statement of the lemma to use N rather than N'. But the proof still uses N', so now instead of drawing false conclusions from a lemma we've just got a false lemma.

2021-03-08, 05:43	#14
jwaltos Apr 2012 Brady 2⁷×3 Posts	Here's the sketch I was thinking of: Attached Thumbnails

2021-07-09, 21:18	#17
RomanM Jun 2021 15₁₀ Posts	Too many of Extremely Clever Math words and no tiny sample i.e. factoring of 2^128-1... or at least O() notation) RSA is dead for sure, its only matter of time, but i guess, not today. Last fiddled with by RomanM on 2021-07-09 at 21:21

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

2021-03-08, 01:28	#12
Drdmitry Nov 2011 3×83 Posts	I tried to look into the paper I found that it looks more like a draft rather than a finalised paper. Firstly, after the first submission on 1st of March, a revised version was submitted on 3rd of March. These two versions are drastically different. Secondly, the last version contains too many mistakes (perhaps, not crucial, but it is hard to tell). For example, the matrix $\mathbf{R}_{n,f}$ on page 2 should definitely be different, otherwise all the arguments in Section 3 are false. I guess that the matrix should have terms $\mathrm{ln} p_i$ on the main diagonal and the last row should contain terms $N\mathrm{ln}p_{f(i)}$ . But I am not sure. After reading the paper, I am skeptical that Schnorr indeed provides a breakthrough factoring algorithm but who knows...

2021-07-09, 22:02	#19
charybdis Apr 2020 11×31 Posts	I think the only change to the previous version of the paper, which Schnorr withdrew in June, is to Lemma 3.1 on page 3. As detailed here, this lemma does not prove what Schnorr wanted to prove, due to confusion between N (the number to be factored) and the much smaller N'. Schnorr has seemingly "fixed" this by changing the statement of the lemma to use N rather than N'. But the proof still uses N', so now instead of drawing false conclusions from a lemma we've just got a false lemma.