Appendix F: Recognizing Primes - Codes: The Guide to Secrecy from Ancient to Modern Times - page 555

Analysis
The reason the authors of [6]considered equations of type (F.2) was that
they were able to prove the following.

Polynomial Primality Criterion

If a ∈ Z , n ∈ N with n> 1, and gcd( a,n ) = 1, then n is prime if and only if

( X + a ) n X n + a (mod n ) . ≡ (F.3)

The satisfaction of polynomial congruence (F.3) is a simple test but the
time taken to test the congruence is too expensive. To save time, they looked
at the congruence modulo a polynomial, whence congruence (F.2). However,
by looking at such congruences, they introduced the possibility that composite
numbers might satisfy (F.2), which indeed they do. Yet, the authors were able
to (nearly) restore the characterization given in the above polynomial primality
criterion by showing that for a suitably chosen r , if (F.2) is satisfied for several
values of a , then n must be a prime power. Since the number of a values and the
suitably chosen r value are bounded by a polynomial in log 2 ( n ), they achieved
a deterministic polynomial time algorithm for primality testing.
The authors of [6]were able to to establish the following facts about their
algorithm. The reader will need the concepts of ceiling and floor functions (see
pages 473 and 474 in Appendix A).

Facts Concerning Algorithm F.1

1. The algorithm outputs “ n is prime” if and only if n is prime. (Hence, it
outputs “ n is composite” if and only if n is composite.)

such that ord r ( n ) > 4 log 2 ( n ).
3. The asymptotic time complexity of the algorithm is O (log 10 . 5+ ε
2

16 log 2 ( n ) 2. There exists and r ≤

( n )) for

any ε> 0.

4. It is conjectured that the time complexity of the algorithm can be im-
proved to the best-case scenario where r = O (log 2 ( n )), which would
mean that the complexity of the algorithm would be

O (log 6+ ε
2

( n )) for any ε> 0 .

Two conjectures support the authors' conjecture in part 4 above. They are
given as follows.