examples of Pollard’s algorithm on a few integers
Let’s try Pollard’s method (http://planetmath.org/PollardsP1Algorithm) for our sample integers with and whenever is odd. Then our are 256, 512, 32 and 128 and thus for each we simply test whether 256, 511, 31 or 127 share any divisors with .
Take . It turns out 256, 511, 31 and 127 are all coprime to 2039189. So let’s try a higher test cap, . Our then become 18446744073709551616, 2417851639229258349412352, 562949953421312 and 33554432, putting the application of this algorithm out of reach for most scientific calculators. But suffice it to say that 18446744073709551615, 2417851639229258349412351, 562949953421311 and 33554431 are all coprime to . What do you say we try and give up if it doesn’t pan out? 340282366920938463463374607431768211455 and 5846006549323611672814739330865132078623730171903 disappoint as the others did. Finally 316912650057057350374175801344 gives something other than the 1 we’ve gotten accustomed to: 43. Dividing 2039189 by 43 gives us 47423. By now it’s understandable if you don’t want to put 47423 through this algorithm, since even a primitive implementation of trial division can quickly tell us that this composite is 47 times 1009. Thus the factorization of 2039189 is .
I’ll spare you the details for . Suffice it to say that the settings of and that worked just now for 2039189 succeed in giving us the laughably small factor 3 of 1411041 which trial division would have given up right away.
As it turns out, Pollard’s method applied to 4393547637856664251490043044051018234292171475232959 is doomed to failure for any and test caps of 10, 100 and 1000.
|Title||examples of Pollard’s algorithm on a few integers|
|Date of creation||2013-03-22 16:44:25|
|Last modified on||2013-03-22 16:44:25|
|Last modified by||PrimeFan (13766)|