# Primality testing using the factorization of n – 1

This section presents results which can be used to prove that an integer *n* is prime, provided that the factorization or a partial factorization of *n—* 1 is known. It may seem odd to consider a technique which requires the factorization of *n -* 1 as a subproblem — if integers of this size can be factored, the primality of *n* itself could be determined by factoring *n.* However, the factorization of *n*—1 may be easier to compute if *n* has a special form, such as a *Fermat number n* = 2^{2} +1. Another situation where the factorization of *n -* 1 may be easy to compute is when the candidate *n* is “constructed” by specific methods (see §4.4.4).

- 4.38 Fact Let
*n >*3 be an integer. Then*n*is prime if and only if there exists an integer*a*satisfying:- (i) a
^{n_1}= 1 (mod n); and - (ii)
*aS*1 (mod^{n}'^{l}^^{q}ф*n)*for each prime divisor*q*of*n —*1.

- (i) a

This result follows from the fact that Z* has an element of order *n —* 1 (Definition 2.128) if and only if n is prime; an element *a* satisfying conditions (i) and (ii) has order *n* — 1.

4.39 Note *(primality test based on Fact 4.38*) If *n* is a prime, the number of elements of order *n* - 1 is precisely *ф(п -* 1). Hence, to prove a candidate *n* prime, one may simply choose an integer *a **e* Z„ at random and uses Fact 4.38 to check if *a* has order *n -* 1. If this is the case, then n is certainly prime. Otherwise, another *a* € Z„ is selected and the test is repeated. If n is indeed prime, the expected number of iterations before an element *a* of order *n —* 1 is selected is O(lnlnn); this follows since (n - *)/ф(п* - 1) < 6 In Inn for

*n >* 5 (Fact 2.102). Tlius, if such an *a* is not found after a “reasonable” number (for example, 12 In In n) of iterations, then *n* is probably composite and should again be subjected to a probabilistic primality test such as Miller-Rabin (Algorithm 4.24).^{[1]} This method is, in effect, a probabilistic compositeness test.

The next result gives a method for proving primality which requires knowledge of only a *partial* factorization of n — 1.

- 4.40 Fact (
*Pocklington’s theorem*) Let*n >*3 be an integer, and let*n = RF*+ 1 (i.e.*F*divides*n -*1) where the prime factorization of*F*is*F*= П^=1*Qj*If there exists an integer^{J}■*a*satisfying:- (i) a”
^{-1}= 1 (mod гг); and - (ii) gcd(a(”~
^{1})/^{J — 1, гг) = 1 for each j, 1 < j < t,}

- (i) a”

then every prime divisor *p* of *n* is congruent to 1 modulo *F.* It follows that if *F > yjn -* 1, then *n* is prime.

If *n* is indeed prime, then the following result establishes that most integers *a* satisfy conditions (i) and (ii) of Fact 4.40, provided that the prune divisors of *F > s/n -* 1 are sufficiently large.

4.41 Fact Let *n = RF +* 1 be an odd prune with *F > ^/n* - 1 and gcd*(R, F)* = 1. Let the distinct prime factors of *F* be гд, *a < n* — 1, satisfies both: (i) a" ^{1} = 1 (mod n); and (ii) gcd(«^^{!_1}-^{)/,' — 1, n) = 1 for each j, 1 < j < t, is П'=1 (1 - 1/<ц) > 1 - E;=i 1 /Чу}

*
*

Thus, if the factorization of a divisor *F > s/n -* 1 of *n* - 1 is known then to test *n* for primality, one may simply choose random integers *a* in the interval [2, *n -* 2] until one is found satisfying conditions (i) and (ii) of Fact 4.40, implying that *n* is prime. If such an *a *is not found after a “reasonable” number of iterations,^{[2]} then *n* is probably composite and this could be established by subjecting it to a probabilistic primality test (footnote 3 also applies here). This method is, in effect, a probabilistic compositeness test.

The next result gives a method for proving primality which only requires the factorization of a divisor *F* of *n* - 1 that is greater than (/n. For an example of the use of Fact 4.42, see Note 4.63.

4.42 Fact Let *n* > 3 be an odd integer. Let *n* = 2*RF +* 1, and suppose that there exists an integer *a* satisfying both: (i) *a"* ^{1} = 1 (mod ?г); and (ii) gcd(oI"^{_1)}^ - l. n) = 1 for each prime divisor *q* of *F.* Let *x >* 0 and *у* be defined by 2*R = xF + у* and 0 *< у < F. *If *F > 1/F* and if *y*^{2}* - 4x* is neither 0 nor a perfect square, then *n* is prune.