Bug in mpz_probab_prime_p (infinite loop)
Mark Rodenkirch
rogue at wi.rr.com
Sun Sep 17 15:34:38 CEST 2006
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
More information about the gmp-bugs
mailing list