Mersenne Digest Tuesday, March 30 1999 Volume 01 : Number 538
----------------------------------------------------------------------
Date: Thu, 25 Mar 1999 15:30:11 EST
From: [EMAIL PROTECTED]
Subject: Mersenne: Small Conjecture (not mine, sadly).
The following was posted on sci.math recently (not by me, unfortunately):
**********
Subject: Mersenne Prime
From: <[EMAIL PROTECTED]>
Newsgroups: sci.math
Date: Thu, 25 Mar 1999 18:10:30 +0800
Message-ID: <7dd21c$[EMAIL PROTECTED]>
Mp is a Mersenne Prime with odd prime p "iff"
3^((Mp-1)/2)=-1 (mod Mp) .
Please mail to : [EMAIL PROTECTED]
(before 3/30)
**********
At first sight, I thought "that's not right", but a few minutes of testing a
few Mersenne primes and non-prime Mersenne numbers on my TI-92+ has upheld the
"iff". Can anyone find a counterexample? This is bugging me. Augh!
S.T.L.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 26 Mar 1999 00:15:25 +0100 (CET)
From: Henrik Olsen <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Small Conjecture (not mine, sadly).
On Thu, 25 Mar 1999 [EMAIL PROTECTED] wrote:
> The following was posted on sci.math recently (not by me, unfortunately):
> **********
> Subject: Mersenne Prime
> From: <[EMAIL PROTECTED]>
> Newsgroups: sci.math
> Date: Thu, 25 Mar 1999 18:10:30 +0800
> Message-ID: <7dd21c$[EMAIL PROTECTED]>
>
> Mp is a Mersenne Prime with odd prime p "iff"
> 3^((Mp-1)/2)=-1 (mod Mp) .
>
> Please mail to : [EMAIL PROTECTED]
> (before 3/30)
> **********
> At first sight, I thought "that's not right", but a few minutes of testing a
> few Mersenne primes and non-prime Mersenne numbers on my TI-92+ has upheld the
> "iff". Can anyone find a counterexample? This is bugging me. Augh!
> S.T.L.
That looks suspiciously like Proths test, though that would be for fermat
numbers, not mersennes, ie. 2^p+1, not 2^p-1, though the reason why you
seen to find lots of tests that work is because the test is based on
a^((Mp-1)/q)=-1 (mod Mp) where q is a factor of n-1, which works for
both numbers since they have 2 as factor. For Mersenne numbers it's not a
working test, since it must be true for all factors.
For a counter example, try M(3)=2^3-1=7, a mersenne prime though
3^((7-1)/2)=27=6 mod 7
The confusion is probably caused by the Proth test being a socalled N-1
test, because it's based on N-1 being trivially factored.
- --
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: Thu, 25 Mar 1999 18:48:43 -0500
From: Jud McCranie <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Small Conjecture (not mine, sadly).
At 03:30 PM 3/25/99 -0500, [EMAIL PROTECTED] wrote:
>Mp is a Mersenne Prime with odd prime p "iff"
>3^((Mp-1)/2)=-1 (mod Mp) .
This looks like it is just based on Euler's criteria.
+--------------------------------------------------------------+
| Jud McCranie [EMAIL PROTECTED] |
| |
| The problem of distinguishing prime numbers from composites, |
| and of resolving composite numbers into their prime factors, |
| is one of the most important and useful in all of |
| arithmetic. ... The dignity of science seems to demand that |
| every aid to the solution of such an elegant and celebrated |
| problem be zealously cultivated. -- Carl F. Gauss, 1801 |
+--------------------------------------------------------------+
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Thu, 25 Mar 1999 16:32:26 -0800
From: Bob Margulies <[EMAIL PROTECTED]>
Subject: Mersenne: Need info about K6
I have just discovered that my wife is about to be presented with a new
computer which contains a K6-2/333 processor, 64K L1, 512K L2, 64MB of
SRAM. I would be willing to invest a few $$$ of my own in an upgrade to
a Pentium if it made a substantial difference in running Prime95. My
understanding is that the program has been optimized for the Pentium.
The question is - how well does it run on the K6?
Can someone please give me a comparison of the merits of the K6 vs. the
Pentium? Also, please withhold comments on the domestic implications of
the problem.
Thank you.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Thu, 25 Mar 1999 19:28:29 -0500
From: Chris Nash <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Small Conjecture (not mine, sadly).
Hi folks
>Mp is a Mersenne Prime with odd prime p "iff"
>3^((Mp-1)/2)=-1 (mod Mp) .
>**********
>At first sight, I thought "that's not right", but a few minutes of testing
a
>few Mersenne primes and non-prime Mersenne numbers on my TI-92+ has upheld
the
>"iff". Can anyone find a counterexample? This is bugging me. Augh!
>S.T.L.
Well one way is easy. The calculation is actually the quadratic residue
symbol (Euler pseudoprime test) for 3. Since (q|3) depends on q mod 12, and
all Mersennes of odd exponent>=3 are =7 mod 12, then if Mp is prime, the
statement is true.
Conversely if the statement above is true, then Mp is a strong probable
prime to base 3. Now composite probable primes do exist (though they get a
bit thin on the ground), more importantly there are an infinity of
counterexamples given any number of strong probable primality tests. So the
result is not necessarily true *but* a counterexample may be very difficult
to find. However, it's much better than strong probable primality to base 2,
*all* Mersennes of prime exponent, Mp prime or not, are strong probable
prime to base 2.
Most importantly though, the computation required to perform this
calculation is no less than a Lucas-Lehmer test, which gives an absolute yes
or no result.
Chris Nash
Lexington KY
UNITED STATES
=======================================================
Co-discoverer of the 7th and 10th largest known primes.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Thu, 25 Mar 1999 19:47:35 -0600
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Need info about K6
> From: Bob Margulies
> Sent: Thursday, March 25, 1999 6:32 PM
> Can someone please give me a comparison of the merits of the K6 vs. the
> Pentium? Also, please withhold comments on the domestic implications of
> the problem.
It is my crude understanding that the floating point performance of the AMD
chips are slower than on the Pentium core. Since the LL tests are FP
intensive, one would expect chips of the same speed but different
manufacture to differ in iteration speed.
Now we just need someone to post that link to the Prime95 benchmark page
which I always forget...
Aaron
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Thu, 25 Mar 1999 20:59:01 -0500
From: Peter Doherty <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Need info about K6
It's not actually optimized for a Pentium so much as the pentium is
optimized for the kind of math that prime95 does. Prime95 uses the FPU
(Floating Point Unit) extensively. The Pentium and Pentium 2 (and 3) can
do a single FLOP (Flointing Point Operation) per clock cycle. It's a
pipelined FPU. This means a 500MHz Pentium can do abou 500 MegaFLOPs.
The K6 has a less advanced FPU and cannot perform one FLOP each clock
cycle. It's significantly slower...perhaps it works arounf 50-75% of the
speed of the Pentium FPU.
However, the K6-2 has the 3DNow! instruction set (similar to P3's SSE)
Which means that the 3DNow! Unit is basically a high speed but simpler FPU.
The 3DNow! unit is like a RISC processor, it can do less sophicated
things, but do them a lot faster. The unit can pump out 4 FLOPs per clock
cycle. A 500MHz processor can theoretically do 2GigaFLOPs. However, I'm
pretty sure Prime95 isn't coded for 3DNow! or SSE, and therefore this is
irrelvent. It may be impossible to code for 3DNow! if the LL tests require
instructions and code that isn't in the 3DNow! unit. I don't know enough
math or programming to be able to answer that conclusively though.
I don't have first hand knowledge, but can speculate that the K6-2 will
perform at about 50-75% of what a Pentium can do clock for clock. But
since the fastest socket-7 Pentium is 233MHz, and that K6-2 is 333, it
should even out...well...actually the K6-2 will come out ahead. To get
much faster performance you'll have to get at least a 300MHz P2 or Celeron,
but that would require a motherboard upgrade, and that's an extra $100 on
top of the CPU price...
I'd stick with the free K6-2 and enjoy the extra CPU time that will go
towards your account.
:-)
- --Peter
At 16:32 03/25/1999 -0800, you wrote:
>I have just discovered that my wife is about to be presented with a new
>computer which contains a K6-2/333 processor, 64K L1, 512K L2, 64MB of
>SRAM. I would be willing to invest a few $$$ of my own in an upgrade to
>a Pentium if it made a substantial difference in running Prime95. My
>understanding is that the program has been optimized for the Pentium.
>The question is - how well does it run on the K6?
>
>Can someone please give me a comparison of the merits of the K6 vs. the
>Pentium? Also, please withhold comments on the domestic implications of
>the problem.
>
>Thank you.
>________________________________________________________________
>Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
>
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 26 Mar 1999 03:24:36 +0100 (CET)
From: Henrik Olsen <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Small Conjecture (not mine, sadly).
On Fri, 26 Mar 1999, Henrik Olsen wrote:
> On Thu, 25 Mar 1999 [EMAIL PROTECTED] wrote:
> > Mp is a Mersenne Prime with odd prime p "iff"
> > 3^((Mp-1)/2)=-1 (mod Mp) .
> >
> > Please mail to : [EMAIL PROTECTED]
> > (before 3/30)
> > **********
> > At first sight, I thought "that's not right", but a few minutes of testing a
> > few Mersenne primes and non-prime Mersenne numbers on my TI-92+ has upheld the
> > "iff". Can anyone find a counterexample? This is bugging me. Augh!
> > S.T.L.
>
> For a counter example, try M(3)=2^3-1=7, a mersenne prime though
> 3^((7-1)/2)=27=6 mod 7
Paint me embarrased:) 6=-1 mod 7, Parkinson time I guess, and me only 33
years old :)
There are actually no counterexample for p<1500, I've checked them all.
- --
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: Fri, 26 Mar 1999 03:47:15 +0100 (CET)
From: Henrik Olsen <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Need info about K6
On Thu, 25 Mar 1999, Bob Margulies wrote:
> I have just discovered that my wife is about to be presented with a new
> computer which contains a K6-2/333 processor, 64K L1, 512K L2, 64MB of
> SRAM. I would be willing to invest a few $$$ of my own in an upgrade to
> a Pentium if it made a substantial difference in running Prime95. My
> understanding is that the program has been optimized for the Pentium.
> The question is - how well does it run on the K6?
>
> Can someone please give me a comparison of the merits of the K6 vs. the
> Pentium? Also, please withhold comments on the domestic implications of
> the problem.
http://www2.tripnet.se/~nlg/mersenne/benchmk.htm
Though it only has results for the K6, not for the K6-2, but the main
speed advance for K6-2 was in the additional 3DNow! instructions, which
aren't used for prime95, so it should still hold.
- --
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: Thu, 25 Mar 1999 19:28:29 -0500
From: Chris Nash <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Small Conjecture (not mine, sadly).
Hi folks
>Mp is a Mersenne Prime with odd prime p "iff"
>3^((Mp-1)/2)=-1 (mod Mp) .
>**********
>At first sight, I thought "that's not right", but a few minutes of testing
a
>few Mersenne primes and non-prime Mersenne numbers on my TI-92+ has upheld
the
>"iff". Can anyone find a counterexample? This is bugging me. Augh!
>S.T.L.
Well one way is easy. The calculation is actually the quadratic residue
symbol (Euler pseudoprime test) for 3. Since (q|3) depends on q mod 12, and
all Mersennes of odd exponent>=3 are =7 mod 12, then if Mp is prime, the
statement is true.
Conversely if the statement above is true, then Mp is a strong probable
prime to base 3. Now composite probable primes do exist (though they get a
bit thin on the ground), more importantly there are an infinity of
counterexamples given any number of strong probable primality tests. So the
result is not necessarily true *but* a counterexample may be very difficult
to find. However, it's much better than strong probable primality to base 2,
*all* Mersennes of prime exponent, Mp prime or not, are strong probable
prime to base 2.
Most importantly though, the computation required to perform this
calculation is no less than a Lucas-Lehmer test, which gives an absolute yes
or no result.
Chris Nash
Lexington KY
UNITED STATES
=======================================================
Co-discoverer of the 7th and 10th largest known primes.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 26 Mar 1999 18:42:39 -0000
From: "Michael Bell" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Need info about K6
I have a K6-2/300, and it is much slower than a Pentium. I actually
use it for RC5 because it is so slow at LL testing, though I have a
K6/233 doing factoring work. The K6 suffers because a) it can't do
FXCH at the same time as another FP instruction (which Pentium's can),
and also it can only do 1 FP instruction per 2 clocks at full load.
I'd guess the performance is about the same as a P150 (I know coz that
the K6/233 is about the same speed as a P100).
It's a shame that the K6 can't compete with the Pentium here, because
otherwise I find it to be fine for everything I use it for (games esp.)
Michael.
>On Thu, 25 Mar 1999, Bob Margulies wrote:
>> I have just discovered that my wife is about to be presented with a new
>> computer which contains a K6-2/333 processor, 64K L1, 512K L2, 64MB of
>> SRAM. I would be willing to invest a few $$$ of my own in an upgrade to
>> a Pentium if it made a substantial difference in running Prime95. My
>> understanding is that the program has been optimized for the Pentium.
>> The question is - how well does it run on the K6?
>>
>> Can someone please give me a comparison of the merits of the K6 vs. the
>> Pentium? Also, please withhold comments on the domestic implications of
>> the problem.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 26 Mar 1999 15:58:07 -0500
From: Joth Tupper <[EMAIL PROTECTED]>
Subject: Mersenne: Need info about K6
Message text written by INTERNET:[EMAIL PROTECTED]
>I have just discovered that my wife is about to be presented with a new
computer which contains a K6-2/333 processor, 64K L1, 512K L2, 64MB of
SRAM. I would be willing to invest a few $$$ of my own in an upgrade to
a Pentium if it made a substantial difference in running Prime95. My
understanding is that the program has been optimized for the Pentium.
The question is - how well does it run on the K6?
Can someone please give me a comparison of the merits of the K6 vs. the
Pentium? Also, please withhold comments on the domestic implications of
the problem.
<
Well, lots of folks will have something to say on this topic. The rule of
thumb is that the K6-2 at
2x Mhx performs about like a P-II at x Mhz. I have a K6-2 @ 400 and clocks
run about .66. My
P-II at 266 generally has clocks at around .5. Amazingly enough,...
.66 * (400/2)/266 = .5 approx.
Yeah, the P-II is a whole lot faster at some things, just bring an extra
barrel of money.
Joth
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 26 Mar 1999 15:18:26 -0600
From: "Griffith, Shaun" <[EMAIL PROTECTED]>
Subject: Mersenne: Is 2 mod ((2^p) - 1) square?
Benny Van Houdt asked about checking 2 mod Mp for "square-ness". [digest
#537]
The hard way is to square every number from sqrt(Mp) to Mp-1, mod Mp, for
equality to 2. This will take ~`(Mp-sqrt(Mp)) square/mod operations, or
O(Mp)...too long.
Another way to look at this: if x == 2 (mod Mp), then x = kMp+2. X is square
if sqrt(kMp+2) is an integer.
If there was a "square" test, this approach would still take ~Mp tests. What
we need here is some way to construct k, or at least eliminate k's faster
than the growth rate of Mp. I would imagine a "square" test would look a lot
like one of the better factoring algorithms.
- -Shaun
Shaun Griffith, Texas Instruments MSP Multimedia, [EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>
work (972)480-2186, fax (972)480-3555, pager (972)598-6823
alpha pager: [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>
Quantum Mechanics: The dreams stuff is made of
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Fri, 26 Mar 1999 22:42:09 -0500
From: Chris Nash <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Is 2 mod ((2^p) - 1) square?
Hi folks
>Benny Van Houdt asked about checking 2 mod Mp for "square-ness". [digest
>#537]
>The hard way is to square every number from sqrt(Mp) to Mp-1, mod Mp, for
>equality to 2. This will take ~`(Mp-sqrt(Mp)) square/mod operations, or
>O(Mp)...too long.
Just a suggestion to you all... don't take this question at face value.
2^(p+1)/2 is an obvious square root of 2 for odd Mersenne exponent p. (For
even Mersenne exponents, 3 divides Mn, 2 is not a square mod 3, therefore
can't be a square mod Mn).
The point Shaun was aiming for is, if Mp is composite, then 2 has more than
two "square roots" modulo Mp. In fact, it has 2^x square roots, where x is
the number of distinct prime factors of Mp. (2 has two square roots modulo
each prime factor and the result follows from the Chinese remainder
theorem). Hence, find one of the non-obvious square roots, and you'll be
able to deduce a factor.
Quick example, 2 has square roots 64 and -64 modulo 2^11-1. But it also has
the less obvious ones 915 and -915. Do a gcd calculation of 2^11-1 with
915+64 and 915-64, and the factors 23 and 89 will appear. (since these other
roots must be equal to one or other of the more obvious ones modulo some
prime factor).
As far as looking for such solutions goes, you could attempt the following
method. Attempt to solve x^2-Dy^2=2, where D=Mp. Such a solution will have
x/y a good rational approximation to sqrt(D), and such good rational
approximations can be generated by continued fractions. However, there's no
guarantee that if you find a solution, it isn't one of the known ones, not
to mention the method involves some rather hairy manipulation of quadratic
surds. The method has been used in the past (by I think Pollard) to generate
several relatively small quadratic residues modulo some composite N as an
aid to factoring. As here, the idea is to find two numbers a and b so
a^2=b^2 mod N, then examining (a-b) and (a+b) for common factors with N. Not
for the faint-hearted either - the residues generated may still be as large
as sqrt(N) and may themselves require factoring before two equal squares
modulo N are found.
Chris Nash
Lexington KY
UNITED STATES
=======================================================
Co-discoverer of the 7th and 10th largest known primes.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Tue, 30 Mar 1999 10:40:51 GMT
From: "Brian J Beesley" <[EMAIL PROTECTED]>
Subject: Mersenne: Database file format
Hi,
A couple of weeks ago George started putting up the database files
lucas_v and hrf3 in zip format, they used to be ASCII text.
My anonymous ftp server (lettuce.edsc.ulst.ac.uk, aka
193.61.169.253) is now carrying the files in both zipped and ASCII
text format. Note that this is a unix system, please use ASCII
mode transfer to upload txt files, else you will have to change all
the linefeeds to linefeed/carriage return pairs. You must use binary
mode transfer for all other files, else they won't unpack or execute.
I try to keep the files up-to-date but may be a day or two behind the
master versions on entropia.com.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
End of Mersenne Digest V1 #538
******************************
