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
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
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
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
Re: Mersenne: Rather naive question
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.
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 a2(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
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
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 a2(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
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^300. 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
Mersenne: Linux Mprime how to Auto Dialup?
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 -- 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
Mersenne: Re: Mersenne Digest V1 #560
I can see two possible ways offhand, neither of which I have tested. 1. Rather than watching stdout, check for prime.spl or whatever the spool file is named existing and having a size 0, then spawn pppd. This is a simpler script, but you'll need to adjust the retry interval so that it contacts the server before the ppp link idles out. 2. Use diald, or a similar demand-dialing daemon and do nothing, it will automatically connect whenever you use any network socket. Beware, however, that demand-dialed analog connections usually take so long to connect that the system call will probably time out the first try. Again, the solution is to keep a relatively small retry interval in mprime. Hi, I have a question to the linux/mprime experts: [...] 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. Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
