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