mpz_probab_prime_p() failures
Décio Luiz Gazzoni Filho
decio at decpp.net
Mon Dec 5 00:15:31 CET 2005
On Dec 4, 2005, at 7:26 PM, Alan McFarlane wrote:
> Ah, sorry, I phrased the question incorrectly...
>
> What I meant to ask was...
>
> Does anyone have any information regarding mpz_probab_prime_p()
> returning 1 (probably prime) when the supplied number is in fact
> composite?
>
Thomas Nicely's web page has the info you want.
> [very quick 'n' dirty pseudocode]
>
> for ( number = 1 to 1,000,000,000,000 )
> for ( iterations = 1 to 1,000 )
> if (mpz_probab_prime_p( number, iterations ) = 1)
> if (number is composite) /* how this is done is left as
> an excersize! */
> print "Found One!!! - number is composite, but
> mpz_probab_prime_p() reports as being probably prime"
> end if
> end if
> next
> next
>
> [end very bad code!]
>
> The reason being that armed with this knowledge, I could perform
> better primality tests:
>
> [pseudo code]
>
> if (number < 1,234,567,890)
> if (mpz_probab_prime_p(number, 5))
> print "prime"
> end if
> else if (number < 1,234,567,890,123)
> if (mpz_probab_prime_p(number, 25)) /* notice increase in
> iterations to compensate for failure at 1,234,567,890 */
> print "prime"
> end if
> end if
>
> etc
That makes no sense in practice. If you really really need to make
sure a number is prime (are you really sure about that? Will your
computation fail if the number involved is not a prime?), then Miller-
Rabin tests, and indeed, any compositeness test, is not the answer.
You probably want to use Miller-Rabin to screen out composites and a
real primality test, not a pseudoprimality test, to certify the
pseudoprimes produced in the screening process. Perhaps a sieve will
help also.
Now, don't take the following comments personally, I'm just sick of
this sort of situation coming up in this and other lists I
participate. First of all, take it from me that, whatever your
application is, you probably don't really need primes, and can live
with the next-to-null probability that once in a blue moon a
composite comes out. If hypothetically composites were to ruin your
algorithm, then you have many other factors to take into account
before worrying about the probability of getting a composite -- does
all your memory have error-correction? Your caches? Are you running
the code on three distinct physically separated CPUs and comparing
their results? Do you have some pretty rugged cosmic ray shielding
for your hardware? You're of course not running off-the-shelf
hardware, right, since those don't go through very strict
verification procedures -- you probably want an Itanium or some IBM
mainframe hardware. You should also formally prove the validity of
the assembly code generated by your compiler and GMP to avoid any
bugs. All these `problems' are more likely to happen than a failure
of the Miller-Rabin algorithm for even a small number of iterations.
Now if you're not doing this for a particular application, but just
to try to invent a `better' compositeness test for the sake of it, be
aware of the fact that this is a terrible line of research and most
likely a waste of time -- and if it turns out to be fruitful, it'll
be through theoretical advances and not brute-force search of
exceptions (the primes are infinite after all, and computational
power is finite).
Décio
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20051205/488c3ca3/PGP.bin
More information about the gmp-discuss
mailing list