Heya Lucas
> P-1 factoring is based upon Fermat's little theorem which states that
> with gcd(a,p)=1, p prime, a^(p-1)==1 mod p
> What if we use 2 as a base? Well, for mersenne numbers, this might be to
> our advantage. Note that 2^n==1 mod Mn, hence 2^q==2^(q mod n) mod Mn.
Unfortunately we're in a circular argument at this point. The factors of
2^p-1 are of the form 2kp+1 - also, even for n composite, the 'new'
(primitive) factors of 2^n-1 are of the form kn+1. So any prime factor q has
q-1 divisible by n, and we already have 2^n=1 mod Mn and hence mod q...
Alternatively, think of the values 2^0, 2^1, 2^2... 2^(n-1), which would be
ALL the values 2^q mod Mn can possibly take. So if this method found a
factor, it would be a common factor of 2^q-1 and 2^n-1, in other words, just
one of the known algebraic factors 2^gcd(q,n)-1.
P-1 is good up to a point... the prime factors P it finds will by definition
either have ALL factors of P-1 very small, or your initial base is already a
high power (which is very unlikely). It's good to find the 'smooth' P-1's -
put it another way, the factors the P-1 algorithm finds are themselves very
easy to prove prime or composite. While the vast majority of primes (and
thus potential factors) certainly do not always have small factors in P-1.
It will catch a few several digit factors - after that, you've pretty well
exhausted the lowest cherries off the tree.
Chris
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
