mpz_probab_prime_p() failures
Alan McFarlane
alan.mcfarlane at gmail.com
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
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
[/code]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://gmplib.org/list-archives/gmp-discuss/attachments/20051204/02058eb8/attachment.html
More information about the gmp-discuss
mailing list