mpz_probab_prime_p() failures

Alan McFarlane alan.mcfarlane at
Sun Dec 4 22:26:25 CET 2005

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?

[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

[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


-------------- next part --------------
An HTML attachment was scrubbed...

More information about the gmp-discuss mailing list