Mersenne Digest Thursday, March 25 1999 Volume 01 : Number 537
----------------------------------------------------------------------
Date: Mon, 22 Mar 1999 11:17:09 +0100 (MET)
From: "Benny.VanHoudt" <[EMAIL PROTECTED]>
Subject: Mersenne: LL-testing
Hi,
I was looking at the LL-test and thought of the following:
To succeed a LL-test the final value (mod 2^p - 1) has to be zero.
To be able to get this there has to be a number x (between 0 and 2^p - 2)
such that x^2 = 2. This because in the final step of the
LL test the value is squared and substracted by two.
In some cases for example 15 = 2^4 - 1 (this cannot be prime because
four isn't but that's not the point) such a value does not exist:
0^2 = 0, 1^2 = 1, 2^2 = 4, 3^2 = 9, 4^2 = 1, 5^2 = 10, 6^2 = 6, 7^2 = 4,
8^2 = 4, 9^2 = 6, 10^2 = 10, 11^2 = 1, 12^2 = 9, 13^2 = 4 and 14^2 = 1.
Of course in this case p = 4 is not prime so we would never do a LL-test
anyway. My question is whether anyone knows if such an x always exists if p
is indeed a prime ? Perhaps this is only true for a subset of all primes,
and this would allow us to focus on this subset only (if it can be
determined more easily) ?
- -------------------------------------------------------------------
Benny Van Houdt,
University of Antwerp
Dept. Math. and Computer Science
PATS - Performance Analysis of Telecommunication
Systems Research Group
Universiteitsplein, 1
B-2610 Antwerp
Belgium
email: [EMAIL PROTECTED]
- --------------------------------------------------------------------
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 22 Mar 1999 11:56:35 +0100 (MET)
From: [EMAIL PROTECTED]
Subject: Re: Mersenne: LL-testing
"Benny.VanHoudt" <[EMAIL PROTECTED]> asks
> I was looking at the LL-test and thought of the following:
> To succeed a LL-test the final value (mod 2^p - 1) has to be zero.
> To be able to get this there has to be a number x (between 0 and 2^p - 2)
> such that x^2 = 2. This because in the final step of the
> LL test the value is squared and substracted by two.
>
> In some cases for example 15 = 2^4 - 1 (this cannot be prime because
> four isn't but that's not the point) such a value does not exist:
>
> 0^2 = 0, 1^2 = 1, 2^2 = 4, 3^2 = 9, 4^2 = 1, 5^2 = 10, 6^2 = 6, 7^2 = 4,
> 8^2 = 4, 9^2 = 6, 10^2 = 10, 11^2 = 1, 12^2 = 9, 13^2 = 4 and 14^2 = 1.
>
> Of course in this case p = 4 is not prime so we would never do a LL-test
> anyway. My question is whether anyone knows if such an x always exists if p
> is indeed a prime ? Perhaps this is only true for a subset of all primes,
> and this would allow us to focus on this subset only (if it can be
> determined more easily) ?
>
If p = 2k + 1 is odd, then x = 2^(k+1) satisfies x^2 = 2 + 2*(2^p - 1).
As far as I know, we don't know how to predict whether the next-to-last
term will be 2^((p+1)/2) or -2^((p+1)/2) in the LL-sequence. For example,
modulo 31, the backwards sequence might go
0
/ \
/ \
8 23
/ | |\
/ | | \
14 17 5 26
/| | \ |\ \
/ | | \ | \ |\
4 27 9 22 10 21 11 20
The left upward sequence (4 -> 14 -> 8 -> 0) is of course the
proper sequence. But with everything having two ancestors,
how do we predict that? Modulo 127 the sequence
4 -> 14 -> 67 -> 42 -> 111 -> 0 has 111 == -16 preceding the zero.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 22 Mar 1999 07:06:21 -0700
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: Mersenne: Can NTPrime be coded for MP?
I have a few quad processor PPro machines that I run NTPrime on.
Currently, they're set up to run 4 instances of NTPrime with affinities from
0-3, and this works just fine.
Now, I'm sure George has thought of this, maybe, but wouldn't it be fun to
have a version of NTPrime that was capable of multi-processor computations?
Does the algorithm lend any good ways to do this?
The reason I thought of this was that if this is possible, would it not also
be possible to use multiple computers on a network to work on the same
number? With Windows OS', you could use DCOM or even just RPC to get many
machines working on the same number.
I thought perhaps it might look something like you assign a "group" name in
prime.ini, identifying that PC as belonging to a group of others all working
in tandem.
It might be too slow for the Internet since the dataset we're talking about
can be big, but for a LAN, I think it's reasonable, and certainly a good
idea for multiprocessing on the same machine.
I just don't know enough about the LL algorithm to see for myself whether it
can be scaled to MP in any useful way. Basically I think it'd be fun to
hook my 32 current PC's together and have them crank out a single LL test on
an exponent above 7M in less than a day. It'd make a great double-checking
"engine" when we find the next prime. We could verify it in hours rather
than weeks. :-)
Just a thought, maybe someone has more thoughts on this.
Aaron
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 22 Mar 1999 12:14:13 -0500
From: [EMAIL PROTECTED]
Subject: Mersenne: BBS
>>Anyone know anything about the BBS generator? I've been able to find
>>little on it.
>>Knuth vol 2 (3rd ed) p. 35-36 gives a reference to
>>Blum, Blum & Shub, SIAM Journal of Computing, vol 15 (1986),
>>pp364-383 (published by the Society for Industrial and Applied
>>Mathematics)
If memory serves, there's also a nice description of it in _Applied
Cryptography_ which may or may not be closer at hand, or a more
interesting read.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 22 Mar 1999 21:15:00 +0100 (CET)
From: Henrik Olsen <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Can NTPrime be coded for MP?
On Mon, 22 Mar 1999, Aaron Blosser wrote:
> Subject: Mersenne: Can NTPrime be coded for MP?
>
> I have a few quad processor PPro machines that I run NTPrime on.
>
> Currently, they're set up to run 4 instances of NTPrime with affinities from
> 0-3, and this works just fine.
>
> Now, I'm sure George has thought of this, maybe, but wouldn't it be fun to
> have a version of NTPrime that was capable of multi-processor computations?
>
> Does the algorithm lend any good ways to do this?
>
> The reason I thought of this was that if this is possible, would it not also
> be possible to use multiple computers on a network to work on the same
> number? With Windows OS', you could use DCOM or even just RPC to get many
> machines working on the same number.
>
> I thought perhaps it might look something like you assign a "group" name in
> prime.ini, identifying that PC as belonging to a group of others all working
> in tandem.
>
> It might be too slow for the Internet since the dataset we're talking about
> can be big, but for a LAN, I think it's reasonable, and certainly a good
> idea for multiprocessing on the same machine.
>
> I just don't know enough about the LL algorithm to see for myself whether it
> can be scaled to MP in any useful way. Basically I think it'd be fun to
> hook my 32 current PC's together and have them crank out a single LL test on
> an exponent above 7M in less than a day. It'd make a great double-checking
> "engine" when we find the next prime. We could verify it in hours rather
> than weeks. :-)
>
> Just a thought, maybe someone has more thoughts on this.
>From what I know, FFT can be effectively handled by multiple processors
with a shared memory abstraction, which should make it possible to greatly
accelerate the LL test in a single SMP machine.
On the other hand, the shared memory abstraction is really crappy
speedwise when implemented in a clustered situation (memory access gets
something like 4 orders of magnitude slower even if you use dedicated
100base-t links between the machines), so that wouldn't lend itself to
parallellation nearly as well.
My suggestion would be to forget about clustering the machines, and
concentrate on either redoing the FFT for SMP or automating multiple
simultaneous tests on the same machine.
- --
Henrik Olsen, Dawn Solutions I/S
URL=http://www.iaeste.dk/~henrik/
Get the rest there.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 22 Mar 1999 16:02:38 -0500 (EST)
From: Jason Stratos Papadopoulos <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Can NTPrime be coded for MP?
On Mon, 22 Mar 1999, Aaron Blosser wrote:
> The reason I thought of this was that if this is possible, would it not also
> be possible to use multiple computers on a network to work on the same
> number? With Windows OS', you could use DCOM or even just RPC to get many
> machines working on the same number.
We all wish that was the case. Unfortunately, the LL test is completely
sequential, so that the only parallelism you can hope to find in it would
be a parallel FFT. But the FFT requires all-to-all communication among
different parallel processors, and this would be far too slow over,
say, ethernet. To put it in perspective, GIMPS will soon need 512k size
FFTs, and 512k doubles means 4MB. You'll have to pump 4MB of data through
your LAN (twice per iteration) and have to do it in under a second for any
hope of a speedup. Beowulf can do this, but Beowulf isn't the norm.
Another vaguely appealing notion is to completely recode Prime95 to use
number-theoretic FFTs, have all your processors do several LL iterations
locally (much smaller FFTs too, since number theory lets you break up
the problem into bite-size chunks), and combine the results into a
single giant residue that gets mod'd and redistributed to all the
processors.
Problem is, it isn't obvious to me how (or even if) you can perform the
single subtraction the LL test requires while in "number theoretic Fourier
space". Sure, you could just subtract the FFT of 2 from the FFT of the
residue, but does that give the same answer as doing the LL test the
conventional way?
jasonp
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 23 Mar 1999 09:06:43 -0500
From: Joth Tupper <[EMAIL PROTECTED]>
Subject: Mersenne: LL-testing
Message text written by "Benny.VanHoudt"
>I was looking at the LL-test and thought of the following:
To succeed a LL-test the final value (mod 2^p - 1) has to be zero.
To be able to get this there has to be a number x (between 0 and 2^p - 2)
such that x^2 = 2. This because in the final step of the
LL test the value is squared and substracted by two.
In some cases for example 15 = 2^4 - 1 (this cannot be prime because
four isn't but that's not the point) such a value does not exist:
0^2 = 0, 1^2 = 1, 2^2 = 4, 3^2 = 9, 4^2 = 1, 5^2 = 10, 6^2 = 6, 7^2 = 4,
8^2 = 4, 9^2 = 6, 10^2 = 10, 11^2 = 1, 12^2 = 9, 13^2 = 4 and 14^2 = 1.
Of course in this case p = 4 is not prime so we would never do a LL-test
anyway. My question is whether anyone knows if such an x always exists if p
is indeed a prime ? Perhaps this is only true for a subset of all primes,
and this would allow us to focus on this subset only (if it can be
determined more easily) ?
<
>From quadratic reciprocity, 2 is a square for any prime of the form M = 2^p
- - 1.
Is there a good way to find a square root of 2 mod M? Actually, I think
that
any good enough way would have to find that square root faster than one FFT
squaring used in the LL test or there is no relative gain.
On the other hand, I have never heard of any root extraction mod a prime
that was significantly different from checking all cases [with just pretty
obvious
eliminations, say starting after 2^((p-1)/2)].
Anyone know something better?
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 23 Mar 1999 18:05:34 -0800
From: Gordon Irlam <[EMAIL PROTECTED]>
Subject: Mersenne: Blocking of postings
We have taken several new steps to protect ourselves and this list from
spam.
For some time we have blocked posts from people not listed as list
members. If your postings haven't made it to the list in the past, this
is probably the reason. You need to make sure your posting address and
subscription address match, before your messages will be able to get
through. If not, your message gets discarded, without any error message
getting sent back to you.
We now also block all email from addresses on any of six real time lists
of known spam addresses:
RBL - static IP spam addresses - http://maps.vix.com/rbl/
ORBS - static IP open relays - http://www.orbs.org/
DUL - dialup IP address blocks - http://maps.vix.com/dul/
DSSL - dialup IP host names - http://www.imrss.org/dssl/
shub-inter.net - open relays - http://www.shub-inter.net/
shub-inter.net - spam IP addresses - http://www.shub-inter.net/
You should receive an error message if you accidentally run into any of
these blocks.
Additionally, we now block postings with an invalid "From" domain, and
messages to the list without any "From:" line, which used to bypass our
anti-spam measures.
The goal is to significantly cut down on the volume of spam we receive,
while minimaly impacting the operation of the list. These are new
measures with the possibility of unintended side-effects.
The thought of intentionally blocking email generates a fair amount of
trepidation on my part. I don't want to accidentally and unknowingly
end up blocking legitimate messages. So, if you used to be able to post
to the list, but now find yourself unable to do so as a result of these
measures, I *want* to know. *Please tell me*. Either send me a message
to me from a non-blocked host, relay a message to me via someone else on
the list, or phone me at +1 (415) 566 7479.
thanks,
gordoni (list admin)
PS: In other administrative news: we have upgraded to the latest version
of majordomo (this allows us to send a verification message before
subscribing someone (we were having problems with bogus subscription
requests)), we have upgraded to the latest version of sendmail (for
improved spam blocking), we have moved our server from a friend's house
in Mountain View to my new place in San Francisco, and we switched to a
higher speed Internet connection around a month ago.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Thu, 25 Mar 1999 12:51:09 +0100 (CET)
From: Henrik Olsen <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Mersenne Machine & Single Floppy LL Tester
On Wed, 10 Mar 1999, Curtis (Jewell) Whalen wrote:
> >From: Marc Getty <[EMAIL PROTECTED]>
<snips>
> >Single Floppy LL Tester?
> >========================
> >Method Two
> >- ----------
> >Use a linux bootable disk with mprime on it set to automatically
> >load on boot, again only manual testing, with temporary files
> >redirected to the hard drive of the computer. The linux kernel
> >would have to be both FAT32 aware, because most new machines
> >ship with FAT32 formatted hard drives now. Hell, if you are really
> >good network support could also be built into this disk!
> >
> >I am not a linux guru by any means, but I'm pretty sure this is
> >possible, and can then be freely distributed as a disk image.
>
> I REALLY like this idea.
>
> If this disk got distributed, maybe put LS-120 (SuperDisk) drivers on the disk
> for an alternate temporary files location as well. I know Linux has them.
>
> Or just make a big ramdrive!
>
> --Curtis
I've made a first approximation for a floppy like this and put it on
http://www.iaeste.dk/~henrik/projects/mprime.html
It's a standalone very small, very limited Linux system with mprime plus
the utilities to run.
I could have made it a lot smaller if I hadn't been adding a complete
runtime environment to figure out why mprime kept segfaulting on me, until
I finally figured out it's because it doesn't do all the checks it should
for low memory, so blindly uses the not after all allocated memory:(
If there is interest, I'll try to make it more useful, but there sure
isn't room for much, more right now:)
bye for now
- --
Henrik Olsen, Dawn Solutions I/S
URL=http://www.iaeste.dk/~henrik/
Get the rest there.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
End of Mersenne Digest V1 #537
******************************
