Re: Factoring integers on a classical computer

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

Date: 17 Mar 2005 06:54:41 -0800

*** T. Winter wrote:
> In article <1111025129.422477.253560@l41g2000cwc.googlegroups.com>
"Craig Feinstein" <cafeinst@msn.com> writes:
> > Yes, I realized my mistake when I saw Tim's post and addressed a
> > response to him. But note the formula for
phi(p^k)=[p^(k-1)]*(p-1), for
> > prime p, and phi is a multiplicative function. From this
observation,
> > it seems that it shouldn't be so difficult to find a factor of n
from
> > the factors of phi(n).
>
> Oh, well, as far as I know, nobody has found a method yet.
>
> > I don't think I was lucky in finding a cycle out of my
calculations. I
> > did it for a few other numbers and came up with similar cycles. My
> > guess is that this procedure always leads to some factors of
phi(n).
>
> As long as the prime factorisation contains primes that are one
larger
> than a product of small primes you stand a good chance. But try
1081,
> I am going to calculate 2^1080 mod 1081:
>
> 2^1 = 2
> 2^2 = 4
> 2^4 = 16
> 2^5 = 32
> 2^10 = 1024
> 2^15 = 32768 -> 338
> 2^30 = 114244 -> 739
> 2^45 = 249782 -> 71
> 2^90 = 5041 -> 717
> 2^135 = 50907 -> 100
> 2^270 = 10000 -> 271
> 2^540 = 73441 -> 1014
> 2^1080 = 1028196 -> 165
>
> Do you see a cycle?
> --
> *** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland,
+31205924131
> home: bovenover 215, 1025 jn amsterdam, nederland;
http://www.cwi.nl/~***/

OK, ***. You win. Very counterintuitive to me.

Thank you,
Craig

Quantcast