[144463] in cryptography@c2.net mail archive
Re: Significance of Schnorr's "Factoring Integers in Polynomial Time"?
daemon@ATHENA.MIT.EDU (Markus =?utf-8?q?R=C3=BCckert?=)
Thu May 21 17:27:57 2009
From: Markus =?utf-8?q?R=C3=BCckert?= <rueckert@cdc.informatik.tu-darmstadt.de>
To: cryptography@metzdowd.com
Date: Wed, 13 May 2009 14:11:17 +0200
In-Reply-To: <a2674a3d0905110747tc9c06f1m8d795262c6cfa14d@mail.gmail.com>
I have three brief comments.
1) The main theorem assumes that we can find a vector of length
=E2=89=A4 \sqrt{2e=CF=80} n^b =CE=BB_1
In general, this is not possible in polynomial time, esp. for small b.
2) NEW ENUM takes time exponential in n unless b is very small such that n^=
b=20
is eliminated by rd(L).
3) GSA does not hold in general. So, even if everything else checks out, th=
e=20
argument might break down here.
We need to see the full result to say more. But in the meantime, let's not =
be=20
afraid ;-)
Cheers,
Markus
Am Montag, 11. Mai 2009 16:47:36 schrieb Ralf-Philipp Weinmann:
>Wanna reply?
>-RPW
> ---------- Forwarded message ----------
> From: Francois Grieu <fgrieu@gmail.com>
> Date: Sun, May 10, 2009 at 3:29 PM
> Subject: Significance of Schnorr's "Factoring Integers in Polynomial Time=
"?
> To: cryptography@metzdowd.com
>
>
> At the rump session of Eurocrypt 2009,
> http://eurocrypt2009rump.cr.yp.to/
> Claus P. Schnorr reportedly presented slides titled "Average Time Fast
> SVP and CVP Algorithms: Factoring Integers in Polynomial Time"
> http://eurocrypt2009rump.cr.yp.to/e074d37e10ad1ad227200ea7ba36cf73.pdf
>
> I hardly understand 1/4 of the mathematical notation used, and can't
> even be sure that the thing is not a (very well done) prank.
>
> Anyone one the list dare make a comment / risk an opinion?
>
> =C2=A0Francois Grieu
>
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.c=
om
=2D-=20
Markus R=C3=BCckert
TU Darmstadt, Fachbereich Informatik
Hochschulstrasse 10, 64289 Darmstadt
Looking for a challenge?
=2D http://www.latticechallenge.org
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
