Bug in mpz_probab_prime_p (infinite loop)

[Mark Rodenkirch]

You are correct.  I was not patient enough.  It took about 10 minutes  
for the Miller-Rabin test.  I probably only waited about half of that  
time.  What's really odd is that it takes so long compared to other  
numbers of the same size.  Other numbers of that size take only a  
fraction of a second for a Miller-Rabin test.

--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