Hi,
I seem to remember about 3.5 years ago someone (I think it was Chris Nash)
had done something similar & eliminated a lot of Mersenne numbers.
Is it worthwhile mounting a formal attack on the Mersenne numbers between 20
million & say 40 million using this technique? We're getting quite close to
this & I think Chris would not have bothered with these, since they were so
far ahead of LL testing at that point (first tests around 6 million).
Regards
Brian Beesley
On Thursday 21 March 2002 00:21, Alexander Kruppa wrote:
> 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
