Significance of Schnorr's "Factoring Integers in Polynomial Time"?
Francois Grieu
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 distinguish the thing from a
(very well done) prank.
Anyone dare risk a comment?
Francois Grieu
SG
> 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 distinguish the thing from a
> (very well done) prank.
>
> Anyone dare risk a comment?
I might be wrong (not my area of expertise) but I think these are the
steps that are involved:
1. Under some conditions SVP (shortest vector problem) can be solved
in polynomial time with respect to the dimension of the lattice.
2. CVP (closest vector problem) and SVP are linked in a way that makes
solving CVP "easy" if the corresponding SVP(s) is/are "easy" (easy =
solvable in polynomial time w.r.t. lattice dimension).
3. Factoring a number N that is not a prime power can be reduced to
CVP. The dimension of the lattice of the CVP instance is the number of
primes below log(N)^a for some power a>1. (Schnorr Adleman Prime
Number Lattice)
From what I know SVP and CVP are NP-hard (in general). So, to prove
that factoring integers is possible in polynomial time -- assuming
this "prime number lattice" works -- you'd need to prove that the
resulting SVP/CVP instances are always "easy" to solve (satisfying
some conditions that allow some algorithm to run in polynomial time).
I havn't seen anything in this regard in the slides.
Cheers!
SG