paul zimmermann <[email protected]> writes: >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? Also reported directly to GMP...
We seem to have been more lucky with the implementation than with the documentation. 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. :-) -- Torbjörn Please encrypt, key id 0xC8601622 _______________________________________________ gmp-bugs mailing list [email protected] https://gmplib.org/mailman/listinfo/gmp-bugs
