VFYPR

A PC program for verifying primes

VFYPR is uses a combination of methods to verify primes: Factorization of N − 1, factorization of N + 1, and the APRCL method. The implementation of the APRCL algorithm is a more-or-less direct conversion of APRT-CLE from UBASIC to C, and somewhat extended to handle numbers of up to about 3000 digits.

An outline of the algorithm is given below.

The program runs on PC systems under MSDOS. Download it from here.

Get instructions from here.

Email me if you have any comments or bug reports. Email address: anthony.d.forbes@gmail.com.

Description of the primality proving algorithm

Preliminary tests

We assume N is not too small. We also assume that N is not divisible by any of the relevant parameters of the algorithm. This is achieved by trial-dividing N by anything that could cause trouble.

Let N be given and suppose d is a prime divisor of N.

Pocklington's Theorem

Suppose N − 1 = F1 R1, 2|F1, gcd(F1, R1) = 1 and F1 is completely factorized into verified primes. Suppose also that for each prime factor f of F1, there exists a number b such that 1 < b < N − 1, bN − 1 = 1 (mod N) and gcd(b(N − 1)/f − 1, N) = 1. Then, by Pocklington's Theorem [BLS1975, Theorem 4],

(1)... d ≡ 1 (mod F1).

Morrison's Theorem

Suppose N + 1 = F2 R2, 2|F2, gcd(F2, R2) = 1 and F2 is completely factorized into verified primes. Suppose also that there is an integer D such that (D/N) = −1 and for each prime factor f of F, there exists a Lucas sequence {Uk} with discriminant D = P2 − 4Q, where gcd(N, Q) = 1, for which UN + 1 = 0 (mod N) and gcd(U(N + 1)/f, N) = 1. Then, by Morrison's Theorem [BLS1975, Theorem 16],

(2)... d ≡ ±1 (mod F2).

The APRCL method

This part follows closely Section 9.1 of Henri Cohen's book [C1995]. See also the paper of Cohen & Lenstra [CL1987].

Denote by vp(x) the exponent of the largest power of p that divides x and by ζn the n-th root of unity e2 π i / n. Let χ be a character modulo q. The Gauss sum is defined by

τ(χ) = ∑x in (Z/qZ)* χ(x) (ζq)x.

Let χ and ψ be characters modulo q. The Jacobi sum is defined by

j(χ, ψ) = ∑x in (Z/qZ)* χ(x) ψ(1 − x).

Let T be an even integer. Write

e(T) = 2 ∏q prime, q − 1|T qvq(T) + 1.

Let S be a factor of e(T) such that gcd(S, e(T)/S) = 1.

For each pair of primes q|S and p|q − 1, let k = vp(q − 1) and let χ be the character modulo q of order pk defined by χ(x) = (ζpk)indg(x), where g is a primitive root modulo q. Assume gcd(N, ST) = 1. Assume that for each pair (p, q) the character χ satisfies condition (*β) for some β for which (ζp)β is not equal to 1. Suppose also that for all primes p|T, condition Lp is satisfied. Then

(3)... dNi (mod S) for some i, 0 < i < T.

Condition (*β)

Let q, p, k and χ be as above; q|S, pk||q − 1, and χ is a character modulo q of order pk. Let σx denote the homomorphism of Z[ζpk] that sends ζpk to (ζpk)x. If h = A σa + B σb + ... is a linear combination of such homomorphims and if f(ζpk) is a polynomial in ζpk, we use the expression f(ζpk)h to denote the product f((ζpk)a)A f((ζpk)b)B ....

The condition (*β) is defined by

(*β) τβ (NσN)η(χ)−β N (mod N)

for some η(χ) in <ζpk>.

When applying the (*β) test it is sufficient to show that τβ(NσN) is congruent to a pk-th root of unity modulo N. If also condition Lp is satisfied, then in fact η(χ) = χ(N) [C1995, Proposition 9.1.11].

For a practical primality-proving algorithm we replace (*β) by equivalent conditions involving Jacobi sums.

Suppose p > 2 (and p < 1093) [C1995, Proposition 9.1.20]. Let

β = sum{pk/2 < x < pk, gcd(x, p) = 1: (σx)−1}.

Then (ζp)β is not equal to 1, and condition (*β) is equivalent to the congruence

j(χ, χ)αη(χ)cN (mod N),

where

α = ∑0 < x < pk, gcd(x, p) = 1 [Nx/pk] (σx)−1

and

c = 2 (2(p − 1) pk − 1 − 1) / pk.

Suppose p = 2 and k > 2 [C1995, Corollary 9.1.23]. Let

