Mersenne Digest Monday, May 17 1999 Volume 01 : Number 560
----------------------------------------------------------------------
Date: Sun, 16 May 1999 20:47:31 -0500
From: Amy and Shane Sanford <[EMAIL PROTECTED]>
Subject: RE: Mersenne: I am curious
At 09:56 AM 5/15/99 +0200, Henrik Olsen wrote:
>> Just out of interest, can I have someone demand I give them a share of the
>> money / stop being in GIMPS if they really wanted to (not that I should
>> think they would...)
>
>One thing most people seems to have forgotten when it comes to talk about
>the money, is that according to the common scientific discovery rules
>George Woltman and Scott Kurowski will be co-discoverers of all primes
>found using mprime/prime95, and the client/server setup, so should
>rightfully get a big part of the money.
>From a legal stand point I think George & Scott may have "signed" away most
of their rights to the money (not the discovery rights though) by
advertising on their web page that participating in GIMPS could win you
$50,000. It certainly seems to imply that from my read anyway...
Of course on the strictly ethical side of things I think George & Scott
deserve something for their troubles. Personally I feel that I would give
a portion of the money back to GIMPS but then again that is easy to say
when dealing with purely theoretical money ;-) I would think that > 95% of
the people here are involved with GIMPS for non monetary reasons, I would
go so far as to say noble reasons, (especially the founders of GIMPS who
have put in so much time and effort over the years). Sadly even the most
noble of pursuits are often spoiled by squabbling over the "brass ring".
Shane Sanford
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sun, 16 May 1999 18:50:02 -0700
From: Jiho Kim <[EMAIL PROTECTED]>
Subject: Mersenne: Rather naive question
How exactly are the exponents to be tested chosen? It must be prime, of
course, and so do we just test all prime exponents? Or is there a further
effort that GIMPS makes to weed out mersenne composites with prime
exponents?
Just wondering,
J.K.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sun, 16 May 1999 20:24:05 -0600
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: cacheable memory
> Anybody know which chipsets have the memory caching
> problems, or who can point me in the direction to find this
> information?
>
> I am interested in finding out whether to add memory to a
> VXPro board, currently has 32MB, AMD K-6 200.
I think it was just the 430TX chipset. It has the problem of not cacheing
anything above 64MB, and due to the way Windows uses memory, it can really
hurt performance.
Other chipsets like the 430VX, 430HX, etc. are okay, and PII chipsets in the
440xx series are all fine.
Other chipsets from non-Intel sources (VIA, etc.) I have no idea about, but
Intel chipsets make up a vast majority of system boards.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sun, 16 May 1999 20:27:49 -0600
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Rather naive question
> From: Jiho Kim
> Subject: Mersenne: Rather naive question
>
> How exactly are the exponents to be tested chosen? It must be prime, of
> course, and so do we just test all prime exponents? Or is there a further
> effort that GIMPS makes to weed out mersenne composites with prime
> exponents?
Good question. Primenet itself gets an allocation of exponents to check out
every time Scott and George do a database synchronization. To my knowledge,
George keeps the best track of what exponents have and have not been tested
as part of the GIMPS project. I'm not sure how many other non-GIMPS folks
are doing testing, but I'd hope that they work with George on who is testing
what exponents.
As for weeding out, basically it's just the trial-factoring. Each exponent
is trial-factored up to a certain bit size (based on the size of the
exponent) to eliminate (relatively) small factors. If a factor is found,
it's obviously not tested with the LL test.
Other than that, they all have to be looked at.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 05:54:26 +0300 (EET DST)
From: Sam Laur <[EMAIL PROTECTED]>
Subject: Re: Mersenne: cacheable memory
> Anybody know which chipsets have the memory caching
> problems, or who can point me in the direction to find this
> information?
Well, you can always search the net (try altavista: +430vx +cacheable)
If it has the VX chipset from Intel, then it can only cache up to 64 MB.
The 430HX chipset could cache up to 512 MB, but even then you need to add
more tag RAM to the motherboard (it usually isn't there as standard...)
http://asus1.ingenuity.net/support/mb/answers/memory/VX.asp
Question:
Why can VX memory cacheable size be only up to 64MB?
Answer:
FX and VX can only provide 8 bit tag. Therefore,
i) Cache size = 256K. Tag bit = 8 bit.
Cacheable size = 2^8 x 2^18 = 64M
ii) Cache size =512K. Tag bit = 7. ( 1 for valid bit or dirty bit )
Cacheable size = 2^7 x 2^19 =64MB
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sun, 16 May 1999 23:14:51 -0400
From: Peter Doherty <[EMAIL PROTECTED]>
Subject: RE: Mersenne: cacheable memory
I'm quite sure the VX chipset has the same problem, and is limited to 64MB
cacheable
The Pentium2 with an older core can cache 512MB of RAM, but the newer ones
can cache 4GB of RAM. The Celerons can also all cache 4GB of RAM.
Most other chipsets cache different amounts depending on the L2
cache...with 512K cache most of those chipsets cache 64MB or 128MB...but
most cache at least 128MB and higher....
- --Peter
At 20:24 05/16/1999 -0600, you wrote:
>> Anybody know which chipsets have the memory caching
>> problems, or who can point me in the direction to find this
>> information?
>>
>> I am interested in finding out whether to add memory to a
>> VXPro board, currently has 32MB, AMD K-6 200.
>
>I think it was just the 430TX chipset. It has the problem of not cacheing
>anything above 64MB, and due to the way Windows uses memory, it can really
>hurt performance.
>
>Other chipsets like the 430VX, 430HX, etc. are okay, and PII chipsets in the
>440xx series are all fine.
>
>Other chipsets from non-Intel sources (VIA, etc.) I have no idea about, but
>Intel chipsets make up a vast majority of system boards.
>
>________________________________________________________________
>Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Sun, 16 May 1999 21:05:42 -0700
From: "Aaron Schaufenbuel" <[EMAIL PROTECTED]>
Subject: Mersenne: SETI@HOME & GIMPS
Just a thought, but since SETI@HOME is only actually using the computer when its
screensaver is on, maybe we could convince the SETI programmers to incorporate Prime95
into the SETI@HOME program to run when the screen saver isn't and have those computer
doing factoring or double checking... It might be worth a try?
"So, look on the bright side, my mathematical friends. We are mapping
the mathematical landscape every time we discover a new Mersenne
composite, even if they are as common as grains of sand on the
beach. Of course we want to find the diamonds, but to do so
requires sifting the sand. When we map this landscape, it is the
same for all time and all the universe. SETI@home is making a
map of sorts too. Let us wish them well and continue. spike"
I agree, both are good projects. I'm very interested in SETI and whould love to see
it succeed, but as soon as it finished its chunk of data, this computer is going back
to searching for a needle in a haystack that we know is there (in other words, I'm
going back to GIMPS). Good Luck everyone!
- ---Aaron Schauf---
[EMAIL PROTECTED]
"Absence of evidence is not evidence of absence"-Carl Sagan
Free web-based email, anytime, anywhere!
ZDNet Mail - http://www.zdnetmail.com
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 02:15:51 -0400 (EDT)
From: lrwiman <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Repeating LL remainders
all,
>Assuming the LL residues are pseudorandom,
Big assumption, here are the first 10 remainders for n=101 (in binary, of course):
1110
11000010
1001001100000010
1010100011010110100110000000010
1101111010110100101101101100111110000001111010011000000000010
10010100001011110111010101101011111011000110011001000100001000000011110101010000011001111011110111111
11000010111111001001011110011011111011011100111110011101110110000101101101110111111011011111001001000
11100010011000110101110001010000110011110000100100000010001010010010101101011100010000101110101100001
11011110101011110010101001010100001000100100111110011011100011101100011001111101111011110010110111011
They hardly look random, but this is hardly conclusive
>then the repetition length should
>be on the order of sqrt(2^n - 1) =~ 2^(n/2) which is veeeeeery big. It
>doesn't seem likely that any repetition will occur, even in testing googols
>of exponents...
Here is an "intuitive" argument:
We start out with a power of 2: 4
we then proceed to square, subract 2
then we take mod to a series of 1's (in binary), lather rinse and repeat.
The actual l_n values would surely not be random, always ending in 10b, and the
strings of zero's in then would just get longer and longer.
Taking mod a number is (basically) subtraction, and subtracting series of 1b's
wouldn't seem to change the "randomness" of the number.
Also, remember our lord and savior (knuth) said (somewhere in Vol. 2 in the section on
random #'s) "random numbers are not produced through the appication of random
proceses." Just because these operations may seem to have only a tenative
relationship to each other, does not mean that they produce random numbers.)
Best I could come up with ;-). I think that the best course of action would be
to try and find numbers where the remainder actually does repeat (should any exist.)
When checking, we should consider exponents were all the remainders can be saved. The
size of saving all the exponent, in bits is ~n*(n-1), so keeping it <10MB, solve the
quadratic eq. n^2-n-10*8*1024*1024=0, so n is ~9159.
Would anyone be willing to write the code to test this? (I would, but my programing
skills are less than enough, I will however loan my CPU cycles)
- -Lucas
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 00:31:06 -0700
From: Kevin Sexton <[EMAIL PROTECTED]>
Subject: Re: Mersenne: cacheable memory
- --------------A0FB27369E55B08C6F9BFDBA
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Here is some more information, it is a Matsonic board (MS-5120),
but OEM, and the computer maker is gone, so no support. I was
trying to find out if it would be advisable to get 64 MB (2x 32
MB EDO simms) and add it, or keep to just 64 MB total. I am also
going to try to upgrade the bios soon.
< General Computer Information >
Type: Standard PC
Class: IBM PC/AT
System Bus(es): ISA(16-bit),
PCI(32-bit)
Fast Windows System: Yes
< Special Mainboard Information >
Name: Release 07/07/1997 S
Unique ID: 07/04/97-VXPro
< Chipset Information >
System Chipset: VIA Tech VT82C585
Apollo Chipset,
Pentium to PCI Bridge
L2 External Cache: 512KB pipeline-burst
write-back
< Logical Memory Banks Information >
Memory Bank 4: 32MB
< System BIOS Information >
Manufacturer: Award
Version: Award Modular BIOS
v4.51PG
Date: 07/04/97
Plug & Play Version: 1.00
ID No.: FC 01 00
- --------------A0FB27369E55B08C6F9BFDBA
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<tt>Here is some more information, it is a Matsonic board (MS-5120), but
OEM, and the computer maker is gone, so no support. I was trying to find
out if it would be advisable to get 64 MB (2x 32 MB EDO simms) and add
it, or keep to just 64 MB total. I am also going to try to upgrade the
bios soon.</tt><tt></tt>
<p><tt> < General Computer Information ></tt>
<br><tt>
Type:
Standard PC</tt>
<br><tt>
Class:
IBM PC/AT</tt>
<br><tt> System
Bus(es):
ISA(16-bit), PCI(32-bit)</tt>
<br><tt> Fast Windows
System:
Yes</tt><tt></tt>
<p><tt> < Special Mainboard Information ></tt>
<br><tt>
Name:
Release 07/07/1997 S</tt>
<br><tt> Unique
ID:
07/04/97-VXPro</tt><tt></tt>
<p><tt> < Chipset Information ></tt>
<br><tt> System
Chipset:
VIA Tech VT82C585 Apollo Chipset,</tt>
<br><tt>
Pentium to PCI Bridge</tt>
<br><tt> L2 External
Cache:
512KB pipeline-burst write-back</tt><tt></tt>
<p><tt> < Logical Memory Banks Information ></tt>
<br><tt> Memory Bank
4:
32MB</tt>
<br><tt></tt> <tt></tt>
<p><tt> < System BIOS Information ></tt>
<br><tt>
Manufacturer:
Award</tt>
<br><tt>
Version:
Award Modular BIOS v4.51PG</tt>
<br><tt>
Date:
07/04/97</tt>
<br><tt> Plug & Play
Version:
1.00</tt>
<br><tt> ID
No.:
FC 01 00</tt>
<br><tt></tt> </html>
- --------------A0FB27369E55B08C6F9BFDBA--
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 08:03:21 -0000
From: [EMAIL PROTECTED]
Subject: Re: Mersenne: Rather naive question
>> How exactly are the exponents to be tested chosen? It must be prime, of
>> course, and so do we just test all prime exponents? Or is there a further
>> effort that GIMPS makes to weed out mersenne composites with prime
>> exponents?
>
>Good question. Primenet itself gets an allocation of exponents to check out
>every time Scott and George do a database synchronization. To my knowledge,
>George keeps the best track of what exponents have and have not been tested
>as part of the GIMPS project. I'm not sure how many other non-GIMPS folks
>are doing testing, but I'd hope that they work with George on who is testing
>what exponents.
Or, at least, reports the results to George.
>
>As for weeding out, basically it's just the trial-factoring. Each exponent
>is trial-factored up to a certain bit size (based on the size of the
>exponent) to eliminate (relatively) small factors. If a factor is found,
>it's obviously not tested with the LL test.
>
>Other than that, they all have to be looked at.
I think it's been pointed out before that exponents which are Sophie Germain
primes can't possibly give rise to a Mersenne prime. However they are bound
to have a small factor, so it's not worth doing an explicit test for Sophie
Germain'ness.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 08:14:18 -0000
From: [EMAIL PROTECTED]
Subject: Re: Mersenne: Repeating LL remainders
>> A couple of weeks ago, there was discussion about repeating remainders in
>> the LL test. There was general agreement that this would be technically
>> unworkable due to the fact that the remainders are so large. Wouldn't it
>> be possible to store the last 1024 binary digits of the remainder (saving
>> 1024 of these would be only 1MB, not a big deal.)
I make 1024 bits 128 bytes - so you could save 8192 of them in a megabyte...
>> Then we could check for
>> repeating remainders in the last 1024 iterations, without signifigantly
>> restraining performance.
No, because the remainder is modulo 2^p-1, the period could repeat after
more than 1024 iterations if you're just keeping 1024 bits.
Actually I would consider keeping just 64 bits, the chance of getting an
"accidental" match in say 4 million (~2^22) iterations would be only 1 in
2^42 - so, in the rare case that you did get a "hit", you could compute
again & compare the whole residual at the actual iteration counts found,
without too much wasted time or too many false alarms. (Same thing really)
>>If it actually repeated, it could be confirmed in
>> double-checking quite easily.
>
>Once a remainder repeats, does it stay in a loop? If so, you can keep the
>remainder when the iteration number is a power of 2, and detect much longer
>loops.
Must stay in a loop since the test is deterministic - there's no random
element involved (except as a result of a computation error).
(x^2 - 2) mod (2^p - 1) depends on x and p only, and p is fixed.
I don't quite see how this makes it unneccessary to check only iteration
numbers which are powers of 2. How long does it take to find a cycle
length of, say, 127 if you're sampling only powers of 2?
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 01:20:47 -0700
From: Jiho Kim <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Rather naive question
When a machine is assigned "factoring" is that what it's doing? Or are they
trying to find as many factors for known composite as they can? I was
wondering how laborious preliminary testing for exponents are. As exponents
get bigger and as current computer in GIMPS outlive their usefulness, higher
exponents can be sieved somehow up to say the the millionth prime...
Just a thought.
- -----Original Message-----
From: Aaron Blosser <[EMAIL PROTECTED]>
To: Mersenne@Base. Com <[EMAIL PROTECTED]>
Date: Sunday, May 16, 1999 7:41 PM
Subject: RE: Mersenne: Rather naive question
> From: Jiho Kim
> Subject: Mersenne: Rather naive question
>
> How exactly are the exponents to be tested chosen? It must be prime, of
> course, and so do we just test all prime exponents? Or is there a further
> effort that GIMPS makes to weed out mersenne composites with prime
> exponents?
Good question. Primenet itself gets an allocation of exponents to check out
every time Scott and George do a database synchronization. To my knowledge,
George keeps the best track of what exponents have and have not been tested
as part of the GIMPS project. I'm not sure how many other non-GIMPS folks
are doing testing, but I'd hope that they work with George on who is testing
what exponents.
As for weeding out, basically it's just the trial-factoring. Each exponent
is trial-factored up to a certain bit size (based on the size of the
exponent) to eliminate (relatively) small factors. If a factor is found,
it's obviously not tested with the LL test.
Other than that, they all have to be looked at.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 09:50:10 +0100
From: Robin Stevens <[EMAIL PROTECTED]>
Subject: Re: Mersenne: cacheable memory
On Sun, May 16, 1999 at 05:22:59PM -0700, Mersenne Digest wrote:
> Date: Sun, 16 May 1999 16:57:08 -0700
> From: Kevin Sexton <[EMAIL PROTECTED]>
>
> Anybody know which chipsets have the memory caching problems, or who can
> point me in the direction to find this information?
Intel chipsetted Pentium boards are the chief offenders: the FX, VX and TX
all being unable to cache more than 64MB. Some HX boards can cache up to
512MB by default, others require additional tag RAM to cache above 64MB.
Some HX boards (like mine) don't have a socket for inserting tag RAM :-(
If you have one of the more recent Socket7/Super7 chipsets from SiS or VIA,
I believe they'll happily cache up to 256MB or 512MB. Pentium IIs are fine
up to 512MB IIRC, so it'll probably be a year or two before that becomes a
problem for significant numbers of people.
I've just put my P200MMX system up from 64MB to 160MB and find the impact
on GIMPs performance under Linux to be at about the 2% level, which I can
live with. To be fair I am doing double checking on this machine - the
performance drop may be greater for exponents in the 7-8 million range than
for those around 3 million.
> I am interested in finding out whether to add memory to a VXPro board,
> currently has 32MB, AMD K-6 200. I know this is not strictly on topic,
> but it might increase performance of prime95, especially if another app
> hogs the memory I have now.
It's probably worth it - 32MB is not a lot these days ;-)
- --
- -------------------- Robin Stevens <[EMAIL PROTECTED]> --------------------
Merton College, Oxford OX1 4JD, UK http://www-astro.physics.ox.ac.uk/~rejs/
(+44) (0)1865: 726796 (home) 273337 (work) 273390 (fax) Pager: 0839 629682
"He's dead Jim." "I know, Bones. I've seen the script"
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 09:20:59 -0000
From: [EMAIL PROTECTED]
Subject: Re: Mersenne: Repeating LL remainders
>Best I could come up with ;-). I think that the best course of action would be
>to try and find numbers where the remainder actually does repeat (should any
exist.)
>When checking, we should consider exponents were all the remainders can be saved.
The size of saving all the exponent, in bits is ~n*(n-1), so keeping it <10MB, solve
the quadratic eq. n^2-n-10*8*1024*1024=0, so n is ~9159.
>
>Would anyone be willing to write the code to test this? (I would, but my programing
>skills are less than enough, I will however loan my CPU cycles)
I think we should check the math first. I have a sneaky suspicion that looping
won't occur in the relevant region (the first 2^n-3 iterations) unless n is
composite - which may be interesting, but doesn't help us eliminate Mersenne
numbers as candidate primes. But my math is inadequate to prove this 8-(
If no-one else can patch the math, then the brute force method may be
indicated, though (unless we start finding loops early) we could potentially
"waste" a lot of time looking for the unfindable.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 08:14:39 -0400
From: "Pierre Abbat" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Repeating LL remainders
> I don't quite see how this makes it unneccessary to check only iteration
> numbers which are powers of 2. How long does it take to find a cycle
> length of, say, 127 if you're sampling only powers of 2?
Let's say you have a cycle of length 127 beginning at 992. You keep 1, 2, ...
1024. When you get to 1151, you see it's the same as 1024, and you know you
have a cycle.
phma
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 08:24:07 -0400
From: "Pierre Abbat" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Screen saver killers?
> The script runs when there's a logged
> in user.
Put it in the crontab; it'll run whether or not you're logged in.
phma
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 09:19:50 -0400
From: Jud McCranie <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Rather naive question
- --=====================_40943039==_.ALT
Content-Type: text/plain; charset="us-ascii"
At 01:20 AM 5/17/99 -0700, Jiho Kim wrote:
>When a machine is assigned "factoring" is that what it's doing? Or are they
>trying to find as many factors for known composite as they can?
No, it is trying to find 1 small factor to avoid having to do the Lucas-Lehmer
test.
- --=====================_40943039==_.ALT
Content-Type: text/html; charset="us-ascii"
<html>
<font size=3>At 01:20 AM 5/17/99 -0700, Jiho Kim wrote:<br>
>When a machine is assigned "factoring" is that what it's
doing? Or are they<br>
>trying to find as many factors for known composite as they can?
<br>
<br>
No, it is trying to find 1 small factor to avoid having to do the
Lucas-Lehmer test.<br>
</font></html>
- --=====================_40943039==_.ALT--
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 11:11:00 -0300 (EST)
From: "Nicolau C. Saldanha" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Back to the maths of primes for a sec....
On Sun, 16 May 1999, Chris Jefferson wrote:
> Sorry, just a quick question!
> In various places, I have read that the generalized Riemann hypothesis is
> true, then there is a very simple test for primeness, namely if n is an
> a-SPRP for all integers a<2(log n)^2, then n is prime. From a computation
> viewpoint, is this actually of any use, as it will show if numbers are
> composite and if it is quick, then primes could be checked using it, then
> double checked via another means, also giving the opportunity to disprove
> a major hypothesis of maths...
Just adding a reference and a related question...
This test is known as Miller's test.
You can read about it in Caldwell's excellent home page about prime
numbers: http://www.utm.edu/research/primes/
The exact location of the reference to Miller's test there is
http://www.utm.edu/research/primes/prove/prove2.html#sprp
Most mathematical programs/packages (maple, gmp, ...)
which are capable of dealing with large integers
have a "probably_prime" function.
The documentation usually does not explain exactly what the algorithm is.
I could be wrong, but I think these are a-SPRP tests,
possibly Miller's test itself. Does anyone know for sure?
As to the idea of using it to try to disprove grh,
the best thing would be for cryptography programs which routinely
generate relatively big "probably prime" numbers to use Miller's test
and keep an eye on possible failures. It would probably be hard to
convince people to introduce that feature, though...
http://www.mat.puc-rio.br/~nicolau
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 16:11:54 -0400 (EDT)
From: lrwiman <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Repeating LL remainders
all,
>I think we should check the math first. I have a sneaky suspicion that looping
>won't occur in the relevant region (the first 2^n-3 iterations) unless n is
>composite - which may be interesting, but doesn't help us eliminate Mersenne
>numbers as candidate primes. But my math is inadequate to prove this 8-(
I think that you mean n-2 iterations, but you may be right. It's hard to
say, without any evidence, or solid math.
Just a side note, but all l_n values are 2 after n-1 iterations on a mersenne
prime. Maybe lends some small bit of evidence against that...
- -Lucas
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 18:41:07 -0400 (EDT)
From: lrwiman <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Repeating LL remainders
all,
>I don't quite see how this makes it unneccessary to check only iteration
>numbers which are powers of 2. How long does it take to find a cycle
>length of, say, 127 if you're sampling only powers of 2?
I wasn't saying that we should keep the checking only in powers of 2,
I was just using powers of 2 as nice big round numbers (I usually use these
rather than multiples of 10.)
- -Lucas
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 21:01:00 -0400
From: Chris Nash <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Back to the maths of primes for a sec....
> > In various places, I have read that the generalized Riemann hypothesis
is
> > true, then there is a very simple test for primeness, namely if n is an
> > a-SPRP for all integers a<2(log n)^2, then n is prime. From a
computation
> > viewpoint, is this actually of any use, as it will show if numbers are
> > composite and if it is quick, then primes could be checked using it,
then
> > double checked via another means, also giving the opportunity to
disprove
> > a major hypothesis of maths...
The theorem tells us, that since the SPRP test is polynomial in log n, and
the expected number of tests required is also polynomial, then, if GRH is
true, we have a deterministic primality test in polynomial time. At the
moment, the best verifiable polynomial-time tests are merely "probable
prime". For an arbitrary number "probable prime" is "pretty good", but proof
is elusive. I'll define "pretty good" in a moment.
> Most mathematical programs/packages (maple, gmp, ...)
> which are capable of dealing with large integers
> have a "probably_prime" function.
> The documentation usually does not explain exactly what the algorithm is.
> I could be wrong, but I think these are a-SPRP tests,
> possibly Miller's test itself. Does anyone know for sure?
The initial test in MAPLE was quite weak (in relative terms) and was a
probable primality test, perhaps only PRP. After it was used quite
excessively, its weakness was found - and the function would return "prime"
for a large class of composites. Generally "probable prime" is pretty
tough - an n-digit probable prime is composite with probability around
10^(-n/10), due to research by Pomerance et al. Their results are somewhere
on Chris Caldwell's wonderful site. While this probability is minute beyond
human comprehension - less likely than hardware/software/programmer/user
error! - it isn't proof, because a larger class of composites are "probable
prime" to the test. For instance, all Mersennes of prime exponent are 2-PRP.
The test is now tougher. If MAPLE now identifies a probable prime, it tests
again, to another base, and if that also passes, it performs a test using a
Lucas sequence. Again these are probable prime tests, so it is possible (and
likely) composites exist that pass all three. I think Carl Pomerance himself
has offered a cash prize for anyone who could find a counterexample to the
"twice SPRP, one Lucas sequence" test - an indication that it is not an easy
task of mere computation.
> As to the idea of using it to try to disprove grh,
> the best thing would be for cryptography programs which routinely
> generate relatively big "probably prime" numbers to use Miller's test
> and keep an eye on possible failures. It would probably be hard to
> convince people to introduce that feature, though...
Is "probable prime" enough? Practically, perhaps yes. Mathematically,
obviously not!
Chris Nash
Lexington KY
UNITED STATES
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
Date: Mon, 17 May 1999 21:16:30 -0400
From: Chris Nash <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Repeating LL remainders
> >I think we should check the math first. I have a sneaky suspicion that
looping
> >won't occur in the relevant region (the first 2^n-3 iterations) unless n
is
> >composite - which may be interesting, but doesn't help us eliminate
Mersenne
> >numbers as candidate primes. But my math is inadequate to prove this 8-(
> I think that you mean n-2 iterations, but you may be right. It's hard to
> say, without any evidence, or solid math.
Think of it like this.
Define L(n)=(2+sqrt(3))^n+(2-sqrt(3))^n. It turns out that what we usually
call *the* Lucas sequence is just
S(n)=L(2^n).
The whole point of the proof is to show that the set of elements a+b.sqrt(3)
(a, b mod N) that form a closed group under multiplication has the maximal
order, N^2-1, and thus N is prime. The Lucas sequence does this with a
little jiggery-pokery, because it is sufficient to show that L(N+1) is zero,
while L((N+1)/q) isn't for any prime factor q of N+1. For Mersenne numbers
the only factor to worry about is 2, so the test collapses into its briefer
form.
So the question becomes one of solving (2+sqrt(3))^n has zero surd part, and
in fact prove that the group does not have order N^2-1. The sequence L(n)
"will" recur in that case. However, it is not difficult to prove that the
"first" recurrence, ie the point where L(x)=L(1), will generally occur quite
late in the sequence unless N has all small factors - in which case, we
would have eliminated this N by trial factoring.
Remember too, this is late in the "L" sequence, not in the S sequence!
Suppose for instance it occurred between L(2^(n-3)) and L(2^(n-2)) - which,
even assuming the "first" recurrence is equally likely anywhere, would occur
with probability 50%. The S-sequence would not even see it.
In short, it doesn't matter how you buffer the S-sequence. Suppose you
recorded every residue, that's n-2 steps. There are only (n-2)^2 possible
differences, while in theory the recurrence length could be any of O(N)
lengths. The odds of success are small, we'll call them practically
non-existent. If we are testing M(10,000,000+), then we could at most get
10^14 differences, while the number is as big as 10^3000000.
The odds of a recurrence occurring make the odds of finding a prime seem
positively good!
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: Mon, 17 May 1999 23:12:06 -0500
From: Greg Czajkowski <[EMAIL PROTECTED]>
Subject: Mersenne: Linux Mprime how to Auto Dialup?
This is a multi-part message in MIME format.
- --------------0CA8ED733B1DB36B601DF36A
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Hi, I have a question to the linux/mprime experts:
I just installed RedHat 6.0, (it's awesome) but the only connection
that machine has to the internet is PPP.
Eventually, I got that to work. My question is whether there is any way
to bring down/up the ppp0 interface whenever mprime needs to contact
PrimeNet server automatically?
The only way I can think of is having a script monitor the optional
STDOUT of mprime and then checking whether it needs to contact the
server.
If there is a better solution, please point me to it.
Thanks.
- --
- ----------------------------------------------------------------------
Greg Czajkowski
College of Engineering
Computer Engineering BS 1999
University of Illinois at Champaign/Urbana
http://www.cen.uiuc.edu/~gczajkow
http://www.cyberconnect.com/chico
[EMAIL PROTECTED] "Time has no Patience"-GZ
- ----------------------------------------------------------------------
- --------------0CA8ED733B1DB36B601DF36A
Content-Type: text/x-vcard; charset=us-ascii;
name="gczajkow.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for Greg Czajkowski
Content-Disposition: attachment;
filename="gczajkow.vcf"
begin:vcard
n:Czajkowski;Greg
tel;home:(217) 332-4152
tel;work:(217) 333-7341
x-mozilla-html:TRUE
adr:;;;;;;
version:2.1
email;internet:gczajkow ___AT___ students.uiuc.edu
x-mozilla-cpt:;-32096
fn:Greg Czajkowski
end:vcard
- --------------0CA8ED733B1DB36B601DF36A--
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
------------------------------
End of Mersenne Digest V1 #560
******************************
