Daniel Grace writes:
> 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.
Yup, almost certainly, if only because k is needed twice. The current
trial factoring method does not even use k per se.
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.
Not quite. My "reverse method" works that way, and will find the
smallest Mersenne exponent which is a multiple of a given odd number,
but the fastest-so-far trial factoring method actually squares and
perhaps multiplies by two modulo the trial factor each loop, starting
with two and looping over the _bits_ of the Mersenne exponent, making
it quite fast. If the particular bit is one, the multiply by two
occurs; if it's zero, it doesn't. That is, it calculates the Mersenne
number (two to the exponent power) mod the trial factor.
This algorithm is in Knuth, apparently, which I don't have a copy of.
Before GIMPS, I was doing something slower; George Woltman told me
about this method, speeding up my then-current trial factoring program
by a factor of about three (in Jan. 1996 or so).
Will
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
