Re: Factoring integers on a classical computer

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

  • Next message: tchow_at_lsa.umich.edu: "Re: Factoring integers on a classical computer" 
    Date: Thu, 17 Mar 2005 13:30:47 GMT

    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/~***/
  • Next message: tchow_at_lsa.umich.edu: "Re: Factoring integers on a classical computer"
    • Quantcast