mpz_probab_prime_p() failures

[Décio Luiz Gazzoni Filho]

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