Lucas Wiman wrote, about the p-1 algorithm:
>What if we use 2 as a base?
Unfortunately, 2 is not an eligible base for the powering.
Example: let's attempt to factor 2^11 - 1 = 23*89 via p-1. The smaller
factor has p-1 = 22=2*11, so raising the base to the powers 2 and 11
and gcd'ing should reveal the factor. Let's denote the product of the
small primes used for the powering by #, and try bases A = 2 and 3:
A=2: 2^22 mod M11 = (2^11)^2 mod M11 == 1. You can continue to power until
you're blue in the face, and all you'll ever get is one, i.e. gcd(a^#-1, M11)
= 0.
A=3: 3^22 mod M11 = 1013, so gcd(a^#-1, M11) = gcd(1012,2047) = 23.
For Mersennes you can in fact use any base you like, as long as it's not
a power of 2.
EXERCISE: We wish to attempt to find an odd prime factor p of a number N
via the p-1 method. What is the mathematical requirement for A to be an
eligible base for the powering?
EXERCISE: which movie is the following quote from?
"...and three shall be the number of the counting. Four shalt thou not count,
nor two, excepting thou then proceed to three. Five is right out..."
-Ernst
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
