Mersenne: Base-3 Pseudoprimes
I was wondering if base-3 pseudo-prime testing might be considerably faster than LL testing for Mersenne Primes ? The base-3 pseudo-prime test is defined as :- 3 ^ P == 3 (mod P) where P is a probable-prime (base-3 prp) 3 ^ P 3 (mod P) where P is composite We know that using binary exponentiation saves having to calculate every power of 3, just some intermediates and the final required answer ... e.g. For M(3) = 7, (111 in binary), starting with the value 3, square, multiply by 3, square, multiply by 3 This is effectively 4 multiplys to get our answer. If we used this modified form of the test :- 3 ^ (P+1) == 9 (mod P) then we'd only need 3 multiplys i.e. starting with value 3, square, square, square. This situation improves with higher exponents i.e. M(13) = 8191, (1 in binary). Usual method takes 24 multiplys, modified method only takes 13 multiplys. i.e.for a given Mersenne Exponent, usual method takes (Exp * 2) - 2 multiplies, modified method takes (Exp) multiplys. Now, okay, this is still 2 more multiplys than the LL test would take. But I believe there must be some advantages. 1) For the LL test using FFT multiplys, we have to Transform the data, Multiply the matrices, Inverse Transform the data, then subtract 2. I am assuming that the only reason we do the Forward and Inverse Transform each time is so we can subtract the 2 ? Please correct me here if I'm wrong ! (by the way, I would appreciate some pointers to FFTs for large integer multiplication for idiots - I understand the (very) basic concept, but how does the modulus occur automatically, why do we need to scramble the data, why does it all work etc.) 2) If we are doing base-3 prps, the only operation we need is multiply - so therefore we Transform the start value 3, then multiply the matrix by itself as many times as required, then finally do one Inverse Transform. This must save a lot of time over traditional LL testing, all those Transforms jumping in and out of virtual memory (a lot of us don't have 128+ MB of RAM !!). 3) The base-3 prp does not prove primality 100%, but it does prove compositeness. So we might narrow down our range of potential Mersenne exponents more quickly. And if if turns out that when we test the remaining exponents, the LL test fails - what the hell, we just found a new Carmichael Number - might still be a new record !! Dave
Subject: Re: Mersenne: pi
Date: Wed, 09 Feb 2000 10:50:44 -0500 From: Jeff Woods [EMAIL PROTECTED] Subject: Re: Mersenne: pi You're bumping up against the Fundamental Theorem of Calculus here. Pi DOES have a precisely defined value, but you cannot express it in decimal form. You can express it as an infinite expansion, however. This is partially correct, but a more intuitive explanation is that: Pi is defined as the ratio of Perimeter to Diameter of a circle. ( Pi*D/D ) Since a circle can be considered as a polygon of infinite number of sides, it follows that the perimeter is not finite and Pi is not precise accordingly. Noel Casey _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: non-synchronized old results
I missed the answer in the digest to the question regarding old results that are left in your Primenet account after a synchronization. I, too, have wondered about these accumlating old results (although I just checked my Account Report and they all have miraculously disappeared). Are those "legacy" exponents counted in your P90 years? Had they been (NOT to reopen this thread) poached or reassigned in some other way? -steve grupp _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: non-synchronized old results
Hi, At 09:20 AM 2/10/00 -0500, Stephan Grupp wrote: I missed the answer in the digest to the question regarding old results that are left in your Primenet account after a synchronization. I, too, have wondered about these accumlating old results (although I just checked my Account Report and they all have miraculously disappeared). Are those "legacy" exponents counted in your P90 years? Had they been (NOT to reopen this thread) poached or reassigned in some other way? This will take a little explaining A database merge is done using the binary database format that only the old-time GIMPSers remember. The Primenet server removes results from the cleared exponents report if the exponent is no longer in the binary database. Unfortunately this algorithm has a flaw. The exponent may still be in the binary database - only now it is marked for double-checking. So even though you properly did a first-time check, the exponent is still in the database, and your line still appears in the cleared exponents report. At present the binary database has data on all exponents below 7 million that need double-checking. In the past it had been 5 million, so not all result lines between 5 million and 7 million were saved. Furthermore, buggy v17 results hung around for quite a while because the exponent was not removed from the binary database for obvious reasons. Now, why did these old lines recently disappear? That's a completely different issue! The prime95 client sends two result messages to the server for every LL test. One is an easy to use C structure that the server uses to update its databases. The other is a text message (identical to the results.txt line) that I download once a week and update my database. Once in a great while I plow through the cleared exponents report and see if the primenet server database has results that I am missing (there were 5 since last May). I've emailed the 5 users in hopes of getting them to email the results.txt file to me. I also told Scott to purge the cleared exponents report of all results sent in prior to Feb 1, 2000. Obviously this isn't the cleanest way for Scott and I to maintain our databases. It developed this way partly for historical reasons and partly due to constraints on our free time. Best regards, George _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Pi and Greek
I just found out that pi is the 16th letter of the Greek Alphabet. So this is more evidence for the theory that the numbers 4 and 16 are important in regards to pi and also to mersenne primes. Dan _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Base-3 Pseudoprimes
At 03:54 PM 2/10/00 +0800, "Dave Mullen" [EMAIL PROTECTED] wrote: 1) For the LL test using FFT multiplys, we have to Transform the data, Multiply the matrices, Inverse Transform the data, then subtract 2. I am assuming that the only reason we do the Forward and Inverse Transform each time is so we can subtract the 2 ? Please correct me here if I'm wrong ! I found this in the Lucas Wiman FAQ. ([EMAIL PROTECTED]). Can't remember the link though. My only question would be, "Can we not figure out a way to stay in the frequency domain and correct the errors internally?" Dan-Somebody-MilesDaniel From the Lucas Wiman FAQ.: Q:6.4: In Q2.6, you say that it doesn't make sense to use a probable prime test. But wouldn't it make sense to do this, since you could stay in frequency space throughout the whole test, and save the time consuming FFT's and IFFT's? A: Well, first of all, you could still do this with the LL test (since x^2-2 has a Fourier transform, or by subtracting the convolution product of ...1*...2). However, the FFT's and IFFT's make certain that errors don't occur (by transforming back into time space, we can make certain that errors don't accumulate, remember this is an irrational base). This also allows "quick checks" e.g. the sum of the squares of the digits=sum of digits in the square (this takes almost no time at all since we have to manipulate the number anyway.) _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re: credit for manual testing
Bill Rea wrote: Do people using the manual check out forms get in the Top Producers list? I ask because I've never been able to find myself in the list and I had an email from a former GIMPS contributor who claimed he got no credit for exponents tested through the manual check out/check in pages. So far as I know, manual testing work doesn't get credited on the PrimeNet top producers pages, but does appear on the GIMPS top producers pages: http://www.mersenne.org./top.htm== top 100 based on P90 CPU-years http://www.mersenne.org./top2.htm == everybody else I don't know if manual testing results are included in the PrimeNet total FLOPS throughput figure, which has jumped appreciably in the last month. Thanks to Scott for adding CPU MHz and program version fields to the PrimeNet account status pages. One problem i noticed, however, is that all of my manual testing machines are listed as running Prime95 v16, even the ones that have in the past reported results using Mlucas. Lastly, it would also be nice to be able to enter something other than an x86 CPU type when requesting work from the PrimeNet server - right now I'm just clicking on "pentium" for all my non-x86 machines, so as to get an appropriate amount of work assigned. There could be preset fields for the better-known RISC CPUs, e.g. Alpha SGI/MIPSSparc IBM RS6000 Mac/PowerPC - - - - -- 21064/ev4 R3000 Sparc 1 (not sure ? 21164/ev5 R4000 Sparc 2 about the ? 21264/ev6 R5000 Sparc 5 early ones) 401 R8000 Sparc 10Power 1/SP1 403 R1 Ultra 1 Power 2/SP2 G3 R12000 Ultra 2 Power 3/SP3 G4 and an "other" field, where users can manually enter a type and speed for any other CPU types. I've ignored fine distinctions, e.g. the Alpha ev45 and ev56 and MIPS 4400 in the above, and some of the types may be redundant, but the table is only for purposes of illustration. If Scott decides this is worthwhile, he can appeal to the axperts with various platforms for an appropriately representative set of CPU types. Cheers, -Ernst _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re: Gabriel's horn
Chris Nash wrote:
If y=f(x), the volume of revolution is given by
{snip}
Chris, you forgot to explicitly give that f(x) = 1/x, although one
can infer that from the rest of your psot.
Brain teaser:
Are there infinitely many smooth functions f(x) which have the same
volume as the classical Gabriel's Horn when rotated about the x-axis
and x goes from 1 to infinity, and which also have infinite surface area?
(It would suffice to find a one-parameter function family which satisfies
this criterion.)
Gabriel's Horn is one of my favorite Calculus problems. Another is
the famous closed-form method of finding the integral of the Gaussian
exp(-x^2), where the fascinating number sqrt(pi) appears in the result.
The famous Euler identity, exp(i*pi)+1=0, which can be obtained from
the Taylor series for the exponential function and which involves the
five most fundamental constants in mathematics, is yet another.
Gauss' "Theorema Egregium" ("Totally awesome theorem" in dude-speak :)
about the curvature of surfaces also deserves mention, but is getting
way off-topic.
Cheers,
-Ernst
_
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Base-3 Pseudoprimes
On Thu, 10 Feb 2000 [EMAIL PROTECTED] wrote: My only question would be, "Can we not figure out a way to stay in the frequency domain and correct the errors internally?" If you can figure out a way to propagate carries while in the transform domain, then you're home free (there are FFTs base on number theory that have no rounding errors). I've thought about this for a while, but have no idea where to start (carry propagation is a nonlinear operation, so it's difficult to apply FFT techniques to it). jasonp _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Double-Checking
Do ALL exponents get Double-Checked? ...or are only selected exponents done beecause the original LL run was suspect? Just curious, Russ _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Email to mersenne
Anyone know why a email with subject "Re: more info on pi" I sent 24 hrs, 2-9-00, ago has not appeared on the list? I sent it with a reply all. Then today, 2-10-00, I forwarded another copy directly to [EMAIL PROTECTED] Another message I sent at the same time titled "Pi and Greek" 2-10-00 showed up on the list right away. Where did the two copies of "Re: more info on pi", 2-9-00, go? Thanks Dan _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Re: credit for manual testing
So far as I know, manual testing work doesn't get credited on the PrimeNet top producers pages, but does appear on the GIMPS top producers pages: http://www.mersenne.org./top.htm== top 100 based on P90 CPU-years http://www.mersenne.org./top2.htm == everybody else Know what's weird about those lists? My brother shows up in 19th place, and I'm in 400 something place, but we both use the same Primenet account. Hmmm... _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: How Many Angels, How Many Pins? Or PrimeNet's Assignment Strategy
Team M: Is it better to have 10 pins at 500MHz with one or two angels dancing, or one 5GHz behemoth looking for luck, given the way PrimeNet assigns exponents? Mixing Metaphors, Stefanovic _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Are these lemmas useful?
Here's something I posted in 1996 to sci.crypt.research, now with some typos corrected. It produced little reaction there. I'm hoping someone here can see how to apply it to factoring, or perhaps just to the Mersenne case. --- forwarded message - Like many others I've been trying for some time to find a fast factoring algorithm and/or to break RSA. Not too surprisingly, I haven't succeeded ( yet? :-). I have, however, proved a couple of little theorems which I haven't seen in the literature. Can anyone: find errors in my proofs? tell me if they're original? apply them to factoring? Fermat's little theorem is that for any prime p and integer i: i^p == i mod p My 1st lemma generalises this to: i^(p^n) == i mod p The proof is by induction. Fermat gives us the i = 1 case. For the induction step: i^(p^n) = i^(p*p^(n-1)) = (i^(p^(n-1)))^p but by hypothesis (i^(p^(n-1))) == imod p so i^(p^n) == i^p mod p == imod p QED My 2nd lemma applies to a strong prime s s = 2r + 1 r,s both prime I'll also assume r odd, ignoring the r=2, s=5 case. Fermat gives us: i^s == imod s and for non-zero i: i^(s-1) == 1mod s i^2r == 1mod s but we also have n^r == nmod r (Fermat) n^s == n^(2r+1) == n^3 mod r so n^s = n^3 + kr for some integer k But n^s and n^3 both have the parity of n so kr must be even So if r is odd (if s 5), k must be even. Which gives us: n^s = n^3 + 2jr for some int j or n^s == n^3 mod 2r whence i^(n^s) == i^(n^3) mod s Which is my 2nd lemma. end forwarded message -- The second lemma can be generalised to the case where s = 2r + t with s and t prime, i^(n^s) == i^(n^(t+2))mod s which reduces to the above if t = 1. I thought at one point this led to factoring N = xy with x, y prime. Very likely for some t you have: x = 2a + t y = 2b + t with a and b prime, in which case i^(n^xy) simplifies nicely. Unfortunately I couldn't find an efficient way to discover t. Can anyone suggest a method for that, or apply the lemmas in some other interesting way? _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
