mersenneforum.org > Math Integer Factorization
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-06-24, 08:07 #1 mgb   "Michael" Aug 2006 Usually at home 2·41 Posts Integer Factorization I am experimenting with an algorithm for integer factorization described in this thread. http://www.artofproblemsolving.com/F...=858406#858406 Any comments?
 2007-06-24, 11:22 #2 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 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
2007-06-24, 13:07   #3
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

254268 Posts

Quote:
 Originally Posted by mgb I am experimenting with an algorithm for integer factorization described in this thread. http://www.artofproblemsolving.com/F...=858406#858406 Any comments?
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

2007-06-24, 13:14   #4
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2B1616 Posts

Quote:
 Originally Posted by xilman It appears to be a variant on Pollard rho and you should analyze the map f(x) -> x^x for its cycle behaviour.
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

 2007-06-24, 13:42 #5 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Don't you need reduction mod p to be a homomorphism for the "random" map? Alex Last fiddled with by akruppa on 2007-06-24 at 13:42
2007-06-24, 14:38   #6
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

254268 Posts

Quote:
 Originally Posted by mgb I am experimenting with an algorithm for integer factorization described in this thread. http://www.artofproblemsolving.com/F...=858406#858406 Any comments?
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
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

Last fiddled with by xilman on 2007-06-24 at 14:43 Reason: Note about failures

 2007-06-24, 15:20 #7 xilman Bamboozled!     "πΊππ·π·π­" May 2003 Down not across 2·5·1,103 Posts 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 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
 2007-06-24, 18:03 #8 mgb   "Michael" Aug 2006 Usually at home 1228 Posts 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 increment M and let k1 = f(k0) modulo s. Let H = Mk modulo n. Then try a0H modulo n. Last fiddled with by mgb on 2007-06-24 at 18:04
2007-06-24, 18:08   #9
mgb

"Michael"
Aug 2006
Usually at home

5216 Posts

Quote:
 Originally Posted by akruppa 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
I thinks so because of the exponents exponent as explained in the thread...

 2007-06-25, 05:36 #10 wpolly     Sep 2002 Vienna, Austria 110110112 Posts Code: 6943318=2*31*53*2113 262533040=2^4*5*7*11*17*23*109 8119594779270=2*3*5*13*17*139*937*9403 looks like it works better on smooth P-1...
 2007-06-25, 05:40 #11 wpolly     Sep 2002 Vienna, Austria 3338 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post jwaltos Other Mathematical Topics 8 2015-05-22 12:20 bearnol2 Information & Answers 7 2010-12-09 02:50 mgb Math 36 2009-11-07 15:59 akruppa Factoring 14 2008-09-18 23:52 mgb Math 5 2007-07-23 12:55

All times are UTC. The time now is 11:11.

Mon Dec 6 11:11:29 UTC 2021 up 136 days, 5:40, 0 users, load averages: 1.94, 2.75, 3.78

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.