tg at gmplib.org
Tue Jun 6 12:00:16 UTC 2017
paul zimmermann <Paul.Zimmermann at inria.fr> writes:
>Anyway, on page 111 of the manual (section 15.7.1, Prime Testing)
>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,
> 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?
Also reported directly to GMP...
We seem to have been more lucky with the implementation than with the
Perhaps this suggests that we should stop writing seperate
documentation? After all, the .c and .asm files document the library in
detail, including all bugs. :-)
Please encrypt, key id 0xC8601622
More information about the gmp-bugs