Re: Factoring integers on a classical computer

From: *** T. Winter (***.Winter_at_cwi.nl)
Date: 03/17/05 

Date: Thu, 17 Mar 2005 01:18:34 GMT

In article <1110993675.236875.97690@z14g2000cwz.googlegroups.com> cafeinst@msn.com writes:
...
> Back to my argument: If primes is in P, then why doesn't it follow that
> there is an algorithm which factors in poly-time? After all, algorithms
> don't work by magic, so somewhere within the AKS algorithm, at least
> one of the factors had to have been computed indirectly; otherwise, how
> could we trust the algorithm?

The algorithm shows that a number has properties that a prime would not
have. It is *not* necessary for this to be even close to calculating a
factor. As I wrote, when I can show that a^p != a (mod p) for some a,
I know for sure that p is a composite, but I am not even close to
calculating a factor of p. I know for instance that with n = RSA-640,
2^n != 2 mod n. Am I close to a factor? Maple does that calculation
in something like milliseconds. 

-- 
*** t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~***/
Quantcast