View Single Post
Old 2007-06-24, 14:38   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×3×883 Posts
Default

Quote:
Originally Posted by mgb View Post
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
xilman is offline   Reply With Quote