Re: Factoring integers on a classical computer

From: Craig Feinstein (cafeinst_at_msn.com)
Date: 03/16/05 

Date: 16 Mar 2005 11:34:12 -0800

*** T. Winter wrote:
> In article <1110905557.170005.112500@l41g2000cwc.googlegroups.com>
cafeinst@msn.com writes:
> ...
> > > "I mean "If one can determine that a number is composite in
poly-time,
> > > one should also be able to determine its factors in poly-time,
since
> > > the factors are what determine whether the number is composite
or not."
> ...
> > Obviously, I don't possess your superior intellect, which is why I
am
> > asking you or any of the other wise men and women of usenet to
explain
> > the fallacy in my argument.
>
> The fallacy is pretty simple. There are properties that composite
numbers
> have that prime numbers do not have (and the converse), aside from
having
> some specific factors. One of those is Fermat's little theorem: if p
> is prime: a^p = a (mod p). If you can show that there is an a such
that
> a^p != a (mod p) you know that p is not prime, but you have no idea
what
> the factors may be. And there are more such properties that are used
in
> primality testing.
> --
> *** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland,
+31205924131
> home: bovenover 215, 1025 jn amsterdam, nederland;
http://www.cwi.nl/~***/

Here's how one might think of building a polynomial-time factoring
algorithm from Fermat's Little Theorem. I am predicting that whenever
there is a composite number n in which Fermat's Little Theorem fails
for some a, one can find one of its factors in polynomial-time from
simply examining how Fermat's Little Theorem fails:

For instance, take the number n=45, which we know is composite. Let's
check
to see how Fermat's Little Theorem fails when a=7, in which
gcd(7,45)=1:

Let's compute 7^(45-1)=7^44 (mod 45) with the standard polynomial-time
algorithm for computing exponents, modulo n: (I'll use the equals sign
when I really
mean equivalence).

7^44=7^(2*22)=(7^2)^22=49^22=4^22 (mod 45)
=(4^2)^11=16^11=16^(2*5+1)=[(16^2)^5]*16=(256^5)*16 (mod 45)
=(31^5)*16=[31^(2*2+1)]*16=(16^2)*31*16 (mod45)
=31*31*16=(31^2)*16=16*16=16^2=31 (mod 45)

Notice when looking at the calculations which just proved that 45 is
composite that we detect a cycle - we see from the computations that
16^2=31 (mod 45) and 31^2=16 (mod 45). In other words,

16^0=1 (mod 45)
16^1=16 (mod 45)
16^2=31 (mod 45)
16^3=1 (mod 45)

So we have a multiplicative cycle of order 3 in a ring of size 45.
Therefore, 3
divides 45. I see no reason why such a procedure cannot be programmed
to factor composite integers for which Fermat's Little Theorem fails,
in polynomial-time. I also see no reason why a similar procedure like
this cannot be used with the polynomial-time 2002 AKS algorithm, in
which a generalization of Fermat's Little Theorem is used.

Therefore, it appears to me that unless I have made a stupid error
somewhere in my analysis, factoring is probably possible in poly-time.
Any arguments against this?

Craig

Quantcast