Mersenne Digest Saturday, November 6 1999 Volume 01 : Number 656 ---------------------------------------------------------------------- Date: Wed, 03 Nov 1999 18:35:22 -0800 From: Eric Hahn <[EMAIL PROTECTED]> Subject: Re: Mersenne: Trial-factorers Brian Beesley wrote: >On 27 Oct 99, at 17:23, Eric Hahn wrote: >> >> I'm looking for program(s) capable of trial-factoring >> prime exponent Mersenne numbers (using 2kp+1) meeting >> the following requirements: >> >> [...requirements...] > >Well, I'm prepared to have a go. Could we tighten up the spec a bit? Wow!! I was going to post a message with regard to the fact that it looked like I was going to have write some code to produce my own program. While the programs that were suggested are well written, perform their designed functions, etc., they were either not capable of the tasks required or too slow to be useful. Now, look. I even have a volunteer to write some code!! :) >(a) There's also been some interest in something else that Prime95 >doesn't do - trial factoring 2^p+1. > >(b) I assume we're only interested in 2kp+1 factors. This means that >we will miss any factors which are not of this form. (Applies to >Mersenne numbers with composite exponents, and all 2^p+1 numbers - >though I believe that the "missed" exponents are easy to derive >analytically.) I'm not opposed or take exception to any possible additional capabilities... It just might require a little extra effort for the coding. >(c) I presume we're looking for a program optimized for IA32 >architecture. The mersfac* programs are available but are unlikely to >be optimally efficient on any particular hardware platform. Optimized for IA32 would be beneficial (which processor architechure runs >80% of PCs?). If possible, the ability to modify so as to optimize for other architectures would be a plus, however. One big concern is speed though! >Given that, I suggest limits on exponent < 2^62 and on factor < 2^95 >(these are convenient for the architecture). After waking up several nights ago with some pretty *scary* thoughts, I realized a couple of things. As such, exponents through 2^62 should do fine. Anything that might be necessary above 4.6 x 10^18 could probably be extrapolated (not that I can think of any reason, currently, that would cause it to be necessary). Factors, however, would be slightly different. I suppose 2^95 would be acceptable for a base level (or default), especially if testing an entire bit depth (or a large range of factors). However, if testing a small and specific range of K, say K=2^143 to K=2^143+500, it might need to go considerable higher. I'm willing to make a few sacrifices for this to be possible... Admittedly, I'm not "in the loop" regarding the division of the massive numbers for which I'm talking. I'm sure somebody is, however (and maybe could explain it). >It's probably sensible to go for an application which runs in a "DOS >box" rather than a proper windowed application. This makes it a bit >easier (for me) to write & also makes deriving a linux variant almost >trivial. (Does anyone know for sure whether or not there's a DOS box >in "Millenium"? I heard a nasty rumour...) I heard the same nasty rumor... Actually, I've heard several, including ones about the floppy and Win16 support, among others. Eric _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 3 Nov 1999 22:46:39 -0500 (EST) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Meganet Corp. > > I may have missed this, but was there any final judgment on the Meganet > >Corp. claim that they had a "deterministic and polynomial-time" prime > >test? There were some discussions on the list early this year when they > >first made their claim. But I don't recall reading about any resolution. > >Did this just fade away? Are they still holding to their claim? And if > >they are, does it stand up to examination (if they are revealing enough > >for examination)? > > These guys are snake-oil vendors. I don't know what type of prime test > they are claiming to have or not have but from my exposure to their crypto > claims I wouldn't trust anything from them without proof. I'd say this is true in this case as well. On their site they say things like: >Those results are unheard of. The 1,000 bits test on a Sparc > II workstation takes 5 Minutes and it is still only > PROBABALISTIC. The gap in time is much greater for larger > bit sizes. Eh? The probable prime test on 10^999+7 took ~20 seconds on my PII/233. That's a thousand digits, ~3000 bits. (w/primeform) >The major breakthrough is solving a 400 year old > mathematical problem – how to positively identify a prime > number without spending exponential time in dividing the > number by all the primes up to its root. This problem was solved by a primality testing algorithm that is based on eliptic curves (it was not practical), but it was polynomial. >The solution > Meganet Corporation have developed is based on a newly > designed Mathematical Sequence called the T-Sequence. > Once a number is transformed to the T-Sequence, its > quadratic residue has definitive characteristics if it’s a prime > number that can be easily determined in polynomial time by > performing a binary decomposition. Ok, if it is a prime then a^p==a mod p, what's your point? They don't even give a correct statment for their claims, they should say if and only if... >Meganet Corporation would like to emphasize that there is a > 100% mathematical proof behind their T-Sequence, and > further, it is a complete working product tested successfully > on over 1.3 million numbers without a single mistake. Ok, so proofs are measured in percent? Also, how many numbers are both a 2-spsp, and a lucas psuedoprime ($620 prize). I'll bet that that combination has been tested for a lot more than 1.3 million numbers without failure... Besides, the name meganet is too remanisant of Homer simpson's name for his internet company (on the Simpsons) I believe he called it something like hyper-compu-global-meganet. (It was eventually bought out by bill gates for fear of competition). - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 09:46:27 +0100 (MET) From: "Benny.VanHoudt" <[EMAIL PROTECTED]> Subject: Mersenne: small question Hi; Is it normal that an LL-test is interrupted when a new exponent is assigned, that hasn't been factored yet, and will the old LL-test proceed when the factoring is over (it is still present in the status report) ? Thanks, Benny - ------------------------------------------------------------------- Benny Van Houdt, University of Antwerp Dept. Math. and Computer Science PATS - Performance Analysis of Telecommunication Systems Research Group Universiteitsplein, 1 B-2610 Antwerp Belgium email: [EMAIL PROTECTED] - -------------------------------------------------------------------- _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 10:20:45 +0100 From: Preda Mihailescu <[EMAIL PROTECTED]> Subject: Re: Mersenne: Meganet Corp. > >The major breakthrough is solving a 400 year old > > mathematical problem – how to positively identify a prime > > number without spending exponential time in dividing the > > number by all the primes up to its root. > > This problem was solved by a primality testing algorithm that is based on > eliptic curves (it was not practical), but it was polynomial. > This is not correct. ECPP is polynomial, but it is _not_ deterministic, in fact pretty far from that. We are currently working at a deterministic polynoial time algorithm. It requires some additional spices, compared to ECPP. Preda _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 13:47:30 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: small question On 4 Nov 99, at 9:46, Benny.VanHoudt wrote: > Is it normal that an LL-test is interrupted when a new exponent > is assigned, that hasn't been factored yet, and will the old > LL-test proceed when the factoring is over (it is still present > in the status report) ? Yes. The idea is that, if the factoring was left, then you might find a factor straight away & have no work left to do. Doing the factoring in the middle of a current assignment means that if you do find a factor (lucky! - saves running the LL test) you have plenty of time to get more work assigned to you. Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 19:11:13 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Meganet Corp. On 4 Nov 99, at 10:20, Preda Mihailescu wrote: > This is not correct. ECPP is polynomial, but it is _not_ deterministic, in fact >pretty > far from that. We are currently working at a deterministic polynoial time algorithm. > It requires some additional spices, compared to ECPP. Gary Miller has demonstrated that, given the Generalized Riemann Hypothesis, at most 2(ln n)^2 probabalistic prime tests (aka Miller's Tests) suffice to determine the primality of n. This gives a "straightforward" deterministic polynominal time algorithm - though the performance is rather poor compared with the Lucas-Lehmer test for Mersenne numbers, the Pepin test for Fermat numbers or Proth's Test for the eponymous numbers. Miller's result yields a direct method of disproving the GRH - simply find a counterexample. I wouldn't hold my breath waiting for a counterexample to be found, though. Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 20:37:01 +0100 From: Preda Mihailescu <[EMAIL PROTECTED]> Subject: Re: Mersenne: Meganet Corp. > > > This is not correct. ECPP is polynomial, but it is _not_ deterministic, in fact >pretty > > far from that. We are currently working at a deterministic polynoial time >algorithm. > > It requires some additional spices, compared to ECPP. > > Gary Miller has demonstrated that, given the Generalized Riemann > Hypothesis, at most 2(ln n)^2 probabalistic prime tests (aka Miller's > Tests) suffice to determine the primality of n. This gives a > "straightforward" deterministic polynominal time algorithm - though Sorry to contradict you, but this things are called ``deterministic under the ERH'', which is totally different from deterministic, straight. The last means an algorithm which gives a provable answer prime or composite on any input, and the proof of which is complete (i.e. does not relay on _any_ unproved conjecture). I agree, many experts believe the ERH is true, but this does not change the notions, the way they are. Simply, if the ERH is proved one day to be true, all the effort spent meanwhile for finding deterministic primality proofs would look rather curly. But such is life. I was in Rome this summer when the proof of the Taniyama conjecture was announced, and at the same conference, in fact the day after the announcement, there were several talks about ``elliptic curves which are modular'', or ``Weyl curves'' - which were in that day known to be simply all elliptic curves :-). By the way there is exactly one deterministic primality proving algorithm (general, i.e. yielding an answer for any input) known by this date, and this is the deterministic version of the Adleman - Rumely - Pomerance test. And as for your claim that Miller's proof would feature a contradiction to the ERH, that is also false. In fact, what Miller noted is, that under the ERH, there is a polynomial bounded quadratic non residue - as you mentioned - and it follows without many complications, that beneath that bound, a Rabin-Miller witness of compositeness must be found: so if you know ERH is true and you performed Rabin - Miller tests up to that bound without encountering any compositeness witness, you are certain n was prime. But now suppose that - as it is in true life - you do not know ERH to be true. You do not find any witness up to so and so much: what do you then know ? Do you have a contradiction to the ERH ? Do you know n is prime ? Neither of both. On the other hand, if you use a deterministic or Las Vegas test ending with an answer on your input then your experiment shows: a) that you did not find any contradiction to ERH, if the number was indeed prime, but the Miller approach just could not give you a proof thereof (which he, of course never claimed !) or b) that you found a contradiction to the ERH if the other test proved n to be composite. Note that Las Vegas and deterministic tests always give correct unconditionally provable answers, the difference being that the last may also end with ``I do not know''. Sincerely Preda > the performance is rather poor compared with the Lucas-Lehmer test > for Mersenne numbers, the Pepin test for Fermat numbers or Proth's > Test for the eponymous numbers. > > Miller's result yields a direct method of disproving the GRH - simply > find a counterexample. I wouldn't hold my breath waiting for a > counterexample to be found, though. > > Regards > Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 22:12:55 +0100 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Mersenne: Re: Meganet Corp. On Tue, Nov 02, 1999 at 12:57:13PM -0600, William H. Geiger III wrote: >These guys are snake-oil vendors. I don't know what type of prime test >they are claiming to have or not have but from my exposure to their crypto >claims I wouldn't trust anything from them without proof. Remember that snake-oil isn't always deliberate. I just found it amusing that only a day after reading your message, one person I know (at school) claimed he had found the ideal way of slashing down file size. He was simply using DEBUG to reduce the file size (via a simple `rcx / (filesize) / w' or something along those lines), and then used the same technique to get it back to `full size'. Amazing... It took me quite a while to get him to show me this `amazing technique'. He claimed there was nothing wrong with it (just let me wipe the empty space on that diskette, please? ;-) ), and he was actually planning on selling it... Does this situation ring a bell? ;-) /* Steinar */ - -- Homepage: http://members.xoom.com/sneeze/ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 17:08:40 -0500 (EST) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Meganet Corp. > Sorry to contradict you, but this things are called ``deterministic under the > ERH'', which is totally different from deterministic, straight. The last > means an algorithm which gives a provable answer prime or composite > on any input, and the proof of which is complete (i.e. does not relay on > _any_ unproved conjecture). I agree, many experts believe the ERH is true, > but this does not change the notions, the way they are. Simply, if the ERH > is proved one day to be true, all the effort spent meanwhile for finding > deterministic primality proofs would look rather curly. But such is life. > I was in Rome this summer when the proof of the Taniyama conjecture > was announced, and at the same conference, in fact the day after the > announcement, there were several talks about ``elliptic curves which > are modular'', or ``Weyl curves'' - which were in that day known to be > simply all elliptic curves :-). I doubt that efforts in the direction of a deterministic polynomial time algorithm will look bad at all. Due mainly to the fact that Miller's test is not very practical. > By the way there is exactly one deterministic primality proving algorithm > (general, i.e. yielding an answer for any input) known by this date, and > this is the deterministic version of the Adleman - Rumely - Pomerance test. What? I thought (I could be wrong) that this had something like a log(log(log(n))) term in the exponent which prevented it from being polynomial. There are many deterministic algorithms (trial division for example), but you have to accept *very* bad run times. - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 22:12:55 +0100 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Mersenne: Re: Meganet Corp. On Tue, Nov 02, 1999 at 12:57:13PM -0600, William H. Geiger III wrote: >These guys are snake-oil vendors. I don't know what type of prime test >they are claiming to have or not have but from my exposure to their crypto >claims I wouldn't trust anything from them without proof. Remember that snake-oil isn't always deliberate. I just found it amusing that only a day after reading your message, one person I know (at school) claimed he had found the ideal way of slashing down file size. He was simply using DEBUG to reduce the file size (via a simple `rcx / (filesize) / w' or something along those lines), and then used the same technique to get it back to `full size'. Amazing... It took me quite a while to get him to show me this `amazing technique'. He claimed there was nothing wrong with it (just let me wipe the empty space on that diskette, please? ;-) ), and he was actually planning on selling it... Does this situation ring a bell? ;-) /* Steinar */ - -- Homepage: http://members.xoom.com/sneeze/ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 22:08:36 +0100 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Mersenne: Re: Trial-factorers On Wed, Nov 03, 1999 at 11:38:54AM -0700, Blosser, Jeremy wrote: >Lastly, bash has been ported to windoze already by the Cygnus folks... even >better tho (for NT at least), is 4NT (JPSoft). If 4NT is better, it would depend on your definition of `better', I guess :-) If you wanted to run bash scripts, bash would definitely be better, but there are surely cases where 4NT is better as well. /* Steinar */ - -- Homepage: http://members.xoom.com/sneeze/ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 04 Nov 1999 22:50:35 +0000 From: "David L. Nicol" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Meganet Corp. > > Once a number is transformed to the T-Sequence, its > > quadratic residue has definitive characteristics if it?s a prime > Ok, if it is a prime then a^p==a mod p, what's your point? > They don't even give a correct statment for their claims, they should say > if and only if... Nine out of ten dentists surveyed agree that only Meganet software soothes your T-sequence. Not one single case of throat irritation has been reported due to running Meganet software. http://www.thelimit.com/camel.htm ______________________________________________________________ David Nicol 816.235.1187 [EMAIL PROTECTED] End Daylight Savings Time in our lifetime _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 16:56:58 -0700 From: "Alan Vidmar" <[EMAIL PROTECTED]> Subject: Mersenne: Friday, November 5 1999 is the Burn All GIFs Day Liberate your website from the GIF patent! Friday, November 5 1999 is the Burn All GIFs Day. Please vist http://burnallgifs.org for more information. Alan "A programmer is a person who turns coffee into software." Alan R. Vidmar Assistant Director of IT Office of Financial Aid University of Colorado [EMAIL PROTECTED] (303)492-3598 *** This message printed with 100% recycled electrons *** _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 5 Nov 1999 00:33:59 -0000 From: "Daniel Grace" <[EMAIL PROTECTED]> Subject: Mersenne: Re: Meganet Corp. This is a multi-part message in MIME format. - ------=_NextPart_000_0042_01BF2725.73CDBEC0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable "Polynomial?" I think and please correct if I am wrong that trial factorisation using long division requires O(sqrt(n)*log(n)) operations. sqrt(n)*log(n) is polynomial in n e.g. it is less than n^2. Presumably when measuring the order of factorisation algorithms you guys use n ~ e^x and then measure the order in terms of x? What is a lower bound on a deterministic factoring algorithm? Puzzled :o - ---------------------------------------------------------- Daniel e-mail: [EMAIL PROTECTED] - ------=_NextPart_000_0042_01BF2725.73CDBEC0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META content=3D"text/html; charset=3Diso-8859-1" = http-equiv=3DContent-Type> <META content=3D"MSHTML 5.00.2014.210" name=3DGENERATOR> <STYLE></STYLE> </HEAD> <BODY bgColor=3D#ffffff> <DIV><FONT size=3D2>"Polynomial?"</FONT></DIV> <DIV> </DIV> <DIV><FONT size=3D2>I think and please correct if I am wrong = that trial=20 factorisation</FONT></DIV> <DIV><FONT size=3D2>using </FONT><FONT size=3D2>long division=20 requires </FONT><FONT size=3D2>O(sqrt(n)*log(n)) </FONT><FONT=20 size=3D2>operations.</FONT></DIV> <DIV><FONT size=3D2>sqrt(n)*log(n) is polynomial in n e.g. it is less = than=20 n^2.</FONT><FONT size=3D2></FONT></DIV> <DIV><FONT size=3D2>Presumably when </FONT><FONT size=3D2>measuring the = order of=20 factorisation</FONT></DIV> <DIV><FONT size=3D2>algorithms you guys </FONT><FONT size=3D2>use n ~ = e^x and then=20 measure the</FONT></DIV> <DIV><FONT size=3D2>order in terms of x?</FONT></DIV> <DIV><FONT size=3D2></FONT> </DIV> <DIV><FONT size=3D2>What is a lower bound on a </FONT><FONT = size=3D2>deterministic=20 factoring</FONT></DIV> <DIV><FONT size=3D2>algorithm?</FONT></DIV> <DIV> </DIV> <DIV><FONT size=3D2>Puzzled :o</FONT></DIV> <DIV> </DIV> <DIV><FONT=20 size=3D2>----------------------------------------------------------<BR>Da= niel<BR>e-mail:=20 <A=20 href=3D"mailto:[EMAIL PROTECTED]">[EMAIL PROTECTED]= o.uk</A></FONT></DIV> <DIV> </DIV> <DIV><FONT size=3D2></FONT> </DIV></BODY></HTML> - ------=_NextPart_000_0042_01BF2725.73CDBEC0-- _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 21:12:11 -0500 (EST) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Meganet Corp. > "Polynomial?" > > I think and please correct if I am wrong that trial factorisation > using long division requires O(sqrt(n)*log(n)) operations. > sqrt(n)*log(n) is polynomial in n e.g. it is less than n^2. > Presumably when measuring the order of factorisation > algorithms you guys use n ~ e^x and then measure the > order in terms of x? Well, it is polynomial to n, but we want it so that the runtime is polynomial to the digits of n (log(n)), which O(sqrt(n)*log(n)) is exponential to log(n). - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 21:17:32 -0500 (EST) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Meganet Corp. > Did I write polynomial anywhere ? I said deterministic primality proving algorithm. I thought that perhaps you mispoke, since your statement seemed incorrect. My point was that trial division is deterministic, but you said there was only one such algorithm. - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 4 Nov 1999 20:12:30 -0700 From: "Aaron Blosser" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Re: Trial-factorers > On Wed, Nov 03, 1999 at 11:38:54AM -0700, Blosser, Jeremy wrote: > >Lastly, bash has been ported to windoze already by the Cygnus > folks... even > >better tho (for NT at least), is 4NT (JPSoft). > > If 4NT is better, it would depend on your definition of `better', > I guess :-) > If you wanted to run bash scripts, bash would definitely be > better, but there > are surely cases where 4NT is better as well. 4NT is the bomb! I write 4NT scripts for doing just about anything. In fact, coupled with some resource kit utilities, it was 4NT that I used to distribute NTPrime to all those US WEST machines in a matter of only hours. Oh well. I do remember showing the script I wrote to the US WEST security team and they were just boggled by it. None of them had ever heard of 4NT there I guess. It started out because when I was doing "legitimate" work for US WEST, rolling out a few thousands of new computers, I wrote little 4NT batch jobs to send out minor file updates to machines already deployed (they kept changing the final spec of the software image even in the middle of the deployment...typical). It was great. I put in logging to keep track of which machines were unreachable so it would try those again later, generate logs of the successes, etc. I seem to recall posting a message to this list about using 4NT to deploy NTPRIME, along with some choice resource kit utilities like the remote command service and netsvc. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 04 Nov 1999 23:07:14 -0500 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Meganet Corp. At 12:33 AM 11/5/99 +0000, Daniel Grace wrote: >"Polynomial?" > >I think and please correct if I am wrong that trial factorisation >using long division requires O(sqrt(n)*log(n)) operations. It means that it is a polynomial function of the number of bits in n. Trial factorization isn't polynomial in the number bits of the number. +---------------------------------------------------------+ | Jud McCranie | | | | Programming Achieved with Structure, Clarity, And Logic | +---------------------------------------------------------+ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 5 Nov 1999 07:19:29 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Meganet Corp. On 4 Nov 99, at 20:37, Preda Mihailescu wrote: > Sorry to contradict you, but this things are called ``deterministic under the > ERH'', which is totally different from deterministic, straight. Of course, you're right. > Simply, if the ERH > is proved one day to be true, all the effort spent meanwhile for finding > deterministic primality proofs [independent of the ERH] would look > rather curly. But such is life. [Phrase in brackets is my insertion - BJB] Not neccessarily. Work applied in one direction sometimes proves useful somewhere else, even if the original project fails or is superceded. > I was in Rome this summer when the proof of the Taniyama conjecture > was announced, and at the same conference, in fact the day after the > announcement, there were several talks about ``elliptic curves which > are modular'', or ``Weyl curves'' - which were in that day known to be > simply all elliptic curves :-). It's unfair to expect people to rewrite their papers overnight! > And as for your claim that Miller's proof would feature a contradiction to the > ERH, that is also false. If we find a number with a certificate of primality derived from some method not dependent on the ERH but which nevertheless passes Miller's Test as a strong pseudoprime for all bases less than 2(ln n)^2, then either Miller's paper is broken, or we have a counterexample disproving the ERH. So far as I'm aware, Miller's paper is no more contentious than Pythagoras's Theorem. Proth's Theorem allows us to find certified prime numbers of a fair size (thousands of digits) quite rapidly. Granted these are a very thin subset of all numbers, and, even then, running sufficient Miller's Tests on a number with "only" a thousand digits would take a very large amount of CPU time. That's why I won't be holding my breath! Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 5 Nov 1999 11:06:57 +0100 From: Preda Mihailescu <[EMAIL PROTECTED]> Subject: Re: Mersenne: Meganet Corp. > On 4 Nov 99, at 20:37, Preda Mihailescu wrote: > > > Sorry to contradict you, but this things are called ``deterministic under the > > ERH'', which is totally different from deterministic, straight. > > Of course, you're right. > > > Simply, if the ERH > > is proved one day to be true, all the effort spent meanwhile for finding > > deterministic primality proofs [independent of the ERH] would look > > rather curly. But such is life. > > [Phrase in brackets is my insertion - BJB] > > Not neccessarily. Work applied in one direction sometimes proves > useful somewhere else, even if the original project fails or is > superceded. > Of course, of course. I said curly, funny, etc. I did not say condemned in the next 25 eternities to bogus treatment, or something. Nuances ! > > I was in Rome this summer when the proof of the Taniyama conjecture > > was announced, and at the same conference, in fact the day after the > > announcement, there were several talks about ``elliptic curves which > > are modular'', or ``Weyl curves'' - which were in that day known to be > > simply all elliptic curves :-). > > It's unfair to expect people to rewrite their papers overnight! The same thing ! Where is your humour ? No one expects nothing from anyone - but it would hypocritical to claim that the situation of those people was not funny/embarassing/out of common - you chose the word the pleases you most ! > > > And as for your claim that Miller's proof would feature a contradiction to the > > ERH, that is also false. > > If we find a number with a certificate of primality derived from some > method not dependent on the ERH but which nevertheless passes > Miller's Test as a strong pseudoprime for all bases less than > 2(ln n)^2, then either Miller's paper is broken, or we have a > counterexample disproving the ERH. So far as I'm aware, Miller's > paper is no more contentious than Pythagoras's Theorem. > I would say Miller paper is correct. In fact not only is it quite old and resisted scrutiny, but first of all the ideas are rather simple, so it is difficult to hide a reasoning bug behind them. (E.g., you cannot compare to Wiles 220 pages proof, which took a time to be followed and understood). So yes, it would be a counterexample to ERH. > Proth's Theorem allows us to find certified prime numbers of a fair > size (thousands of digits) quite rapidly. Granted these are a very > thin subset of all numbers, and, even then, running sufficient > Miller's Tests on a number with "only" a thousand digits would take a > very large amount of CPU time. That's why I won't be holding my > breath! > No one is out for your holding your breath. ( I do not realle understand for what either, but it is unimportant). Regards Preda > > Regards > Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 5 Nov 1999 10:30:53 -0000 From: "Daniel Grace" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Meganet Corp. This is a multi-part message in MIME format. - ------=_NextPart_000_0057_01BF2778.D67C6AA0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable > At 12:33 AM 11/5/99 +0000, Daniel Grace wrote: > >"Polynomial?" > > > >I think and please correct if I am wrong that trial factorisation > >using long division requires O(sqrt(n)*log(n)) operations. >=20 > Jud McCranie wrote : > It means that it is a polynomial function of the number of bits in=20 > n. ... or nibbles, bytes or whatever base your machine is working in ... basically whatever you consider as requiring O(1) operations - it does not effect the "O" analysis. > Trial factorization isn't polynomial in the number bits of the number. I did not say it was. Daniel. - ------=_NextPart_000_0057_01BF2778.D67C6AA0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META content=3D"text/html; charset=3Diso-8859-1" = http-equiv=3DContent-Type> <META content=3D"MSHTML 5.00.2014.210" name=3DGENERATOR> <STYLE></STYLE> </HEAD> <BODY bgColor=3D#ffffff> <DIV>> At 12:33 AM 11/5/99 +0000, Daniel Grace wrote:<BR>>=20 >"Polynomial?"<BR>> ><BR>> >I think and please correct if = I am=20 wrong that trial factorisation<BR>> >using long division requires=20 O(sqrt(n)*log(n)) operations.<BR>> <BR></DIV> <DIV>> Jud McCranie wrote :<BR>> It means that it is a polynomial = function=20 of the number of bits in <BR>> n.<BR><BR>... or nibbles, bytes or = whatever=20 base your machine is working in ...<BR>basically whatever you consider = as=20 requiring O(1) operations - it<BR>does not effect the "O" = analysis.<BR><BR>>=20 Trial factorization isn't polynomial in the number bits of the = number.<BR><BR>I=20 did not say it was.<BR><BR>Daniel.<BR><BR><BR></DIV></BODY></HTML> - ------=_NextPart_000_0057_01BF2778.D67C6AA0-- _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 05 Nov 1999 10:10:21 -0500 From: Jud McCranie <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Meganet Corp. At 10:30 AM 11/5/99 +0000, Daniel Grace wrote: > > Trial factorization isn't polynomial in the number bits of the number. > >I did not say it was. You said: > > At 12:33 AM 11/5/99 +0000, Daniel Grace wrote: > > >"Polynomial?" > > > > > >I think and please correct if I am wrong that trial factorisation > > >using long division requires O(sqrt(n)*log(n)) operations. But that is not what we call a "polynomial time" algorithm. Poly time refers to a polynomial function of the size of the input (bits, digits, etc) - NOT the size of the number itself. +---------------------------------------------------------+ | Jud McCranie | | | | Programming Achieved with Structure, Clarity, And Logic | +---------------------------------------------------------+ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 6 Nov 1999 16:07:03 EST From: [EMAIL PROTECTED] Subject: Mersenne: Re: Mlucas on SPARC Bill Rea writes: >At 256K FFT I was seeing 0.11 secs/iter with >Mlucas against 0.15 secs/iter for MLU, at 512K FFT the figures were >0.25 secs/iter and 0.29 secs/iter respectively. ...and don't forget the added benefits due to Mlucas being able to test significantly larger exponents at the same FFT length, as well as having intermediate runlengths between powers of two. 0.11 seconds at 256K is impressive - that's faster than on my 400MHz Alpha 21164 (0.16 sec) and Prime95 on a 400MHz PII (0.13sec), though, to be fair, both of the latter systems have a smaller (512KB) L2 cache. >Mlucas runs significantly faster if you can compile and run it >on a 64-bit Solaris 7 system. This is the first I've heard of this - roughly how much of a speedup do you see? >I would like to upgrade the E450 to Solaris 7 and see what Mayer's >code can do in 64-bit mode, but the owners won't let me :-( Luddites. :) Brian Beesley writes: >Bear in mind that Mlucas is still a bit "experimental". One problem >has come to light - if you're using the PrimeNet Manual Testing page >to submit results, you _must_ remove the space preceding the M at the >beginning of the result line, else PrimeNet won't accept the result. >Actually it says it has got the result but doesn't remove the >assignment from the current assignments report or add it to the >completed assignments report unless the leading space is removed. >(This seems to be a program bug, I see the extra space in the source >code so I'd assume the problem afflicts Mlucas 2.7y on all platforms. >Certainly the binary executable I built for Alpha systems running >linux is also afflicted.) Actually, I had good reason to insert the leading space - many Fortran compilers (especially older ones) interpret the leading character of a literal output string as a linefeed character (a holdover from the days of line printers) and will print gibberish if it's nonblank. I quote from Metcalf & Reid, "Fortran 90/95 Explained," p.212: "Fortran's formatted output statements were originally designed for line-printers, with their concept of lines and pages of output. On such a device, the first character of each output record must be of default kind. It is not printed but interpreted as a _carriage control character_. If it is a blank, no action is taken, and it is good practice to insert a blank as the first character of each record..." It seems this is something that is better dealt with on the server end - seems a bit silly for PrimeNet to get discombobulated by an extra blank space here and there. Scott, any chance you could apply a patch to solve this problem in the near future? (In between diaper-changing, of course :) For those of you who own/administrate Alphas, SGIs and SPARCs (or know someone who does), please get the word out - it would be nice to start increasing the percentage of non-x86 GIMPS clients, especially now that there's Mersenne testing code roughly as fast as Prime95 for all these systems. The one thing we still need to make it easy to administer multiple machines (e.g. a lab full of them) is a PrimeNet interface. Scott suggested to me that the easiest way to do this is to start with the Mprime (Prime95) for Linux interface routines. Does any want to look at those, and see if they can get something working for at least one of the above Unix/Linux clients? If I don't hear from anyone I suppose I'll have to do it myself, but I honestly prefer to work on the under- lying "engine" - every day I spend on other things is a day I don't have to work, e.g. on the Mlucas P-1 factoring code. Also, I've had no responses to my query about the Absoft f90 compiler for the Macintosh - is the Mac portion of GIMPS dead, or is the name "MacLucas" leading all the Mac users to believe that MLU is the only code that will run on their hardware? Happy hunting, Ernst ftp://209.133.33.182/pub/mayer/home.html _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #656 ******************************
