Integer Factorization
I am experimenting with an algorithm for integer factorization described in this thread.
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?p=858406#858406[/url] Any comments? 
Is there a reason to believe that a_i is more likely to have a large factor in common with phi(n) than a random integer?
Alex 
[QUOTE=mgb;108817]I am experimenting with an algorithm for integer factorization described in this thread.
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?p=858406#858406[/url] Any comments?[/QUOTE]It appears to be a variant on Pollard rho and you should analyze the map f(x) > x^x for its cycle behaviour. It's possible that it it behaves better than a random mapping, in which the cycle length is usefully less than sqrt(N)  the observed behaviour for the classical Pollard rho mapping f(x) > ax^2+c  but without the analysis I'm not convinced that it's even as good as Pollard's mapping in this regard. What does seem clear is that each iteration is much more computationally demanding than rho's single multiplication and addition in Z_N. I urge you to examine the cycle behaviour in more depth. Numerical experiments could well give you insight in how to approach the problem. Good luck! You may be on to something but don't get your hopes too high. Paul 
[QUOTE=xilman;108832]It appears to be a variant on Pollard rho and you should analyze the map f(x) > x^x for its cycle behaviour.[/QUOTE]Which reminds me of a crazy idea I had about 15 years ago.
Pollard rho is essentially searching for cycles mod p in a "random" mapping from Z_N to Z_N. Multiplication in Z_N is expensive without specialized hardware. However, specialized hardware existed back then for doing DES encryption and DES was designed to perform a random mapping (conspiracy theories aside) so ... Nothing came of it, of course, it would have been faster than regular rho by at most a constant factor, and I could see no way of exploiting constraints on the form of any factors. Paul 
Don't you need reduction mod p to be a homomorphism for the "random" map?
Alex 
[QUOTE=mgb;108817]I am experimenting with an algorithm for integer factorization described in this thread.
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?p=858406#858406[/url] Any comments?[/QUOTE]Not looking very promising. I coded up a very quick and dirty program in GMP and attempted to factor the integer 398105020104303515267327521 with a variety of starting values of a_0 and up to 10,000 iterations. The table below gives the number of iterations required to find a factor for 1 < a_0 < 100. The final line gives the minimum, maximum and mean number of iterations. [code] Iterations a_0 factor 2251 2 6943319 2914 3 6943319 2250 4 6943319 4154 5 6943319 866 6 6943319 3579 7 6943319 2302 9 6943319 136 11 6943319 999 12 6943319 955 13 6943319 2175 14 6943319 1554 15 6943319 3136 16 6943319 5397 17 6943319 1853 18 6943319 3415 19 6943319 3306 20 6943319 339 21 6943319 808 22 6943319 5092 23 6943319 1030 24 6943319 5511 25 6943319 459 26 6943319 2913 27 6943319 623 28 6943319 5539 29 6943319 1552 30 6943319 3927 31 6943319 674 32 6943319 144 33 6943319 536 34 6943319 2027 35 6943319 211 36 6943319 436 37 6943319 8648 38 6943319 1130 39 6943319 2216 40 6943319 2808 41 6943319 8678 42 6943319 7117 43 6943319 1989 44 6943319 945 45 6943319 125 46 6943319 678 47 6943319 111 48 6943319 1249 49 6943319 1896 50 6943319 587 51 6943319 380 52 6943319 2113 53 6943319 3096 54 6943319 125 55 6943319 947 56 6943319 9230 57 6943319 4012 58 6943319 2187 59 6943319 1797 60 6943319 2837 61 6943319 43 62 6943319 501 63 6943319 8354 64 6943319 173 65 6943319 1617 66 6943319 658 67 6943319 3674 68 6943319 103 69 6943319 547 70 6943319 1462 71 6943319 617 72 6943319 1035 73 6943319 1983 74 6943319 2337 75 6943319 6523 76 6943319 6132 77 6943319 5036 78 6943319 3172 79 6943319 31 80 6943319 775 81 6943319 1889 82 6943319 8367 83 6943319 498 84 6943319 255 85 6943319 1736 86 6943319 6319 87 6943319 102 88 6943319 546 89 6943319 2778 90 6943319 2027 91 6943319 1746 92 6943319 5024 93 6943319 235 94 6943319 288 95 6943319 576 96 6943319 155 97 6943319 785 98 6943319 1475 99 6943319 minimum = 31 maximum = 9230 mean = 2266.02 successes 96 [/code] Pollard rho would be expected to take approximately sqrt(6943319) == 2635 iterations to find this factor. Admittedly I've only tried factoring the one integer and I may just have hit on a particularly bad example, but your algorithm is not obviously better than rho and has a much more expensive mapping function. Note, also, that the algorithm failed to find a factor within 10,000 iterations in two cases (a_0 = 8 and 10). Keep analyzing it, but I'm not hopeful it will pay off. Paul 
Hmm, another example, N = 2131661909089739393111, gives somewhat better results:
[code] Iterations a_0 factor 30 2 262533041 99 3 262533041 29 4 262533041 43 5 262533041 353 6 262533041 72 7 262533041 75 8 262533041 34 9 262533041 13 11 262533041 23 12 262533041 100 13 262533041 25 14 262533041 42 15 262533041 41 16 262533041 45 17 262533041 51 18 262533041 127 19 262533041 35 20 262533041 400 21 262533041 49 22 262533041 99 23 262533041 38 24 262533041 227 25 262533041 161 26 262533041 98 27 262533041 56 28 262533041 238 29 262533041 225 30 262533041 80 31 262533041 27 32 262533041 307 33 262533041 18 34 262533041 23 35 262533041 67 36 262533041 62 37 262533041 22 38 262533041 30 39 262533041 60 40 262533041 49 41 262533041 85 42 262533041 78 43 262533041 266 44 262533041 37 45 262533041 101 46 262533041 354 47 262533041 72 48 262533041 10 49 262533041 148 50 262533041 32 51 262533041 107 52 262533041 9 53 262533041 317 54 262533041 93 55 262533041 99 56 262533041 158 57 262533041 227 58 8119594779271 33 59 262533041 170 60 262533041 94 61 262533041 40 62 262533041 135 63 262533041 53 64 262533041 15 65 262533041 33 66 262533041 72 67 262533041 56 68 262533041 128 69 262533041 111 70 262533041 43 71 262533041 337 72 262533041 49 73 262533041 238 74 262533041 13 75 262533041 97 76 262533041 296 77 262533041 67 78 262533041 239 79 262533041 30 80 262533041 130 81 262533041 288 82 262533041 95 83 262533041 73 84 262533041 43 85 262533041 31 86 262533041 127 87 262533041 317 88 262533041 63 89 262533041 134 90 262533041 80 91 262533041 161 92 262533041 70 93 262533041 93 94 262533041 173 95 262533041 520 96 262533041 32 97 262533041 83 98 262533041 125 99 262533041 minimum = 9 maximum = 520 mean = 110.86 successes 97 [/code] sqrt(262533041) = 16202. There was only one failure to find the factor in 10,000 iterations and the successes were rather more impressive and the larger factor was found on one occasion. Paul 
Thanks Paul for your analysis. I have found it is also possible to do a variation on this. Let M be a small integer. Let k vary a la Pollard Rho  f(k) = ??? modulo s where s is the square root of the number to be factored. With each iteration [I]increment M[/I] and let k[sub]1[/sub] = f(k[sub]0[/sub]) modulo s. Let H = M[sup]k[/sup] modulo n. Then try a[sub]0[/sub][sup]H[/sup] modulo n.

[QUOTE=akruppa;108830]Is there a reason to believe that a_i is more likely to have a large factor in common with phi(n) than a random integer?
Alex[/QUOTE] I thinks so because of the exponents exponent as explained in the thread... 
[code]
6943318=2*31*53*2113 262533040=2^4*5*7*11*17*23*109 8119594779270=2*3*5*13*17*139*937*9403 [/code] looks like it works better on smooth P1... 
On average, the algorithm expects to have O(log N) mults per iteration.
and...unless the average cycle length is as low as O(sqrt(p)/log p), I see no advantage compared to P1 or Rho. 
All times are UTC. The time now is 12:46. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.