documentation bug
paul zimmermann
Paul.Zimmermann at inria.fr
Tue Jun 6 10:38:05 UTC 2017
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
More information about the gmp-bugs
mailing list