Some folks at an outfit called Meganet Corporation claim to have
developed a rigorous primality prover that runs as fast a pseudoprime test.
See their ballyhooing at http://www.meganet.com/primality.htm.
An excerpt:
MAJOR WORLDWIDE MATHEMATICAL
BREAKTHROUGH MEGANET CORPORATION
DEVELOPED FAST 100% DETERMINISTIC PRIME
NUMBER TESTING. IT IS THE ONLY
DETERMINISTIC ALGORITHM IN THE WORLD
TO WORK IN POLYNOMIAL TIME.
Meganet Corporation have announced the result of 13
years of Research & Development in the prime number
testing area the world's first and only POLYNOMIAL
TIME, 100% DETERMINISTIC PRIMALITY
TESTING. It is NOT a probabilistic test like the other
algorithms in the market, but 100% deterministic. The
algorithm is in POLYNOMIAL TIME, therefore much
faster than even the probabilistic algorithms. Meganet
Corporation have implemented the algorithm in an
ANSI C application running on a single CPU 450 MHz
PC Computer. Some sample results:
1,000 bits primality test {timing obscured}
{snip}
7,000 bits primality test 1:01min
10,000 bits primality test 1:58min
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.
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. 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.
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.
Of course they won't give out any details about the maths behind the method,
assuring us that a licensed practical mathematician is evaluating their claims,
which seems to fall a tad short of normal peer review. As Paul Jobling noted
in a posting to Chris Caldwell's Primes-List:
>I sent a mail to Meganet regarding their primality proving claims and
>received the following reply:
>>Hi,The Meganet Primality Test is currently being evaluated by a reputable
>>mathematician - when he'll finish his evaluation and endorse it (in about 2
>>weeks) we'll make it public.
>>We'll notify you by email and publish it on the web site.
>>Thank you for your interest in Meganet.
To which Mark Coffey replied:
>Three things about this statement by Meganet strike me as intersting:
>1) They did not see fit to name the "reputable mathematician"
>2) They already know that he will finish testing in two weeks
>3) They already know that he will endorse the test
>
>Oh and I guess a fourth would be the horrendous grammar in their reply.
I also note that near the bottom of the page, they make a statement that
seems to indicate theirs is in fact a probable-prime test (issues of
grammar aside):
Meganet Corporation is seeking for companies
interested in this algorithm which generates large
industrial grade prime numbers at record speeds, and
would be glad to demonstrate the technology to any
interested party on request.
Does anyone know more about the "400-year-old problem" they mention,
which would allow us to better judge the likelihood that their method
is rigorous? (I have my doubts.)
-Ernst
