Mersenne Digest Tuesday, 16 March 1999 Volume 01 : Number 532 ---------------------------------------------------------------------- From: Jud McCranie <[EMAIL PROTECTED]> Date: Mon, 15 Mar 1999 11:20:03 -0500 Subject: Re: Mersenne: RE: Meganet's Primality Code At 06:15 PM 3/14/99 -0800, Scott Kurowski wrote: > >I can say, loosely, that the 'T-sequence' primality test is actually a >family of four related complementary algorithms performed in series, >any of which can reject a number as composite, but if all four pass >the number is supposedly prime. This reminds me of the primality test used by Maple. "It returns false if n is shown to be composite within one strong pseudo-primality test and one Lucas test and returns true otherwise. If isprime returns true, n is ``very probably'' prime .... No counter example is known and it has been conjectured that such a counter example must be hundreds of digits long. " So one strong PSP test and one Lucas test *seems* to work, but it hasn't been proven to always work and no counterexamples are known. +--------------------------------------------------------+ | Jud McCranie [EMAIL PROTECTED] | | | | 127*2^96744+1 is prime! (29,125 digits, Oct 20, 1998) | +--------------------------------------------------------+ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: Paul Derbyshire <[EMAIL PROTECTED]> Date: Mon, 15 Mar 1999 13:10:39 -0500 Subject: Re: Mersenne: Milstein At 01:22 AM 3/11/99 -0000, you wrote: >I was not the only one to run a check on Prof. Milstein on the web then. > >It seemed odd that the only three recent mentions of Jaime Milstein are in >the field of linear algebra with the same co-author, Thomas L Moeller. > >One wonders who the other "top ranking " mathematician that he submitted the >theory to could have been. <BG> OK... how's about someone with the connections checks out *Moeller* now? :-) - -- .*. "Clouds are not spheres, mountains are not cones, coastlines are not - -() < circles, and bark is not smooth, nor does lightning travel in a `*' straight line." ------------------------------------------------- -- B. Mandelbrot |http://surf.to/pgd.net _____________________ ____|________ Paul Derbyshire [EMAIL PROTECTED] Programmer & Humanist|ICQ: 10423848| ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: Paul Derbyshire <[EMAIL PROTECTED]> Date: Mon, 15 Mar 1999 12:49:33 -0500 Subject: RE: Mersenne: Fabs. At 07:14 AM 3/10/99 -0800, you wrote: > >> >Eh? My first job after finishing my DPhil... >> >> Your what? > >It's what Oxford and a bunch of other universities call a PhD. They doctor >us differentlyin Oxford ;-) You mean you have a PhD? (looks at email headers) And you're wasting it in Microsoftland??? >I also cheated slightly (and I'm surprised that other old-hands didn't pick >me up on it). Although the clock ticked at 40MHz, it took at least four >ticks to do anything --- just as the 4MHz Z80A did. Why bother calling it 40MHz then? Why not call it 10MHz? Marketing, make it seem 4 times faster than it is? Even those greedy crooks at Intel don't do that... - -- .*. "Clouds are not spheres, mountains are not cones, coastlines are not - -() < circles, and bark is not smooth, nor does lightning travel in a `*' straight line." ------------------------------------------------- -- B. Mandelbrot |http://surf.to/pgd.net _____________________ ____|________ Paul Derbyshire [EMAIL PROTECTED] Programmer & Humanist|ICQ: 10423848| ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: Paul Derbyshire <[EMAIL PROTECTED]> Date: Mon, 15 Mar 1999 13:37:51 -0500 Subject: Re: Mersenne: Want to Increase Sales 100 - 150% ? What's this garbage doing on the list, apparently directly from someone on base.com??? At 08:35 AM 3/10/99 -0100, "[EMAIL PROTECTED]" wrote: > >INCREASE SALES UP TO 100-150% > >ACCEPT CREDIT CARDS OVER THE INTERNET *** NO SETUP FEES >Good Credit / Bad Credit / No Credit **** NO PROBLEM ****!!! >It Just Doesn't Matter - Everyone Gets Approved >ONLY $49.95 TO GET STARTED!!! >No Upfront Fees For Application-Processing >While Others Charge You From $195 To $250 To Get Set Up >WE CHARGE ZERO FOR SETUP FEES!! >Limited Offer So Take Advantage Of It!! >We Specialize In Servicing The Following: >*Multilevel Marketing >*Mail Order/Phone Sales >*At Home Business >*INTERNET BASED BUSINESS >*New Business*Small Business >Whatever!!! We Do It All!!! Everyone Is Welcome! > >Call us TOLL FREE today 1-877-SWIPE-CC (I.D. 20) > 1-877-794-7322 (I.D. 20) > >What Can Do It For Your Company ???? > >>>>>INTERNET SERVICE<<<<< > >SECURE REAL-TIME ON-LINE TRANSACTIONS make it as easy as possible for your >customers to purchase your products or services. >We use SSL SECURITY (best on the NET today). > >Now tell me if this doesn't sound intriguing, lets say a customer visits >your website and decides they want to buy your product(s) or services(s). >They would simply enter their credit card information and receive an >approval WITHIN 5 SECONDS. That's all there is to it!!! > >>From that point on, the sale is complete and the money will be directly >deposited into your business checking account within 24 to 48 hours. >So you will have LIQUID ASSETS AVAILABLE ALMOST IMMEDIATLY!!!! >Your customer will be e-mailed a receipt and you will be e-mailed an >invoice slip, all instantaneously. Now, since this program is automated >for 24 hours a day 7 days a week, you will be recieving orders and maiking >money in your sleep!!!!! >IT'S JUST THAT EASY!!!! > >WHAT MAKES US SO SPECIAL????? > >* We process over $4 Billion in credit card transactions every year. >* We have over 100,000 merchants online and growing. >* We offer secured on-line real time transactions. >* We offer 24 hour customer service 7 days a week in 17 different languages. >* We offer complete training and installation through our technical support group. >* We offer a life time warranty and unlimited upgrades. >* We help make money for your company and yoru customer. > >>>>>>CONTACT INFORMATION<<<<< > >Call us TOLL FREE today 1-877-SWIPE-CC (I.D. 20) > 1-877-794-7322 (I.D. 20) > >Leave a message with your Name, Phone Number, and a brief description of your >type of business. > >Once you call, an account executive will contact you within 24 hours to discuss >your options, answer your questions, and start you on your way to financial success. > >DON'T DELAY!!!! ACT TODAY!!!! >---------------------------------------------------------- >To be removed, simply call 1-800-600-0343 ext. 1746 >and leave your e-mail address. Thank you. >---------------------------------------------------------- > >________________________________________________________________ >Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > > - -- .*. "Clouds are not spheres, mountains are not cones, coastlines are not - -() < circles, and bark is not smooth, nor does lightning travel in a `*' straight line." ------------------------------------------------- -- B. Mandelbrot |http://surf.to/pgd.net _____________________ ____|________ Paul Derbyshire [EMAIL PROTECTED] Programmer & Humanist|ICQ: 10423848| ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: The thrill of minimalism <[EMAIL PROTECTED]> Date: Mon, 15 Mar 1999 19:47:55 +0000 Subject: Re: Mersenne: VME claim [EMAIL PROTECTED] wrote: > > > > The only stronger tests that I can think of are making the program > > available via a TCP/IP server of some sort, so people like us can give > > it arbitrary numbers to check in real time, and a rigorous proof of > > the method, which requires making it public. > > > I bet the last is highly sufficient .... > > Sincerely > > Preda The fact that they don't already have such a thing set up weakens their credibility, it would be a total piece of cake to create on a web page: <form action=VMEverify.cgi method=post> Enter your number here for a sample analysis from our splendid software: <textarea rows=10 cols=60></textarea></from> ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: [EMAIL PROTECTED] Date: Mon, 15 Mar 1999 21:27:09 +0100 (MET) Subject: Re: Mersenne: RE: Meganet's Primality Code > Hi all, > > About a month ago I invited Meganet to show me their primality > program, a small subcomponent of VME. Saul stopped by our office. I > echoed the Mersenne list's skepticism, but suggested independent peer > review might buy Meganet better credibility. I don't necessarily > support Meganet's claims but thought being open minded enough to > invite concrete results would clear the air. > This is a fair approach ! > I signed a simple NDA, the same that up to three other reviewers I > choose will sign to try the program and examine/modify/compile the > code. I have not yet received a copy of the source code, pending > further progress on their patent application. > Basically, once an application has been announced, the idea is protected. Did they already announce a patent at all or are they still working on the claims ? > He walked me through the code, explained the algorithm and described > how it was developed with Milstein. The program was simple - a few > pages - and uses a public domain integer math package. I'm tough to > snow and didn't detect any B.S. as we reviewed its internals, but I'm > no math expert, either. > > I can say, loosely, that the 'T-sequence' primality test is actually a > family of four related complementary algorithms performed in series, > any of which can reject a number as composite, but if all four pass > the number is supposedly prime. > > One claim Saul made (and showed on paper to my unqualified eyes to > verify) was that pinning the coefficients of the 'T-sequence' to a set > of specific values causes it to degenerate into the LL series. Saul > also claimed the algorithm detects and rejects strong pseudo-primes as > composite, and showed some examples with the program (I don't recall > what they were). > There are _very_ many ways to generalize Lucas - Lehmer sequences. And I can also define on the spot a dozen generalizations of which I am prety positive that no one might come up with an example of failure (an adapted kind of pseudoprime that would pass the given test). The point is that giving a proof is more than nobody in the next 100 years not being able to show a counterexample. So I do not think very much of the testing idea. If they combine four different tests in the LL flavour, one may be smart enough to do so and making it _really_ hard for someone to come up with a counterexample. This happened last year with a student who made the same kind of claim public: he used two LL kind of tests, and R.Pinch had a pseudoprime for _that_. > >The number n=4^7057-3 has been proved prime by cyclotomy: with 4249 > >decimal digits, it is currently the largest prime proved with a > >general prime proving algorithm. The main stage of the proof took 6 > >hours, the final "Lenstra - gcd and trial division" step (allowing a > >factored part of O(n^{1/3}) took roughly 2 days. > > Luke invited me to try the Meganet program on 4^7057-3. It reported > the number as prime in 33 minutes on my PPro 200, with a bunch of > other apps going at the same time. > Sounds totally feasible for four extended LL tests ! They cannot take place in too large extensions though ... > I had planned to get the code before asking the list for a few folks > interested in taking a crack at finding a flaw in it. We get only > three evaluations under NDA. Maybe we can use one up to hook it up on > a server under a web form in kind of constrained batch mode. Any > takers? Please email me privately. > In short words: unless there is a crude programming error too - which I doubt, since I believe they tried it on quite some known primes - it is _only_ the proof scrutiny which can make the difference. It is simpler with factoring .... Regards Preda > Regards, > scott > > > > ________________________________________________________________ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: Gary Untermeyer <[EMAIL PROTECTED]> Date: Mon, 15 Mar 1999 14:21:07 -0700 Subject: Re: Mersenne: Want to Increase Sales 100 - 150% ? Greetings, Paul Derbyshire wrote: > > What's this garbage doing on the list, apparently directly from someone on > base.com??? > > At 08:35 AM 3/10/99 -0100, "[EMAIL PROTECTED]" I don't know, but did you have to quote the whole thing so it went on twice?! Gary Untermeyer ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: "Aaron Blosser" <[EMAIL PROTECTED]> Date: Mon, 15 Mar 1999 14:45:41 -0700 Subject: RE: Mersenne: Fabs. > >I also cheated slightly (and I'm surprised that other old-hands > didn't pick > >me up on it). Although the clock ticked at 40MHz, it took at least four > >ticks to do anything --- just as the 4MHz Z80A did. > > Why bother calling it 40MHz then? Why not call it 10MHz? > Marketing, make it > seem 4 times faster than it is? Even those greedy crooks at Intel don't do > that... It was my understanding that the first x86 machines were incapable of completing instructions in a single clock cycle. For example, the 8086/8088 took 2-3 cycles just for an integer add. Nowadays you can do multiple instructions in a single cycle, using pipelining, but you don't "increase" the apparent MHz speed. That's why comparisons between RISC and CISC fall flat if you only look at clock speed. A RISC running at 800MHz might take more clock cycles to do what a CISC can do in 1 cycle at 400MHz, for example. ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: George Woltman <[EMAIL PROTECTED]> Date: Mon, 15 Mar 1999 18:39:45 -0500 Subject: Re: Mersenne: Chance of a Mersenne prime Hi all, I had to be out of town for a week. I'll catch up on my email and the stats pages as soon as possible. Thanks for your patience. At 04:12 PM 3/7/99 -0000, [EMAIL PROTECTED] wrote: >1. Does anyone know where the estimate of an exponent yielding a Mersenne prime >that Prime95 outputs in its status pop-up comes from? Remember, I'm a layman mathematician so don't be too hard on me! This comes from the observation that the chance of finding a factor between 2^x and 2^(x+1) is 1/x. Now assume we are looking at M1000 and we know from trial factoring that it has no factors below 2^50. The chance that M1000 is prime is the chance that it has no 51 bit factor (50/51) times the chance that it has no 52 bit factor (51/52) times .... the chance that it has no 500 bit factor (499/500). You'll note a lot of these terms cancel leaving the formula: chance of prime = how far factored / (exponent/2) = 2 * how far factored / exponent BTW if you couple this with the formula for frequency of primes you get the expectation of 1.78 Mersenne primes between exponents Y and 2*Y Another BTW, real mathematicians have told me the 2 in the above formula should really be Euler's constant. >2. Does our continued effort in eliminating possible Mersenne primes change that >estimate in any way? No. Each test is an independent event. > Since I joined the project 10 months ago, we have found no >new Mersenne primes We have been unlucky. Best regards, George ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: [EMAIL PROTECTED] Date: Mon, 15 Mar 1999 23:32:30 EST Subject: Mersenne: LL testing I'm curious, as to the nature of the proof that the LL test can definitively prove/disprove the primality of a Mersenne number. The resources I have are limited and don't go into depth. Before I search elsewhere, I was wondering if anyone on the list could help me: What were the original details of Lucas' test? And how did Lehmer modify it into its current form (at least I know how to perform the LL test in its current state). What are the details of the proof that Lucas' test definitively (dis)proves the primality of a Mersenne number? Does the proof change for the Lucas-Lehmer test? In the LL test, we start with S(1) = 4. The Prime Page says we can use S(1) = 10 and certain other values depending on p. Can anyone clarify this? To prove that M(127) (Or M127, whichever refers to 2^127 - 1, not the 127th Mersenne prime) is prime, did Lucas use his test by hand? I know he did it by hand, at the very least. I posted a message on sci.math a while ago. The response was deafening. If anyone on the list would like to add to the voluminous (har har har) response I've received, I'd be grateful. It can be found at: http://www.dejanews.com/getdoc.xp?AN=450576076 I don't wish to add to the size of the list digest unduly. Thanks. Please reply to the list, as if you have an Internet E-mail address, my software will auto-block you. AOL members need not worry. S.T.L. ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: Conrad Curry <[EMAIL PROTECTED]> Date: Mon, 15 Mar 1999 23:29:45 -0600 (EST) Subject: Re: Mersenne: RE: Meganet's Primality Code ... > >The number n=4^7057-3 has been proved prime by cyclotomy: with 4249 > >decimal digits, it is currently the largest prime proved with a > >general prime proving algorithm. The main stage of the proof took 6 > >hours, the final "Lenstra - gcd and trial division" step (allowing a > >factored part of O(n^{1/3}) took roughly 2 days. > > Luke invited me to try the Meganet program on 4^7057-3. It reported > the number as prime in 33 minutes on my PPro 200, with a bunch of > other apps going at the same time. A strong pseudo prime test is wrong at most 1/4 of the time. However, in practice this is much smaller. If I use 100 random bases and it reports a number is prime then the probability it is wrong is (1/4)^100=6.2E-61. You would need to test more than 6.2E61 values before having a good probability of finding a counterexample. If random bases are used even then your counterexample would not be reproducible (without knowing the random bases). See Knuth v.2 3rd ed. p. 395. I could disguise the algorithm with some complex arithmetic operations and call it a "U-sequence". Without publishing the algorithm for peer-review and a rigorous proof I could claim it was a fast 100% determinstic primality test. Noone would be able to find a counterexample. Perhaps Meganet has done this or they have unknowingly created a probabilistic primality test. In Dr. Milstein's endorsement he states "I did not develop rigorous proofs...I applied the assertions of the paper to a number of non-trivial values." Regardless of his credibility this endorsement is meaningless. It is just marketing hype for their primality test. Without a proof Meganet's primality test is still a probabilistic test, so why not use a free one. Here is one, no marketing hype, no endorsements and no "T-sequences"! Compile with GNU-MP. #include <stdio.h> #include "gmp.h" int main() { mpz_t N; mpz_init (N); printf ("Enter number:\t"); mpz_inp_str (N, stdin, 10); if (mpz_probab_prime_p (N, 100)) printf ("Prime\n"); else printf ("Composite\n"); return (0); } > > I had planned to get the code before asking the list for a few folks > interested in taking a crack at finding a flaw in it. We get only > three evaluations under NDA. Maybe we can use one up to hook it up on > a server under a web form in kind of constrained batch mode. Any > takers? Please email me privately. Ask to see their proof and not just the code. Their website claims they have one. ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: Jonathan A Zylstra <[EMAIL PROTECTED]> Date: Mon, 15 Mar 1999 21:39:59 -0800 Subject: Re: Mersenne:Garbage - -this was in the ad, so this might help >---------------------------------------------------------- >To be removed, simply call 1-800-600-0343 ext. 1746 >and leave your e-mail address. Thank you. >---------------------------------------------------------- >>>>>CONTACT INFORMATION<<<<< Call us TOLL FREE today 1-877-SWIPE-CC (I.D. 20) 1-877-794-7322 (I.D. 20) J. Zylstra [EMAIL PROTECTED] ___________________________________________________________________ You don't need to buy Internet access to use free Internet e-mail. Get completely free e-mail from Juno at http://www.juno.com/getjuno.html or call Juno at (800) 654-JUNO [654-5866] ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ From: "Scott Kurowski" <[EMAIL PROTECTED]> Date: Tue, 16 Mar 1999 00:21:52 -0800 Subject: Mersenne: RE: Meganet's Primality Code I'll wait until I get source code before doing anything else - I'm expecting to hear from Saul then, and will ask about a web server demo hookup. Maybe he would set it up for us. When I asked about a proof, he said they didn't have one - just a huge test set. Short of a proof, I thought finding at least one example that breaks their program would be most effective. If it's not worth the bother, I'll drop it. Regards, scott ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ End of Mersenne Digest V1 #532 ******************************
