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.
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.
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).
>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.
> M(727) is not prime. VME made the claim that they could
> compute the first prime following M(727) in two seconds.
I tried this on my PPro 200 and reproduced the composite result < 2
seconds.
> Well, that's only 156 more than M727, so finding it is easy; the
> obvious sieve will do it. Verifying it's at least pseudo-prime took
> the mers package's ecmfactor program only 1.27 seconds CPU
> on my Linux
> Pentium 200MHz just now, and proving it prime using Morain's ECPP
> program took all of 50.9 seconds.
>
> So, even if they are proving it prime, it's not a big advance.
I thought I'd try this, too:
M(727)= 70600348967705437423727721055115696583783847796289
4381170850482715673457590299624976468480248807499242724466
3745709991445308242164695977369066382721217365266076990228
70679030143158018123175881930939339869708632591433727
(pasted output)
Composite:
Start: 1999/03/14-12:05:33
Finish: 1999/03/14-12:05:33
(end output)
I had the program find the next 5 primes, in 37 seconds:
(pasted output)
Prime: 70600348967705437423727721055115696583783847796289
4381170850482715673457590299624976468480248807499242724466
3745709991445308242164695977369066382721217365266076990228
70679030143158018123175881930939339869708632591433883
Prime: 70600348967705437423727721055115696583783847796289
4381170850482715673457590299624976468480248807499242724466
3745709991445308242164695977369066382721217365266076990228
70679030143158018123175881930939339869708632591434057
Prime: 70600348967705437423727721055115696583783847796289
4381170850482715673457590299624976468480248807499242724466
3745709991445308242164695977369066382721217365266076990228
70679030143158018123175881930939339869708632591434109
Prime: 70600348967705437423727721055115696583783847796289
4381170850482715673457590299624976468480248807499242724466
3745709991445308242164695977369066382721217365266076990228
70679030143158018123175881930939339869708632591435431
Prime: 70600348967705437423727721055115696583783847796289
4381170850482715673457590299624976468480248807499242724466
3745709991445308242164695977369066382721217365266076990228
70679030143158018123175881930939339869708632591436901
Start: 1999/03/14-12:08:49
Finish: 1999/03/14-12:09:26
(end output)
> More to the point, a better test, since they're unwilling to reveal
> their method, would be to give them some large, strong pseudo-primes
> mixed in with known primes of similar size. Anybody care enough to
> produce such a set? The composite factors of prime exponent
> Mersennes are all base-2 pseudo-primes, but that's not enough; they
> should probably be Cunningham numbers (which are pseudo-prime to all
> bases that aren't related to their factors).
I'd be happy to try some of these and report what happens. The
program is easiest to use if the number to be tested is built by
formulation, but it can also read ascii digits from a text file.
> 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.
Hooking up its rather interactive DOS UI is a hassle, but it's a great
idea.
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.
Regards,
scott
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
