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.

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

**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 = *F*_{1} *R*_{1},
2|*F*_{1}, gcd(*F*_{1}, *R*_{1}) = 1 and
*F*_{1} is completely factorized into verified primes.
Suppose also that for each prime factor *f* of *F*_{1}, there exists a
number *b* such that 1 < *b* < *N* − 1,
*b*^{N − 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 *F*_{1}).

**Morrison's Theorem**

Suppose *N* + 1 = *F*_{2} *R*_{2}, 2|*F*_{2},
gcd(*F*_{2}, *R*_{2}) = 1 and *F*_{2} 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 {*U*_{k}} with discriminant *D* = *P*^{2} − 4*Q*,
where gcd(*N*, *Q*) = 1, for which *U*_{N + 1} = 0
(mod *N*) and gcd(*U*_{(N + 1)/f}, *N*) = 1.
Then, by Morrison's Theorem [BLS1975, Theorem 16],

(2)... *d* ≡ ±1 (mod *F*_{2}).

**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 *v*_{p}(*x*) the exponent of the largest power
of *p* that divides *x* and by *ζ*_{n} the *n*-th
root of unity *e*^{2 π 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}
* q*^{vq(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* = *v*_{p}(*q* − 1) and let *χ* be the
character modulo *q* of order *p*^{k} defined by *χ*(*x*)
= (*ζ*_{pk})^{indg(x)},
where *g* is a primitive root modulo *q*. Assume gcd(*N*, *S**T*)
= 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 *L*_{p} is satisfied. Then

(3)... *d* ≡ *N*^{i} (mod *S*) for some *i*,
0 < *i* < *T*.

**Condition (* β)**

Let *q*, *p*, *k* and *χ* be as above; *q*|*S*,
*p*^{k}||*q* − 1, and *χ* is a character modulo *q*
of order *p*^{k}. Let *σ*_{x} denote the
homomorphism of ** Z**[

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 *p*^{k}-th root of unity modulo *N*.
If also condition *L*_{p} 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{*p*^{k}/2 < *x* < *p*^{k},
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} [*N**x*/*p*^{k}]
(*σ*_{x})^{−1}

and

*c* = 2 (2^{(p − 1) pk − 1} − 1) / *p*^{k}.

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

*β* = ∑_{0 < x < 2k,
x ≡ 1 or 3 (mod 8)} [3*x*/2^{k}]
(*σ*_{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)} [*N**x*/2^{k}] (*σ*_{x})^{−1},

*c* = 3 (3^{2k − 2} − 1)/2^{k}

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 L_{p}**

For prime *p* we say that condition *L*_{p} is satisfied
if for all prime divisors *r* of *N* and all integers *a* >
0 we can find an integer *l*_{p}(*r*, *a*) such that

*r*^{p − 1} ≡ *N*^{(p − 1) lp(r,
a)} (mod *p*^{a}).

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

*p* > 2 and *N*^{p − 1} is not congruent to 1 (mod
*p*^{2}).

However, if (**β*) is satisfied and if *η*(*χ*) is
a primitive *p*^{k}-th root of unity, then condition *L*_{p}
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*, *F*_{1} *F*_{2}) = 1, Let *G* = *F*_{1}
*F*_{2} *S*/2. We require *G*^{3} > *N*.

From the conditions (1), (2) and (3) above, by the Chinese Remainder
Theorem, *d* must belong to one of at most 2*T* 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 *G*^{2} > *N*, *N* is prime.

Otherwise, let *F* be the greater of *F*_{1} and *F*_{2}. Let
*H* = *G* *F*^{2}. In addition to
*G*^{3} > *N*, the final condition we require is that *m**H*
> *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 =
*F**R*, 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 *b*^{N − 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, *c**F*
+ 1 and *d**F* + 1. Furthermore, if

*N* < *G* (2*aF*^{2} − *G* + *r**F* + 2)

for some *a* > 0, where *r* and *s* are defined by
*R* = 2*F**s* + *r*, 0 < *r* < 2*F*,
then 2(*s* − *a*) < *c**d* ≤ 2*s*.

**Theorem 2**. Suppose *N* is composite, suppose *N* + 1 =
*F**R*, 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 {*U _{}*

*N* < *G* (2*aF*^{2} + *G* − |*r**F* −
2|)

for some *a* > 0, where *r* and *s* are defined by
*R* = 2*F**s* + *r*, |*r*| <
*F*, then 2(*s* − *a*) < *c**d* ≤ 2(*s*
+ *a*).

**References**

[BLS1975] J. Brillhart, D.H. Lehmer and J.L. Selfridge, 'New Primality
Criteria and Factorizations of 2^{m} ± 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.