Bruce Leenstra wrote:
>
> As luck would have it, this is nearly what I am doing right now:
>
> tempvalue = (q+1)/2
> count = 1
> while tempvalue != 1 {
> if tempvalue is odd tempvalue += q
> shiftright tempvalue
> count++
> }
> v = count
I'm not sure I understand that code yet, but
> I've crunched through all q < 2^23; [...] The program is really starting to slow
>down.
There may be a faster method.
Let f be a prime factor of the prime exponent Mersenne number M(p).
f | M(p) <=>
2^p == 1 (mod f) <=>
ord(2) (mod f) | p <=> (since ord(n) = 1 <=> n = 1)
ord(2) (mod f) = p.
Thus, f is a factor of M(p) if and only if the group order of 2 (mod f)
is equal to p.
On the other hand, ord(2) (mod f) divides f-1, since f is prime.
We can thus test whether f is a factor of some prime exponent Mersenne
M(p) by testing all prime divisors p of f-1 and checking if 2^p == 1
(mod f).
I add a quick hack to exemplify. Please don't take this code too
seriously. I made no effort to make it efficient, for example all odd
and not only prime f are tested and the trial division is pathetic, too.
An order of magnitude speedup would be possible.
But the basic algorithm is reasonably fast:
time ./ismersfac >/dev/null
real 1m7.907s
user 1m7.710s
sys
0m0.040s
for f < 10000000 =~ 2^23.25 , on a K6-II 500Mhz.
#include <stdio.h>
unsigned int powmod(unsigned int a, unsigned int b, unsigned int m) {
unsigned int t = 0, mask = 1<<31;
if (b == 0) return 1;
while ((b & mask) == 0) mask >>= 1;
mask >>= 1;
t=a;
while (mask) {
t = (unsigned long long) t * t % m;
if (b & mask) {
t = (unsigned long long) t * a % m;
}
mask >>= 1;
}
return t;
}
unsigned int ismersfac(unsigned int f) {
unsigned int fm1 = f-1;
unsigned p;
while ((fm1 & 1) == 0) fm1 >>= 1;
for (p = 3; p*p <= fm1; p+=2) {
if (fm1 % p == 0) {
if (powmod(2, p, f) == 1) {
return p;
} else {
while (fm1 % p == 0)
fm1 /= p;
}
}
}
if (fm1 > 1) {
if (powmod(2, fm1, f) == 1)
return fm1;
}
return 0;
}
int main() {
unsigned int i, p;
for (i=3; i < 10000000; i+=2) {
if ((p = ismersfac(i)))
printf("M( %d )C: %d\n", p, i);
}
return 0;
}
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
