mersenneforum.org RSA cracked by SVP algorithms? (claim is disputed)
 Register FAQ Search Today's Posts Mark Forums Read

 2021-03-08, 01:28 #12 Drdmitry     Nov 2011 4108 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-03-08, 05:15   #13
jwaltos

Apr 2012

1100101102 Posts

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.

Last fiddled with by Dr Sardonicus on 2021-03-08 at 12:52 Reason: Correct attribution

 2021-03-08, 05:43 #14 jwaltos     Apr 2012 Gracie on alert. 6268 Posts Here's the sketch I was thinking of: Attached Thumbnails
2021-07-09, 20:31   #15
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

630210 Posts
Fast Factoring Integers by SVP Algorithms

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

2021-07-09, 21:14   #16
paulunderwood

Sep 2002
Database er0rr

1111010111102 Posts

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.

 2021-07-09, 21:18 #17 RomanM   Jun 2021 2916 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
2021-07-09, 21:22   #18
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

11000100111102 Posts

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.

 2021-07-09, 22:02 #19 charybdis     Apr 2020 22216 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post dans Hardware 3 2010-12-02 02:23 bearnol Miscellaneous Math 58 2010-09-05 17:48 Mindnar Lounge 28 2008-08-27 16:22 bearnol Miscellaneous Math 2 2006-08-12 09:17 Jeff Gilchrist Math 1 2005-03-24 02:31

All times are UTC. The time now is 02:20.

Fri Dec 3 02:20:16 UTC 2021 up 132 days, 20:49, 0 users, load averages: 0.92, 0.96, 0.96