Integer Factorization

mgb · 2007-06-24, 08:07

I am experimenting with an algorithm for integer factorization described in this thread.

http://www.artofproblemsolving.com/F...=858406#858406

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:

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

xilman · 2007-06-24, 13:14

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

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:

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

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

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 increment M and let k₁ = f(k₀) modulo s. Let H = M^k modulo n. Then try a₀^H modulo n.

mgb · 2007-06-24, 18:08

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

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

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.

2007-06-24, 08:07	#1
mgb "Michael" Aug 2006 Usually at home 2²×3×7 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, 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-25, 05:36	#10
wpolly Sep 2002 Vienna, Austria 3·73 Posts	Code: 6943318=231532113 262533040=2^457111723109 8119594779270=23513171399379403 looks like it works better on smooth P-1...

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Utility of integer factorization.	jwaltos	Other Mathematical Topics	8	2015-05-22 12:20
Integer factorization?	bearnol2	Information & Answers	7	2010-12-09 02:50
Integer factorization with q < 2p	mgb	Math	36	2009-11-07 15:59
CADO workshop on integer factorization	akruppa	Factoring	14	2008-09-18 23:52
Integer Factorization 2	mgb	Math	5	2007-07-23 12:55

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, 18:03	#8
mgb "Michael" Aug 2006 Usually at home 124₈ 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 k₁ = f(k₀) modulo s. Let H = M^k modulo n. Then try a₀^H modulo n. Last fiddled with by mgb on 2007-06-24 at 18:04

2007-06-25, 05:40	#11
wpolly Sep 2002 Vienna, Austria 3×73 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.