reported to me by Bob Baillie (through Sam Wagstaff): >Anyway, on page 111 of the manual (section 15.7.1, Prime Testing) >https://gmplib.org/gmp-man-6.1.2.pdf >where it describes the algorithm for mpz_probab_prime_p, it says, > >"For an odd input n, and with n = q*2^k + 1 where q is odd, this algorithm >selects a random base x and tests whether > x^q mod n is 1 or -1, >or an > x^(q2^j) mod n is 1, for 1 <= j <= k. >If so then n is probably prime, if not then n is definitely composite." > >It looks like they are trying to describe the strong probable prime test. >However, in a strong probable prime test, the second check should be > x^(q2^j) mod n is -1, for 1 <= j < k. > >The manual is wrong, right? Do you know if the code is correctly written?
Paul Zimmermann _______________________________________________ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs