Hi folks,
Just thought I'd add my 2c worth to the discussion.
Firstly, bashing Professor Milstein is not getting anybody anywhere. His
"endorsement" is merely part of Meganet's commercial blurb, and while some
comments outside the body of the letter are rather eye-catching, isn't that
what advertising is about? As for the letter itself, it doesn't make any
indefensible claims, it doesn't claim a proof, it analyses the method for
its algorithmic qualities.
I'd disagree with some of the claims of efficiency, in that existing
implementations of probable-prime tests return the "same" results in shorter
time. At least, the "same" primes are returned, in shorter time. (I tested
4^7057-3 for probable primality some weeks ago in much less than 33 minutes
on a mere P-200). Pomerance et al tell us that pseudoprimes are rare, but
they also tell us that it's possible to construct counterexamples for any
number of pseudoprime tests. Meganet would therefore only have a
"breakthrough" (either algorithmic or mathematical) if their test was "more
effective", ie was indeed deterministic. Hence we require proof or
counterexample. Either would only be feasibly attained with more details of
the algorithm. And again, don't curse Meganet for being very clandestine
about these details - they are after all using it as a commercial
proposition. That's business.
Saul Backal's comment to Scott Kurowski that the test can degenerate into LL
is really the only lead anyone is going to get on attempts for
counterexamples - it might be worth considering Lucas pseudoprimes (to one
or more discriminants), somewhat tougher a condition than strong
pseudoprimality but still capable of construction. Even *if* the method is
equivalent to a Lucas test, you could be spending a lot of time on the
attempt. As Jud McCraine points out, Maple has been doing this for a long
time - and even if you know how Maple does the test, you may be hard-pressed
to find a counter-example. (the SPRP and LL test question is still
unanswered as far as I know but there seems no reason to believe there is
*no* counter-example - deterministic arbitrary prime polynomial-time testing
would say a lot about GRH).
On the one hand, I'd like to support any efforts to find a counter-example.
On the other hand, I feel maybe it is best to let things be. If Meganet's
target market is "industrial-strength" primes, that's fine. Since however
they addressed us as mathematicians in their initial mailings, I'm imagining
they seek a mathematical market too, unfortunately a market that requires
*proof*. Caveat emptor - there is no top 5000 for "probable primes".
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
