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 $a^{p^e}$ are 256, 512, 32 and 128 and thus for each $n$ we simply test whether 256, 511, 31 or 127 share any divisors with $n$.

Take $n=2039189$. It turns out 256, 511, 31 and 127 are all coprime to 2039189. So let’s try a higher test cap, $B=100$. Our $a^{p^e}$ 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 $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 division can quickly tell us that this composite is 47 times 1009. Thus the factorization of 2039189 is $43\cdot 47\cdot 1009$.

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