Mersenne: netconx
L.S., Any netconx teammember on the list that can contact me? YotN, Henk Stokhorst _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors aren't just factors
Don't be so hard on Phil, I made not only a mistake but one that was very easy to catch. I should know by now better than to trust my memory before sending something out. But it's hard to get used to being senile :-) I guess that also explains why I never pursued it... Steve -Original Message- From: Torben Schlüntz [EMAIL PROTECTED] To: Phil Moore [EMAIL PROTECTED]; [EMAIL PROTECTED] [EMAIL PROTECTED] Date: Wednesday, March 20, 2002 4:41 PM Subject: SV: Mersenne: Factors aren't just factors Actually I should have let Steve answer this, but I can't ignore to say that I already have pointed out that M89 is prime. So Steve had a mistake. Okay?! I do several mistakes every hour. snip _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Stop computations before the last term of the Lucas-Lehmer serie
If a term of the Lucas-Lehmer serie equals 0 modulo Mx, then if it is the last term Mx is prime else Mx is not prime (because next terms will be -2 ; 4 ; 4 ; 4...). In both cases, we needn't compute next terms. Checking if a term of the Lucas-Lehmer serie equals 0 can be done, for example, during the inverse transform or during the substraction. So, this test is cheap and it would not slow down the program. However, it would be interesting if and only if a term of the Lucas-Lehmer serie can be 0 before the last term. What do you think about this idea ? _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors aren't just factors
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
real1m7.907s
user1m7.710s
sys
0m0.040s
for f 1000 =~ 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 = 131;
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 1000; 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
Mersenne: A runaway P95 install script?
Hi all. There was some discussion earlier about a team that reserved several thousand exponents only to let them expireafter 60 days. I'm not sure we ever resolved what was happening then, but we have something similar on another team now. Is there anyone who can speak for BART (machine) on netconx (team)? This machine began acquiring 33Ms every few minutes for the past day or two, and has amassed several hundred by now. If it is intentional fine. If not, since it is still reserving away, I thought bringing up the fact might lessen the longer term reservation impact. Respectfully, C. Garrison
Re: Mersenne: A runaway P95 install script?
C. Garrison wrote: Hi all. There was some discussion earlier about a team that reserved several thousand exponents only to let them expire after 60 days. I'm not sure we ever resolved what was happening then, but we have something similar on another team now. Is there anyone who can speak for BART (machine) on netconx (team)? This machine began acquiring 33Ms every few minutes for the past day or two, and has amassed several hundred by now. If it is intentional fine. If not, since it is still reserving away, I thought bringing up the fact might lessen the longer term reservation impact. Respectfully, C. Garrison Nope, it is the very same machine of the very same team that did this twice before, again in the same characteristical amount of reservations per hour. Not a single exponent will be returned. The only way to contact that machine seems to be through the emailaddress in the client if even that is known to the server. YotN, Henk Stokhorst _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
