It is well known that n is prime if for all prime factors of n-1, a^(n-1)
= 1 mod n and a^((n-1)/q) is not 1 mod n.
For example, take a=2, and 2^p+1 (p is prime, yes, that IS a plus)
Then we need to check if 2^(2^p)=1 mod (2^p -1) and 2^((2^p)/2) is not 1.
Now, we know that 2^p = 1 mod (2^p - 1)
so, 2^n = 2^n*2^p mod (2^p - 1)
It is a simple extension to say that (2^n = 2^(n mod p) ) mod 2^p-1
So 2^(2^p) = 2^(2^p mod p) mod (2^p - 1) (Still following?)
So to check primality of 2^p+1, only need to check value of 2^p and
2^(p-1) (which is obviously (2^p)/2).
The main reason I am asking this is that I know that to check whether a
number is a factor of a mersenne prime involves checking 2^p - 1 mod n for
a number n and I was wondering if anyone's factoring code would go that
high and wether it would be quicker to check this than the traditional 2^p
- 1.
------------------------------------
Chris Jefferson, Girton College, Cambridge, [EMAIL PROTECTED]
------------------------------------
Someone may have beaten me to Fermat's Last Theorem, but I've done
Riemann's general equation. However it won't fit in my signature file...
------------------------------------
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
