Error in manual (section 15.7.1, Prime Testing)

bobbaillie at frii.com bobbaillie at frii.com
Thu Jun 1 19:58:49 UTC 2017


Hi!

On page 111 of the manual (section 15.7.1, Prime Testing)
https://gmplib.org/gmp-man-6.1.2.pdf

you say

"For an odd input n, and with n = q2k + 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 you're 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.

If x^q is either 1 or -1 (mod n), and some x^(q2^j) = -1 (mod n) for j =
1...k-1, then n is a strong probable prime base x.

See Sam Wagstaff's book, "The Joy of Factoring", or the paper, "The
Pseudoprimes to 25*10^9 by Pomerance, Selfridge, and Wagstaff.

Yours truly,
Robert Baillie



More information about the gmp-bugs mailing list