> Anyway, any mersenne's factor can be written as 2kp+1
>
<snip>
> directly). Call (P-1)/p = Q
>
> Then 2n = Q mod p
> n = Q/2 mod p which is well defined
> Therefore we can find the sun of the two factors mod p.
I think what you are trying to say is
M_p is composite for p a prime iff
1+2kp divides (2^(p-1)-1)/p - k for some k>0.
If I am not mistaken factoring this using current methods
is harder than factoring 2^p - 1. Remeber it is easy to
trial divide 2^p - 1 using bit wise operators, because
2^p - 1=1+2+2^2+...+2^(p-1). Let u be a potential divisor
(e.g. u=2kp+1) then let j be smallest int. such that 2^j-1>u
then you can try dividing 2^p-1 using just j bits of storage.
e.g. start with 1+2+2^2+...+2^(j-1), subtract u, shift to the
left appending 1's at the start, until you get v>u,
subtract u and so on. I think that the software stops
if it gets a residue of 0 before all p bits have been
eliminated - in this case u divides some smaller Mersenne.
Rgds,
----------------------------------------------------------
Daniel
e-mail: [EMAIL PROTECTED]
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
