Re: Factoring integers on a classical computer

From: Enzo (nomail_at_nomail.it)
Date: 03/17/05 

Date: Thu, 17 Mar 2005 19:26:16 +0100

*** T. Winter wrote:
> 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?

A little bit closer (one bit?)
Think about an encoding of a factorization of a number.
Surely the information that the factors are more then one needs at least
one bit to be encoded.
:-)

Quantcast