Infinite loop in mpz_probab_prime_p
Torbjorn Granlund
tege at swox.com
Thu Mar 3 19:33:48 CET 2005
"Darin Ohashi" <darin242 at hotmail.com> writes:
I have an integer that seems to cause mpz_probab_prime_p to go into an
infinite loop. Similarly sized and much larger integers finish almost
instantly.
Perhaps these faster numbers quickly identified as composite?
I've let my code run for over an hour without the call finishing.
There is some amazingly stupid code in mpz/pprime_p.c that
will cause long delays:
ln2 = mpz_sizeinbase (n, 2) / 30; ln2 = ln2 * ln2;
for (q = PP_FIRST_OMITTED; q < ln2; q += 2)
{
...
}
This loop is supposed to find any small divisor of the number,
thus proving it composite.
In your case, ln2 will become 96884649. That's a long loop...!
I'll think of this and come up with a solution.
If you're in a hurry, you can simply remove the statement "ln2 =
ln2 * ln2" to shorten the division loop.
--
Torbjörn
More information about the gmp-bugs
mailing list