Re: Factoring integers on a classical computer

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

Date: 17 Mar 2005 10:23:30 -0800

Craig Feinstein wrote:
> *** 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

Here is a related question: Can anyone give an example of a problem in
which determining whether a solution exists is easy (can be done in
poly-time), but where finding the solution has been proven to require
super-polynomial time?

Craig

Quantcast