 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 = 22 +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) an_1 = 1 (mod n); and
• (ii) aSn' l^q ф 1 (mod n) for each prime divisor q of n — 1.

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). 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 QjJ If there exists an integer a satisfying:
• (i) a”-1 = 1 (mod гг); and
• (ii) gcd(a(”~1)/J — 1, гг) = 1 for each j, 1 < j < t,

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 гд, 2,... > Then the probability that a randomly selected base a, 1 < 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, 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 = 2RF + 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 2R = xF + у and 0 < у < F. If F > 1/F and if y2 - 4x is neither 0 nor a perfect square, then n is prune.

•  ! Another approach is to run both algorithms in parallel (with an unlnmted number of iterations), until one ofthem stops with a definite conclusion ''prune" or "composite".
•  Thenumberof iterations may be taken to be T where PT < (f)100, and where P = 1 - П) i (1 — V'/j)-