Bug in mpz_probab_prime_p (infinite loop)

[Mark Rodenkirch]

You are correct, I wasn't patient enough.  It took about 10 minutes  
to complete the Miller-Rabin test.  I probably waited about half that  
long before terminating the process.  To me (but probably not to  
others), it doesn't make much sense that a Miller-Rabin test on most  
numbers of similar size takes a fraction of a second.

--Mark

On Sep 17, 2006, at 2:20 AM, Torbjorn Granlund wrote:

> 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