β = ∑0 < x < 2k, x ≡ 1 or 3 (mod 8) [3x/2k] (σx)−1.

Then (ζp)β is not equal to 1, and condition (*β) is equivalent to the congruence

(j(χ, χ) j(χ, χ2))α j(χ2k − 3, χ3*2k − 3)2 δ ≡ (−1)δ η(χ)cN (mod N),

where

α = ∑0 < x < 2k, x ≡ 1 or 3 (mod 8) [Nx/2k] (σx)−1,

c = 3 (32k − 2 − 1)/2k

and

δ = 0 if N ≡ 1 or 3 (mod 8),

δ = 1 if N ≡ 5 or 7 (mod 8).

Suppose p = 2 and k = 2. Then condition (*1) is equivalent to the congruence

j(χ, χ)(N − 1)/2 q(N − 1)/4η(χ)−1 (mod N)

if N ≡ 1 (mod 4), and to the congruence

j(χ, χ)(N + 1)/2 q(N − 3)/4 ≡ − η(χ) (mod N)

if N ≡ 3 (mod 4).

Suppose p = 2 and k = 1. Then condition (*1) is equivalent to the congruence

q(N − 1)/2η(χ) (mod N)

if N ≡ 1 (mod 4), and to the congruence

q(N − 1)/2 ≡ − η(χ) (mod N)

if N ≡ 3 (mod 4).

Condition Lp

For prime p we say that condition Lp is satisfied if for all prime divisors r of N and all integers a > 0 we can find an integer lp(r, a) such that

rp − 1N(p − 1) lp(r, a) (mod pa).

Assume that we can find a character χ modulo q of order pk and a β, with (ζp)β not equal to 1, for which (*β) is satisfied. Then condition Lp is satisfied if the following additional condition is true:

p > 2 and Np − 1 is not congruent to 1 (mod p2).

However, if (*β) is satisfied and if η(χ) is a primitive pk-th root of unity, then condition Lp is satisfied if one of the following additional conditions is true [C1995, Proposition 9.1.17]:

(i) p > 2

(ii) p = 2, k = 1 and N ≡ 1 (mod 4)

(iii) p = 2, k > 1 and q(N − 1)/2 ≡ −1 (mod N).

Checking the divisors d of N

Assume gcd(S, F1 F2) = 1, Let G = F1 F2 S/2. We require G3 > N.

From the conditions (1), (2) and (3) above, by the Chinese Remainder Theorem, d must belong to one of at most 2T residue classes mod G. We compute the representatives of these residue classes which are less than G and try them one by one as possible non-trivial divisors of N. If there are none, we can conclude that d > G.

If G2 > N, N is prime.

Otherwise, let F be the greater of F1 and F2. Let H = G F2. In addition to G3 > N, the final condition we require is that mH > N, where m is not too large. (m < 1000000000, say.) For then we can complete a primality proof by means of one of the following theorems.

Theorem 1. Suppose N is composite, suppose N − 1 = FR, where F is even, R is odd, R > 1 and gcd(F, R) = 1. Suppose also that for each prime factor f of F, there is an integer b, 1 < b < N−1, such that bN − 1 ≡ 1 (mod N) and gcd(b(N − 1)/f − 1, N) = 1. If every prime factor of N is greater than G, then N is the product of two primes, cF + 1 and dF + 1. Furthermore, if

N < G (2aF2G + rF + 2)

for some a > 0, where r and s are defined by R = 2Fs + r, 0 < r < 2F, then 2(sa) < cd ≤ 2s.

Theorem 2. Suppose N is composite, suppose N + 1 = FR, where F is even, R is odd, R > 1 and gcd(F, R) = 1. Suppose there exists an integer D for which (D/N) = −1 and also for each prime factor f of F a Lucas sequence {Ui} with discriminant D such that N divides UN+1 and gcd(U(N+1)/f, N) = 1. If every prime factor of N is greater than G, then N is the product of two primes, cF + e and dFe, where e = 1 or −1. Furthermore, if

N < G (2aF2 + G − |rF − 2|)

for some a > 0, where r and s are defined by R = 2Fs + r, |r| < F, then 2(sa) < cd ≤ 2(s + a).

References

[BLS1975] J. Brillhart, D.H. Lehmer and J.L. Selfridge, 'New Primality Criteria and Factorizations of 2m ± 1', Mathematics of Computation, 29 (1975), 620-647.

[CL1987] H. Cohen & A. K. Lenstra, 'Implementation of a new primality test', Math. Comp., 48 (1987), 103-121.

[C1995] Henri Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin, 1995.