> 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.
I am extremely sceptical of this claim for several reasons, but open-
minded enough not to reject such a claim completely out-of-hand.
Long ago I "invented" a technique which seemed to be reasonable,
involving a transform from the natural number field onto a subset,
the intention being to effectively carry out sieving to isolate primes
without actually having to carry out the whole operation.
Unfortunately I couldn't get it to work, and eventually learned
enough math to realise why. However, a clever application of a
similar concept just might work.
> [... snip ...]
> 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
Now that seems to make more sense. Psuedo-prime testing can
deliver "industrial grade" pseudoprimes, i.e. numbers which are not
neccessarily prime but are very hard to factor.
I wonder what their "rigorous primality prover" would make of a
Carmichael number? (A Carmichael number is a composite number
which is nevertheless pseudoprime to every base. They are rather
rare.) Do we know any Carmichael numbers which are of any
appreciable size, i.e. long enough not to be easily factored by
standard methods?
> 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.)
I have my doubts, too. But, does the conjecture that there are an
infinite number of Mersenne primes date back to Mersenne himself?
To the best of my knowledge, this conjecture remains unproved.
Though what it has to do with industrial-grade pseudoprimes useful
for cryptography defeats my imagination.
Regards
Brian Beesley
