Re: Factoring integers on a classical computer

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

Date: Thu, 17 Mar 2005 01:39:21 GMT

In article <1111001652.654406.162030@l41g2000cwc.googlegroups.com> "Craig Feinstein" <cafeinst@msn.com> writes:
...
> 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,

Yes, you were lucky to find a cycle.

> 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.

This is wrong on two counts. 2^4 = 1 mod 15, but 4 does not
divide 15. 4 divides (as it should according to Euler's extension of
Fermat's little theorem) phi(15) = 8. And your 3 divides phi(45) = 24.

Second, if we have a multiplicative cycle of order k in a
multiplicative group of order n, k is a divisor of n. But the
multiplicative group for numbers mod n is *not* order n, it is
order phi(n) (which is n-1 if n is prime). If n is composite,
the numbers 1 to n-1 do not form a group; there are zero-divisors
in that ring.

Now, if there was somebody who could from the finding of a divisor
of phi(n) find a factor of n, we would have something. 

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