Bug in mpz_probab_prime_p (infinite loop)

Torbjorn Granlund tege at swox.com
Sun Sep 17 09:20:17 CEST 2006

Mark Rodenkirch <rogue at wi.rr.com> writes:

  There appears to be an infinite loop in mpz_probab_prime_p.  Here are  
  the details:
  Version:  GMP 4.2.1 (on PowerPC G5)
  and:  GMP 4.1.99 (on Pentium 4)
  Test program that can reproduce the error:
  #include <gmp.h>
  #include <stdio.h>
  int main(int argc, char *argv[])
      mpz_t theNumber;
      mpz_init_set_ui(theNumber, 199);
      mpz_pow_ui(theNumber, theNumber, 14869);
      mpz_sub_ui(theNumber, theNumber, 1);
      mpz_tdiv_q_ui(theNumber, theNumber, 198);
      printf("%d\n", mpz_probab_prime_p(theNumber, 1));
      return 0;
  The mpz_probab_prime_p never returns for this number.  If I change  
  the exponent to 14870 or 14868 it returns almost instantaneously.
I cannot reproduce this, but perhaps I am simply more patient
than you.  :-)

How long did you wait before you came to the conclusion that
there is an infinite loop?

Our aging Opteron system needed 7 minutes to return.  While 7
minutes might seem like a long time, I don't think it is quite
long enough to qualify as "infinte".  A better approximation of
infinte is some typical large number, e.g., 4711.

I think you'll find a more useful answer here:


More information about the gmp-bugs mailing list