Bug in mpz_probab_prime_p (infinite loop)

[Torbjorn Granlund]

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));
      fflush(stdout);
  
      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:
http://gmplib.org/list-archives/gmp-bugs/2005-March/000189.html

-- 
Torbjörn