Finding primes & proving primality 3.3: Combined Tests Home > Primality Proving > Chapter Three > Combined Tests

In previous sections we have pointed out if the factored portion of n-1 or of n+1 is larger than the cube root of n, then we can prove n is prime.  In this section we discuss the case that the product of these two factored portions is greater than the cube root of n, then we can prove n prime using a combined test.  (If we can not find enough factors to prove n prime this way, then we must use the generalized tests of the following chapter.)

Let n > 1 be an odd integer.  Let n-1 = F₁R₁ and n+1 = F₂R₂ where F₁ and F₂ are completely factored, and gcd(F₁,R₁) = gcd(F₂,R₂) = 1.  The two types of tests we have applied to n in the previous sections are as follows.

Condition I.  For each prime p dividing F₁ there is an integer a such that

• a^n-1 ≡ 1 (mod n), but
• gcd(a^(n-1)/p-1, n) = 1.
  

Condition II.  Let (d|n) = -1.  For each prime p dividing F₂ there is a Lucas sequence with discriminant d such that

• U(n+1) ≡ 0 (mod n), and
• gcd(U((n+1)/p), n) = 1.

Pocklington's theorem tells us that if (I) is true, then each prime factor q of n has the form k·F₁+1.  About 60 years later Morrison proved that if (II) held, then each prime factor q of n has the form k·F₂±1 [Morrison75].  Together these give us the following:

Combined Theorem 1:  Suppose n, F₁, F₂, R₁, R₂ are as above and conditions (I) and (II) are satisfied.  If n < max(F₁²F₂/2 , F₁F₂²/2), then n is prime.

Proof.  Let q be a prime factor of n and let n = mq.  From Condition I we have that q ≡ 1 (mod F₁), so since n is 1 (mod F₁), so is m.  From Condition (II) we know q = ±1 (mod F₂), so since n is -1 (mod F₂), either q or m is 1 (mod F₂).  We may assume that m = 1 (mod F₂), because if every prime factor q of n was 1 (mod F₂), we'd have the contradiction that n ≡ 1 (mod F₂).  Finally gcd(F₁,F₂)=2, so we can combine these to get that m ≡ 1 (mod F₁F₂/2). So for n to be composite we must have both

• n =  qm >  ( 1 + F₁)(1 + F₁F₂/2)  >  F₁²F₂/2, and
• n  =  qm  >  (-1 + F₂)(1 + F₁F₂/2)  >  F₁F₂²/2.

This completes the proof of the theorem.

Adding in a factoring bound

Sometimes, if n is small enough that we have almost enough factors to use the above (or similar) results, it can be helpful to bring in information about how far we have tried to factor n±1.  Suppose, for example, that all of the prime factors of R₁ and R₂ are greater than B.  Next apply the conditions above to R₁ and R₂

Condition III.  There is an integer a such that

• a^n-1 ≡ 1 (mod n), but
• gcd(a^(n-1)/R₁ -1, n) = 1.

Condition IV.  Let (d|n) = -1.  There is a Lucas sequence with discriminant d (same d as used in condition II) such that

• U(n+1) ≡ 0 (mod n), and
• gcd(U((n+1)/R₂), n) = 1.

These two conditions inform us respectively that every prime factor q of n has the form k·u+1 where u is a prime factor of R₁; and every prime factor q also has the form k·v±1 where v is a prime factor of R₂.  (Note that the factors u and v are dependent on q.)  Of course u and v must each be larger than the factoring bound B.  With the above notation we can now state our final classical theorems.  (For the first the proof is virtually identical to the proof above.)

Combined Theorem 2:  Suppose n, F₁, F₂, R₁, R₂, B are as above and conditions (I) through (IV) are satisfied.  Define integers r and s by R₁ = sF₂/2 + r with 0 < r < F₂/2.  If

n < max(B·F₁ + 1, B·F₂ - 1) (B²F₁F₂/2 + 1)

then n is prime.

Combined Theorem 3:  Suppose n, F₁, F₂, R₁, R₂, B are as above and conditions (I) through (IV) are satisfied.  Again define integers r and s by R₁ = sF₂/2 + r with 0 < r < F₂/2.  If for some integer m

n < (m·F₁F₂ + r·F₁ + 1) (B²F₁F₂/2 + 1)

then either n is prime or kF₁F₂ +  rF₁ + 1 divides n for some non-negative integer k < m.

Both of these results (and more) can be found in "the" paper on the classical results: [BLS75].  Another excellent source on these theorems and their extensions is the excellent text H. Williams "Édouard Lucas and Primality testing" [Williams98]

How much further can we go?  It is possible to consider higher powers such as the factors of

n⁶ -1 = (n - 1)(n² + n + 1)(n + 1)(n² - n + 1).

(See [Williams78] for the theory and examples of these techniques).  But the cost in terms of mathematical complication is very high.  So in practice adding a few terms such as n²+n+1 or n²-n+1 is rarely worth the effort.  Rather it makes sense to just move on to the general primality proving methods of the next chapter.