PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] examples of Pollard's $p - 1$ algorithm on a few integers (Example)

Let's try Pollard's $p - 1$ method 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 $1 < a < 1001$ and test caps of 10, 100 and 1000.




"examples of Pollard's $p - 1$ algorithm on a few integers" is owned by PrimeFan.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: right, succeed, composite, trial division, primitive, even, scientific calculators, algorithm, application, coprime, divisors, odd, integers

This is version 1 of examples of Pollard's $p - 1$ algorithm on a few integers, born on 2007-02-23.
Object id is 8963, canonical name is ExamplesOfPollardsP1AlgorithmOnAFewIntegers.
Accessed 1168 times total.

Classification:
AMS MSC11A41 (Number theory :: Elementary number theory :: Primes)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)