Bug in mpz_probab_prime_p (infinite loop)
Torbjorn Granlund
tege at swox.com
Sun Sep 17 09:20:17 CEST 2006
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