### Re: Significance of Schnorr's Factoring Integers in Polynomial Time?

I have three brief comments.

1) The main theorem assumes that we can find a vector of length
≤ \sqrt{2eπ} n^b λ_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
is eliminated by rd(L).

3) GSA does not hold in general. So, even if everything else checks out, the
argument might break down here.

We need to see the full result to say more. But in the meantime, let's not be
afraid ;-)

Cheers,
Markus

Am Montag, 11. Mai 2009 16:47:36 schrieb Ralf-Philipp Weinmann:

-RPW
-- Forwarded message --
From: Francois Grieu fgr...@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

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?

Francois Grieu

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com

--
Markus Rückert

Looking for a challenge?
- http://www.latticechallenge.org

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com



### Significance of Schnorr's Factoring Integers in Polynomial Time?

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