mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Integer Factorization (https://www.mersenneforum.org/showthread.php?t=8482)

mgb 2007-06-24 08:07

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?

akruppa 2007-06-24 11:22

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

xilman 2007-06-24 13:07

[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

xilman 2007-06-24 13:14

[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

akruppa 2007-06-24 13:42

Don't you need reduction mod p to be a homomorphism for the "random" map?

Alex

xilman 2007-06-24 14:38

[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

xilman 2007-06-24 15:20

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

mgb 2007-06-24 18:03

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.

mgb 2007-06-24 18:08

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

wpolly 2007-06-25 05:36

[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 P-1...

wpolly 2007-06-25 05:40

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