examples of Pollard’s p-1 algorithm on a few integers

Let’s try Pollard’s p-1 method (http://planetmath.org/PollardsP1Algorithm) for our sample integers with B=10 and a=2 whenever n is odd. Then our ape are 256, 512, 32 and 128 and thus for each n we simply test whether 256, 511, 31 or 127 share any divisorsMathworldPlanetmathPlanetmath with n.

Take n=2039189. It turns out 256, 511, 31 and 127 are all coprimeMathworldPlanetmath to 2039189. So let’s try a higher test cap, B=100. Our ape then become 18446744073709551616, 2417851639229258349412352, 562949953421312 and 33554432, putting the application of this algorithmMathworldPlanetmath out of reach for most scientific calculators. But suffice it to say that 18446744073709551615, 2417851639229258349412351, 562949953421311 and 33554431 are all coprime to n. What do you say we try a=4 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 divisionMathworldPlanetmath can quickly tell us that this composite is 47 times 1009. Thus the factorization of 2039189 is 43471009.

I’ll spare you the details for n=1411041. Suffice it to say that the settings of a and B 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 p-1 method applied to 4393547637856664251490043044051018234292171475232959 is doomed to failure for any 1<a<1001 and test caps of 10, 100 and 1000.

Title examples of Pollard’s p-1 algorithm on a few integers
Canonical name ExamplesOfPollardsP1AlgorithmOnAFewIntegers
Date of creation 2013-03-22 16:44:25
Last modified on 2013-03-22 16:44:25
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 4
Author PrimeFan (13766)
Entry type Example
Classification msc 11A41