Infinite loop in mpz_probab_prime_p

Torbjorn Granlund tege at
Thu Mar 3 19:33:48 CET 2005

"Darin Ohashi" <darin242 at> 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
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.


More information about the gmp-bugs mailing list