Bug in mpz_probab_prime_p (infinite loop)

[Mark Rodenkirch]

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 would give config options, but I could reproduce this on PowerPC G5  
(64-bit) and Pentium 4.  On PowerPC I compiled with -O3 for one run  
then -g (in  a weak attempt to debug) in another.

gcc versions:  gcc version 4.0.1 (Apple Computer, Inc. build 5363)
and:  gcc 3.4.2 (mingw-special)

uname -a:  Darwin MGRs-Computer.local 8.7.0 Darwin Kernel Version  
8.7.0: Fri May 26 15:20:53 PDT 2006; root:xnu-792.6.76.obj~1/ 
RELEASE_PPC Power Macintosh powerpc
and:  MINGW32_NT-5.1 DD90VX41 1.0.10(0.46/1/1) 2004-03-15 07:17 i686  
unknown

config.guess results:  powerpc970-apple-darwin8.7.0
and:  pentium4-pc-mingw32


Due to the different CPUs, versions of GMP and versions of gcc, it  
strongly suggests that the loop is in GMP itself.

If you need additional information, let me know.

--Mark