PRIMALITY TESTING

AADITYA BILAKANTI

Abstract. This paper covers and analyzes various different primality tests, including some
“lesser known ones”. We also investigate the distribution of primes whose first Euler–Jacobi
Pseudoprime is not a Carmichael number.

Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1. Fundamental Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2. Theorems from Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3. Results from Group Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3. Probabilistic Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1. Fermat Primality Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2. Solovay–Strassen Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3. Miller–Rabin Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.4. Lucas Probable Prime Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.5. Baillie–PSW Primality Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4. Deterministic Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1. AKS Primality Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5. Future Directions and Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.1. Euler Jacobi Pseudoprimes and Carmichael Numbers . . . . . . . . . . . . . . . . . . . 33
5.2. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

1. Introduction
A prime number is a number that only divides 1 and itself, first defined by Euclid. He
also proved that there are an infinite amount of primes. Another Greek mathematician,
Eratosthene, created a method in order to find prime numbers called the Sieve of Eratosthenes.
The algorithm first involved listing all the numbers from 2 through an integer n, giving us
Date: July 13, 2024.
1
2 AADITYA BILAKANTI

the list 2, 3, 4, . . . , n. We then take the smallest number in the list and “cross out” all of its
multiples (starting at 2 in this case): 2, 3, 4
, 5, 6
, 7, 8
, 9, 
10,
 . . . , n. We now repeat this for 3,
and so on. The numbers left at the end of this process are primes. However, this method is
extremely inefficient for large primes. Another method to determine the primality of n is to
check if n is divisible by any of the numbers from 2 through n − 1. However, this also gets
quite inefficient for large n (the time complexity is O(n)), √ so a small optimization can be
made, which is that we only have to test the numbers ≤ n. We prove this below:
√
Theorem 1.1. If a number n is not divisible by any of the positive numbers ≤ n, then n is
prime.
√
Proof. Suppose that n divides a positive integer q such that 2 ≤ q ≤ n. This would mean
that n is composite. If n did not divide any such √ integer, this would mean that n√is prime,
n
since this implies that there are no factors ≥ n that divide n. Note that q ≥ n, since
n √ √
q
≥ √nn = n. Therefore, it is redundant to check numbers > n if we already know that
√
no numbers ≤ n divide n. ■
We can slightly optimize this further by noticing that a prime must be√ of the form 6k ± 1,
so therefore, we only have to test numbers of the form 6k ± 1 that are ≤ n. We now define
certain types of algorithms that we reference throughout the paper:
Unconditional: An algorithm is unconditional if it does not use any unproven theorems
or conjectures. The opposite of this is a conditional test, meaning that it does depend
on certain unproven conjectures.
General: A general algorithm works for any number n, and does not rely on specific
qualities of the number.
Deterministic: An algorithm is deterministic if it gives the same result every time it
is run. In the context of Primality Testing, it would also mean that the algorithm
always identifies whether a number is a prime or a composite correctly.
Probabilistic: An algorithm is probabilistic if it does not give the same result every
time. Rather, it gives an answer with some chance that it is correct. Probabilistic
tests often require multiple iterations to give an answer with reasonable confidence.

2. Preliminaries
We first define some useful symbols that will be needed later on in the paper:
 
Definition 2.1. We define ap as the Legendre Symbol, where p is an odd prime number
and a ∈Zas follows:
(1) ap = 1 if a is a quadratic residue modulo p and a ̸≡ 0 (mod p)
 
(2) ap = -1 if a is a non-quadratic residue modulo p
 
(3) ap = 0 if a ≡ 0 (mod p)
 PRIMALITY TESTING 3

Definition 2.2. Let n be an odd positive integer that can be factorized as pb11 ·pb22 ·pb33 · . . .
·pbkk
(p1 , p2 , p3 . . . pk are prime numbers), and let a ∈ Z. We define the Jacobi Symbol, na , as
follows:  b1  b2  b3  bk
a a a a
· · · ... · ,
p1 p2 p3 pk
 
where ap is the Legendre Symbol.

We now will give the following lemmas about the Jacobi Symbol, which be will be
particularly useful to us when going over the Solovay–Strassen test. The proofs for these
are omitted, as they mainly rely on the properties of Jacobi Symbols. See [Bur10] for these
proofs.
Lemma 2.3. If a ≡ b (mod n), then na = nb , where a, b, and n are integers.

Lemma 2.4.
Let a and n be integers. If either the top or the bottom argument of the Jacobi
Symbol na is fixed, then the Jacobi Symbol is completely multiplicative for the remaining
argument.
a


Lemma 2.5. Let a and n be integers. If gcd(a, n) = h, where h ̸
= 1 then n
= 0. Otherwise,
a


n
= ±1.
Theorem 2.6 (Law of Quadratic Reciprocity). If a and b are odd positive relatively prime
integers, then:
a  b  a−1 b−1
= −1 2 · 2 ,
b a
a b a



b

where b and a are Jacobi Symbols. If n or m ≡ 1 (mod 4), then b a
= 1. If
a

b

n ≡ m ≡ 3 (mod 4), then b a = −1.
Lemma 2.7
(1st supplement of the
Law of Quadratic Reciprocity). Let n be an odd positive
n−1
integer. −1 −1 −1


n
= (−1) 2 , where
n
is the Jacobi Symbol. If n ≡ 1 (mod 4), then n
= 1.
−1


Otherwise, if n ≡ −1 (mod 4), then n = −1.
Lemma 2.8 (2nd supplement of the Law of Quadratic Reciprocity). Let n be an odd positive
n2 −1
integer. n2 = (−1) 8 , where −1 −1




n
is the Jacobi Symbol. If n ≡ ±1 (mod 8), then n
= 1.
−1


Otherwise, if n ≡ ±3 (mod 8), then n = −1.
Definition 2.9. We define the notation orda (b) to be the multiplicative order of b modulo a.
The multiplicative order of b modulo a is the smallest number d such that bd ≡ 1 (mod a).
Note that a and b must be relatively prime.
We now prove a useful theorem about orders:
Theorem 2.10. Let a and b be positive integers that are relatively prime, and let n be an
integer such that an ≡ 1 (mod b). Then d | n, where d = ordb (a).
4 AADITYA BILAKANTI

Proof. Let n = qd + r, where q is a positive integer and 0 ≤ r < d. We therefore see that
an ≡ 1 (mod n) can be represented as aqd+r ≡ 1 (mod n). We know that aqd ≡ 1 (mod n),
so we have ar ≡ 1 (mod n). However, since we defined that r < d, we do not have a positive
r that satisfies this (since d is the smallest number such that ad ≡ 1 (mod n)). Therefore,
r = 0, and therefore, n = qd. This means that d | n. ■
Definition 2.11. We define ϕ(n) to be Euler’s Totient function (or the phi function), where
n = pb11 · pb22 · pb33 · . . . · pbkk (p1 , p2 , p3 . . . pk are prime numbers), as follows: n(1 − p11 )(1 −
1
p2
)(1 − p13 ) . . . (1 − p1k ). Euler’s Totient function calculates the amount of numbers between 1
and n that are relatively prime to n. We prove the formula later, along with Euler’s Totient
Theorem.
Definition 2.12. Define the recurrence polynomial f (x) = x2 − ax + b, where a and b are
integers such that ∆ = a2 − 4b is not a perfect square. We now create two sequences using
these values:
xj − (a − x)j
Uj = Uj (a, b) ≡ (mod f (x))
x − (a − x
Vj = Vj (a, b) ≡ xj + (a − x)j (mod f (x)),
where we define g(x) (mod f (x)) as the remainder when g(x) is divided by f (x). We can
also recursively define the sequences Uj and Vj as follows:
Uj = a · Uj−1 − b · Uj−2
Vj = a · Vj−1 − b · Vj−2 .
A third definition can also be created by letting p and q be the roots of f (x) as follows:
pn − q n
Uj =
p−q
Vj = p + q n .
n

Using these definitions, we can easily see that U0 = 0 and U1 = 1. For more information on
Lucas Sequences, see [CP05].
2.1. Fundamental Theorems. We now will give and prove some useful theorems that will
be important later on. We first prove Fermat’s Little Theorem (FLT), which states:
Theorem 2.13 (Fermat’s Little Theorem). If p is a prime number, then ap ≡ a (mod p).
Equivalently, if gcd(a, p) = 1, then ap−1 ≡ 1 (mod p).
Proof. We prove FLT by induction, with the base case being a = 1. This is of course
satisfies the congruence, and so we now assume that k p ≡ k (mod p), for some integer
p
k. We now
p−1 p

p−2 p

p−3this implies that (k + 1) ≡ k + 1 (mod p).
show that
p
We do this by adding
pk + 2 k +
3 k + . .
. + 1 to both sides of the congruence k ≡
k (mod p), which gives
us: k p + pk p−1 + p2 k p−2 + p3 k p−3 + . . . + 1 ≡ k + pk p−1 + p2 k p−2 + p3 k p−3 + . . . + 1 (mod p).


 PRIMALITY TESTING 5

However, the left hand side can be factored by the Binomial Theorem, giving us: (k + 1)p ≡
p p
p−1

p−2
p−3
k + pk + 2 k + 3 k + . . . + 1 (mod p). However, since all the middle terms on the
left hand side of the congruence are divisible by p, they become 0 (mod p). This means that
we can simplify the congruence to (k + 1)p ≡ k + 1 (mod p), which means we have shown that
k p ≡ k (mod p) implies that (k + 1)p ≡ k + 1 (mod p). Thus, we have proved this “version”
of FLT by induction. In order to obtain the other form of FLT stated in the theorem, notice
that we can divide both sides of the congruence by a if and only if gcd(a, p) = 1, which gives
us: ap−1 ≡ 1 (mod p). Therefore, we have proved FLT. ■
Theorem 2.14. If n = pb11 · pb22 · pb33 · . . . · pbkk (p1 , p2 , p3 . . . pk are prime numbers. Let
ϕ(n) be the amount of numbers relatively prime to n between 1 and n. Then ϕ(n) =
n(1 − p11 )(1 − p12 )(1 − p13 ) . . . (1 − p1k ).
Proof. We first show that ϕ(p), where p is a prime number, is equal to p − 1. This is true
because a prime must be relatively prime to all numbers less than it, by its definition. We
now use this to show that ϕ(pk ), where k is an integer is equal to pk−1 (p − 1). This is true
because we notice that the only way for a number not to be relatively prime to pk is if the
number is of the form cp, where c ≥ 1, and cp ≤ pk . We know that there are pk−1 numbers
of the form cp as we defined as above, since c can be any integer between 1 and pk−1 . This
means that there are a total of pk−1 numbers that are not relatively prime to pk that are
≤ pk . Since we know that there are a total of pk numbers, this means that the amount of
numbers relatively prime to pk is pk − pk−1 , which can be factored as pk−1 (p − 1), or pk (1 − p1 ).
We now prove that ϕ(n) is a multiplicative function, meaning that ϕ(ab) = ϕ(a)ϕ(b) when
gcd(a, b) = 1. Suppose we have the set of all positive numbers less than ab that are relatively
prime to ab called A, along with the same sets for a and b individually, which we shall call
Sets C and D respectively. We now define a function that takes every element a1 ∈ C and
b1 ∈ D and adds a new element d < ab such that d ≡ a1 (mod a) and d ≡ b1 (mod b). We call
this set B. We now prove the following lemma, which will be helpful to finding a relationship
between sets A and B:
Lemma 2.15. If x, a, b, c, and d are all positive integers where gcd(c, a) = 1, gcd(d, b) = 1
and gcd(a, b) = 1, then the solution to the congruence reduced (mod ab):
x ≡ c (mod a)
x ≡ d (mod b)
is relatively prime to ab.
Proof. We can solve this congruence by converting each of the congruences into linear
equations and substituting. This gives us that the solution to the congruence is x ≡
aa−1 d − aa−1 c + c (mod ab). We prove that gcd(aa−1 d − aa−1 c + c, ab) = 1. We prove this by
contradiction. Suppose that there exists some number gcd(aa−1 d − aa−1 c + c, ab) = h. We
first examine if h | a, meaning that h ∤ b (since a and b are relatively prime). We also know
that h | aa−1 d − aa−1 c + c. This means that h | c, since all the terms must be divisible by h in
6 AADITYA BILAKANTI

order for the whole expression to be divisible by h. However, this is a contradiction, since we
defined that gcd(a, c) = 1. If h | b, we instead use the solution x ≡ bb−1 c − bb−1 d + d (mod ab),
and using the same method, we find a contradiction. However, we could also have h | ab, with
h ∤ a and h ∤ b. Informally, this means that h shares some factors with a and b, but not all
its factors for either. Again, we know that h | aa−1 d − aa−1 c + c. In order for this to be true
h | c. However, since h shares some factors with a, this means that gcd(a, c) ̸= 1, which is a
contradiction to what we defined in the lemma. Therefore, gcd(aa−1 d − aa−1 c + c, ab) = 1,
meaning we have proved the lemma. ■
By Lemma 2.15, we know that this function creates numbers that are relatively prime
to ab, meaning that all elements of B are elements of A, or B ⊆ A. We now need to show
that A ⊆ B. This means that we must show that there exists some numbers c, d that satisfy
gcd(a, c) = 1 and gcd(c, d) = 1, such that:
x ≡ c (mod a)
x ≡ d (mod b),
where x ∈ A. This is simply just the converse of the Chinese Remainder theorem, which
is true. Therefore, we have that A ⊆ B. Therefore, we have that A = B, meaning that
#(A) = #(B). We also know that #(B) = ϕ(a)ϕ(b), and #(A) = ϕ(ab). Therefore,
ϕ(ab) = ϕ(a)ϕ(b). Therefore, we have shown that Euler’s Totient function is multiplicative.
Therefore, ϕ(n) for a number n that can be factorized as pb11 · p2b2 · pb33 · . . . · pbkk , is equal to
ϕ(pb11 )ϕ(pb22 )ϕ(pb33 ) . . . ϕ(pbkk ). We can expand each of those theorem using the formula we
derived previously, giving us: ϕ(n) = pb11 · pb22 · pb33 · . . . · pbkk (1 − p11 )(1 − p12 )(1 − p13 ) . . . (1 − p1k ).
However, pb11 · pb22 · pb33 · . . . · pbkk can be replaced with n (this is just its factorization), giving
us the final formula:
1 1 1 1
ϕ(n) = n(1 − )(1 − )(1 − ) . . . (1 − ).
p1 p2 p3 pk
Therefore, the theorem has been proven. ■
Theorem 2.16 (Euler’s Totient Theorem). Define ϕ(n) as we have previously. Suppose we
have two positive integers a, n such that gcd(a, n) = 1. Then the following congruence holds:
aϕ(n) ≡ 1 (mod n).
Proof. Let A denote the set of all numbers that are relatively prime to n as follows:
{k1 , k2 , k3 , k4 , k5 , . . . , kϕ(n) }. We now create a new set B that multiplies each element by a,
giving us: {ak1 , ak2 , ak3 , ak4 , ak5 , . . . , akϕ(n) }. We now show that ϕ(n) is always even for any
n > 2 (if n ≤ 2 then the theorem holds trivially). We see that in the formula, each term is
of the form pip−1 i
(where pi is one of the prime factors of n). We know that the numerator
is always even for any odd pi , and is only odd for pi = 2. However, ϕ(2) = 1, so it does
not contribute anything to the product. The terms in the denominator “cancel” out with
n, leaving us with an even product, meaning that ϕ(n) is even. This means that #(A) is
 PRIMALITY TESTING 7

even. We now use the fact that A is simply the multiplicative group of Z/nZ, meaning that
every element has a multiplicative inverse. Since we know that there are an even number of
elements, we know that we can pair up the numbers with their inverses, meaning that the
product of the integers (mod n) is just 1. This means that if we were to multiply all the
elements in B (mod n), we would get: aϕ(n) (mod n). We now show that all elements of B
(mod n) are congruent to the elements of A (mod n). This is true because of all values of B
are relatively prime and unique to n as well, so therefore, it must contain the same elements
as A. Or in other words, each element of B is congruent to one element of A. This means
that we have that aϕ(n) ≡ k1 · k2 · k3 · . . . kϕ(n) (mod n), or aϕ(n) ≡ 1 (mod n). Therefore, we
have proved the theorem. ■

2.2. Theorems from Sequences. We now will prove theorems related to Lucas sequences,
that will be needed later on.
Theorem 2.17. Let a, b, ∆, Uj , and Vj be defined as above. If p is a prime such that
gcd(p, 2b∆) = 1, then
Up−( ∆ ) ≡ 0 (mod p),
p
 
where ap is the Legendre Symbol.

Proof. We approach this proof by finding an explicit formula for Uj , in terms of a and b. We
do this by first assuming that Uj = cj , for some c ∈ R. We can plug this into the recurrence
relation that we defined for Uj previously, giving us cj = a · cj−1 − b · cj−2 . Dividing by cj−2 on
both sides of√the equation gives
√
us the quadratic x2 − ax + b = 0. The roots to this quadratic
a+ ∆ a− ∆
are c1 = 2 and c2 = 2 , where we use ∆ as the discriminant of the quadratic, as
defined previously. Therefore, our explicit formula satisfies the form Uj = λ1 cj1 + λ2 cj2 , where
λ1 , λ2 ∈ R. We now find the value of λ1 and λ2 by using the values of U0 and U1 (found
previously) to form a system of equations:
λ1 + λ2 = 0
√ √
a+ ∆ a− ∆
λ1 + λ2 = 1.
2 2
Solving this system of equations gives us the solutions λ1 = √1 and λ2 = − √1 . This means
√ √ ∆ ∆
(a+ ∆)j −(a− ∆)j
that the explicit formula for Uj is Uj = √
2j ∆
, which results from plugging the
values of λ1 and λ2 back into the equation Uj = λ1 c1 + λ2 cj2 .
j

We now do casework based on the value of ∆p .

 
∆
Case 1 p
= 1: This means that we are trying to prove that Up−1 ≡ 0 (mod p). We
√ √
(a+ ∆)p−1 +(a− ∆)p−1
can plug p−1 into the explicit formula for Uj which gives us Up−1 = √
2p−1 ∆
.
8 AADITYA BILAKANTI

Expanding this gives us:

p−2 √
p−4 √ 3
√ p−2
2( p−1
1
a ∆+ p−1
a ( ∆) + . . . + p−1
3 p−2
a( ∆) )
Up−1 = p−1 √
2 ∆
p−1 p−2

p−1 p−4

√ 2 p−1

√ p−3
1
a + 3
a ( ∆) + . . . + p−2
a( ∆)
Up−1 = p−2
2
     
p − 1 p−2 p − 1 p−4 p−1 p−3
2p−2 · Up−1 = a + a ∆ + ... + a(∆) 2 .
1 3 p−2
We now take this equation modulo p, which gives us Up−1 · 2−1 ≡ p−1

p−2
1
a +
p−1 p−4 p−1 p−3
−1



3
a ∆ + . . . + p−2 a(∆) 2 (mod p). We have 2 on the left hand side of
the congruence because we simplified 2p−2 with Theorem 2.13. We now prove the
following lemma which will allow us to simplify the right hand side:
Lemma 2.18. p−1


k
≡ (−1)k (mod p), for some prime number p and some integer k.
Proof. We begin by expanding and reducing p−1


k
modulo p, which gives us:
(p − 1)(p − 2) . . . (p − k) (−1)(−2) . . . (−k)
≡ (mod p)
k! k!
≡ (−1)k · k! · (k!)−1 (mod p)
≡ (−1)k (mod p).
Thus, the lemma has been proved. ■
Using Lemma 2.18, we can simplify the congruence to
p−3
Up−1 ≡ −2(ap−2 + ap−4 ∆ + . . . + a(∆) 2 ) ( mod p).
We now apply the finite geometric series formula to the right side, which gives
p−1
ap−2 (( ∆2 ) 2 −1)
us Up−1 ≡ −2( a
∆
−1
) (mod p). We now do casework on the gcd(a, p). If
a2
gcd(a, p) = p, this case is trivial, since the numerator becomes a multiple of p, meaning
that the whole expression becomes 0 (mod p). If the gcd(a, p) = 1, we approach this
case by first simplifying the numerator using Theorem 2.13:
p−1
−2ap−2 (∆ 2 · (ap−1 )−1 − 1)
Up−1 ≡ ∆
(mod p)
a2
−1
p−1
−2ap−2 (∆ 2 − 1)
Up−1 ≡ ∆
(mod p).
a2
−1
We now apply Euler’s Criterion
  (proven later on 
in the Solovay-Strassen Primality
p−1
a a
Test), which states: a 2 = p (mod p), where p is the Legendre Symbol, and
 PRIMALITY TESTING 9

p−1
 
p is a prime number. This means that ∆ 2 ≡ ∆p (mod p). However, since we
  p−1
defined that ∆p = 1 for this case, this means that ∆ 2 ≡ 1 (mod p). This means
that we can simplify the congruence to:
−2ap−2 (1 − 1)
Up−1 ≡ ∆
(mod p)
a2
−1
Up−1 ≡ 0 (mod p)
Therefore,
  this case has been proved.
Case 2 ∆p = −1: This means that we are trying to prove that Up+1 ≡ 0 (mod p).
This means that we√ can substitute
√
p + 1 into our explicit formula to obtain the
(a+ ∆)p+1 −(a− ∆)p+1
equation Up+1 = 2p+1 ∆
. Expanding this gives us:
p+1 p

p−1
a + p+1 a ∆ + . . . + p+1


p−1
1 3 p
a∆ 2
Up+1 = p
   2  
p p+1 p p + 1 p−1 p+1 p−1
Up+1 · 2 = a + a ∆ + ... + a∆ 2 .
1 3 p
p−1
We now take this expression modulo p, which gives us Up+1 ≡ 2−1 (ap +a∆ 2 ) (mod p).
We were able to remove the middle terms because they are all 0 (mod p), however,
the only exception to this rule is when p = 3. Therefore, we will have to separately
prove this case. We first assume that p ̸= 3. We can apply Theorem 2.13 and
Euler’s Criterion (similar to the previous case) to simplify the congruence to Up+1 ≡
2−1 (a − a) ≡ 0 (mod p).
However, we must now deal with the case where p = 3. This means that we are
trying to prove that U4 ≡ 0 (mod 3). Using the recurrence relations defined previously,
we find that U4 = a3 − 2ab. This means that we have a3 − 2ab (mod 3). We now
do casework based on the gcd(a, p). The case where gcd(a, p) = p is trivial, since
this means that the whole expression is 0 (mod p). If gcd(a, p) = 1, we now do more
casework on ∆ (mod 3).
Case 1 ∆ ≡ 0 (mod 3): This case is trivial since this contradicts the fact that
gcd(2b∆, 3) = 1 (stated in the theorem itself). Therefore, ∆ ̸≡ 0 (mod 3).
Case 2 ∆ ≡ 1 (mod 3): This case means that a2 − 4b ≡ 1 (mod 3). Since we
stated that gcd(a, p) = 1, this allows us to use Theorem 2.13, giving us:
1 − 4b ≡ 1 (mod 3)
b ≡ 0 (mod 3)
However, this again contradicts the statement gcd(2b∆, 3) = 1, so therefore,
∆ ̸≡ 1 (mod 3).
10 AADITYA BILAKANTI

Case 3 ∆ ≡ 2 (mod 3): This statement implies a2 − 4b ≡ 2(mod3). Simplifying,

we find that b ≡ 2 (mod 3). There are no contradictions from this, so this means
that ∆ ≡ 2 (mod 3) is valid. We now use b ≡ 2 (mod 3) in the congruence
a3 − 2ab (mod 3) (what we are trying to prove), which gives us:
a − 2ab ≡ a − 4a ≡ 0 (mod 3)
Thus, we have shown that p = 3 also satisfies the Theorem.
We have proved all the cases, and therefore, the Theorem. ■
2.3. Results from Group Theory. We first define Cyclic Groups and give some important
qualities about them:
Definition 2.19 (Cyclic Groups). A cyclic group is a group generated by a single element.
More specifically, it is a group of invertible elements, and contains an element g such that
repeatedly performing the group operation on g will obtain every other element of the group.
We list some properties of cyclic groups below:
(1) Every cyclic group is abelian (the group operation is commutative).
(2) All subgroups of a cyclic group are also cyclic.
• One can form a subgroup generated by all the integer powers of a specific element,
denoted by ⟨g⟩, where g is in the group.
(3) The multiplicative group modulo n is cyclic if and only if n = 1, 2, 4, pk , 2pk , where p
is an odd prime and k ∈ N.
(4) If d | n, where n is the order of the group, then there exists some subgroup that has
order d.
We now prove Lagrange’s Theorem, which will be very useful in our proofs.
Theorem 2.20 (Lagrange’s Theorem). Let G be a finite group. If H is a subgroup of G,
then |H| | |G|.
Proof. We divide the problem into three cases.
Case 1 |H| = 1: This means that H is just the trivial group. Of course, 1 | |G|.
Case 2 |H| = |G|: This means that H = G, and obviously, |G| | |G|.
Case 3 |H| = ̸ 1, |H| =
̸ |G|: Since H is a subgroup of G, it must contain the identity
element, which we shall call e. Let us then take an element in G but not in H called
g1 , and create a new set:
g1 H = {g1 ∗ h ∀h ∈ H}.
Note that the above set is known as a left coset. We now prove the following lemma:
Lemma 2.21. g1 H does not share any elements with H.
Proof. We prove this by contradiction. Suppose we have: g1 ·hi = hj , where hi , hj ∈ H.
Multiplying by the inverse of hi gives us: g1 · e = g1 = hj · (hj )−1 . However, note
that hj · (hj )−1 is an element of H, meaning that g1 is an element of H. However,
 PRIMALITY TESTING 11

this contradicts the fact that we defined that g1 was not an element of H. Therefore,
there cannot be any overlapping elements between g1 H and H. ■
Let us now take another element g2 that is not in H and g1 H. We can apply the
same argument in Lemma 2.21 to show that g2 H do not share any elements. However,
we still must show that g1 H and g2 H do not have any overlapping elements.
Lemma 2.22. g1 H and g2 H do not share any overlapping elements.
Proof. We again prove this by contradiction. Let hi , hj ∈ H. Then we have:
g2 · hj = g1 · hi
g2 · hj · (hj )−1 = g1 · hi · (hj )−1
g2 = g1 · hi · (hj )−1 .
However, since hj · (hi )−1 ∈ H, this means that g2 ∈ g1 H. However, this is a
contradiction to how we defined g2 . Hence, we have proved the lemma. ■
We now continue until there is no element left that is not in a coset or H. We
now split G into non-overlapping left cosets. However, we must now prove that all
these cosets are the same size. Suppose the coset gn · H has a duplicate element. Let
hi , hj ∈ H. We therefore have the following equation:
gn · hi = gn · hj
−1
gn · (gn ) · hi = gn · hj · (gn )−1
hi = hj .
However, the final equation is a contradiction. Therefore, each coset is the same size,
which is |H| = d. Since we have now managed to split G into non-overlapping cosets,
suppose we say we have split G into k non-overlapping cosets. We thus have that
d · k = |G|, meaning that d = |H| | |G|. Therefore, we have proved this case.
We have proved all three cases and therefore Lagrange’s Theorem. ■

3. Probabilistic Tests
3.1. Fermat Primality Test. We define the Fermat Primality Test using FLT:
Definition 3.1 (Fermat Primality Test). The Fermat Primality Test checks if a number n
satisfies an−1 ≡ 1 (mod n), for some integer a relatively prime to n. Of course if n is prime,
then this is just Fermat’s Little Theorem, which is true. If n does not satisfy the congruence,
then n is definitely composite. However, if n passes the test, the converse is not necessarily
true, and n is called a probable prime (since some composite numbers can pass the test). If
n is composite and passes the test, it is called a Fermat pseudoprime to base a.
To lower the chance of a false result being outputted, we can choose k different values of a
and therefore run k iterations of the test. If one of these tests fails for n, then n is composite.
12 AADITYA BILAKANTI

Using fast algorithms for modular exponentiation and multiplication, the time complexity
of the test is O(k log2 (n) log log n), where k is the number of iterations being performed, and
n is the number itself.
However, while the test seems to be relatively accurate and fast, one of the main problems
with the test is that there exist numbers such that they are a Fermat pseudoprime to all
bases a relatively prime to the number itself. These numbers are known as Carmichael
numbers. We show that 561 (the first Carmichael number) satisfies our current definition of
a Carmichael Number:
Proposition 3.2. 561 is a Carmichael number.
Proof. We must show that 561 satisfies a560 ≡ 1 (mod 561) for all integers a relatively prime
to 561. We can split the congruence into three equations modulo each of the prime factors of
561 by the Chinese Remainder Theorem. This gives us:
a560 (mod 3)
a560 (mod 11)
a560 (mod 17)
We can apply Theorem 2.13 to each congruence, giving us:
a2 ≡ 1 (mod 3)
a10 ≡ 1 (mod 11)
a16 ≡ 1 (mod 17).
Since 80 = LCM(2, 10, 16), we know that a80 is congruent to 1 modulo all factors of 561 (a
solution to the congruence). However, by CRT, the system of modular congruences:
x ≡ 1 (mod 3)
x ≡ 1 (mod 11)
x ≡ 1 (mod 17),
has only one solution modulo 561. However, since a80 and 1 are both solutions, this must
mean that a80 ≡ 1 (mod 561). Since 80 | 560, we have that a560 ≡ 1 (mod 561), for all a
relatively prime to n. ■
Robert D. Carmichael proved that every Carmichael number is odd, square-free, and has at
least 3 prime factors. Furthermore, in 1899, Korselt’s criterion was created, which stated that
a positive integer n is a Carmichael number if n is odd, n is squarefree, and p − 1 | n − 1 for
all prime divisors p of n. For a proof, see [Con16]. Additionally, Alford, Granville, Pomerance,
et al. proved in 1992 that there were infinitely many Carmichael numbers, a claim that had
gone long unproven [AGP94].
The infinitude and existence of the Carmichael numbers makes the Fermat Primality test
not very reliable (especially when applied to cryptography), and thus, the next two tests it.
 PRIMALITY TESTING 13

Specifically, they have bounds for the maximum number of bases that allows a composite
number to pass the test.
3.2. Solovay–Strassen Test. The Solovay–Strassen test relies on Euler’s Criterion, which
is as follows:
p−1
Theorem 3.3. x2 ≡ a (mod p) has a solution if and only if a 2 ≡ 1 (mod p), for a prime
p and an integer a not divisible by p.
Proof. Recall that from Theorem 2.13, if z is relatively prime to p, then z p−1 ≡ 1 (mod p).
p−1
Therefore, since the only square roots of 1 are 1 and -1, we have that z 2 ≡ ±1 (mod p).
p−1
This means that we have to show that if a 2 ≡ 1 (mod p), then a is a quadratic residue,
p−1
and if a 2 ≡ −1 (mod p), then a is a quadratic non-residue.
p−1
Case 1 a 2 ≡ 1 (mod p): Since p is prime, we know that there exists some integer g
such that its order modulo p is p − 1 (the primitive root modulo p). Therefore, we have
g p−1 ≡ 1 (mod p). Since g is the primitive root modulo p, there exists some number
p−1
m such that g m ≡ a (mod p). Replacing this with a in a 2 ≡ 1 (mod p) gives us
p−1 p−1 p−1
(g 2 )m ≡ 1 (mod p). We know that g 2 ≡ −1 (mod p), as if g 2 ≡ 1 (mod p), this
would contradict the fact that the order of g modulo p is p − 1. Therefore, we know
that m is even (since -1 must be raised to an even power to become 1). Therefore,
we know that since g m ≡ a (mod p), and that m is even, a can be represented as
m p−1
(g 2 )2 ≡ a (mod p). Therefore, if a 2 ≡ 1 (mod p) then a is a quadratic residue
modulo p.
p−1 p−1
Case 2 a 2 ≡ −1 (mod p): Notice that the equation x 2 ≡ 1 (mod p) has at most
p−1
2
roots. However, we have just showed that all quadratic residues satisfy this
equation, and there are exactly p−1 2
modulo p. Therefore, the only other option for
p−1
quadratic non-residues is for them to satisfy a 2 ≡ −1 (mod p).
Therefore, we have proved Euler’s Criterion. ■
p−1
   
Euler’s criterion can be concisely summarized as a 2 ≡ ap (mod p), where ap is
Legendre’s Symbol. We can now define the Solovay–Strassen test:
Definition 3.4 (Solovay–Strassen Primality Test). The Solovay–Strassen test
considers the
n−1
congruence a 2 ≡ n (mod n), where n is any odd, positive integer and na is the Jacobi
a


symbol. Note that n must be odd because we defined the Jacobi Symbol for only odd integers.
If n is prime, as we showed previously, this congruence holds for all a. If n is composite and
fails the test, then a is called an Euler witness for the “compositeness” of n. However, if n
passes the test and is composite, then a is called an Euler liar and n is known as an Euler
pseudoprime (or Euler–Jacobi pseudoprime).
Just as we ran k iterations of the Fermat Primality Test to improve its accuracy, we
can use the same technique to improve the Solovay–Strassen. However, unlike the Fermat
14 AADITYA BILAKANTI

Primality Test, there is a probability “bound” on whether the test classifies a composite
number incorrectly (which we prove later).
It is also important to note that we must use an algorithm to calculate the Jacobi Symbol,
since our definition of it relies on knowing the prime factors of n. However, using the
properties of the Jacobi Symbol defined previously, we can devise an efficient way to calculate
the Jacobi symbol of any two integers. The algorithm is as follows:
(1) If the top argument is greater than the bottom argument, then reduce the top
argument modulo the bottom argument, by Lemma 2.3.
(2) We can “get rid” of any factors of 2 using Lemma 2.4 and 2.8.
(3) If the top argument is 1, then the Jacobi Symbol evaluates to 1 (1 is always a quadratic
residue modulo any number). If the numerator and denominator are not relatively
prime (determined by Euclid’s Algorithm), then by Lemma 2.5, the Jacobi Symbol
becomes 0.
(4) If none of the conditions in step 3 are satisfied, then the top and bottom arguments are
now odd positive relatively prime integers. This means we can “flip” the arguments
by Lemma 2.6. We can then return to step 1 after we do this and repeat this process.
This algorithm allows us to calculate the Jacobi symbol without knowing the prime
factorization of n, and is also quite efficient.
We now will prove that at most 12 of the bases for a composite integer n are Euler liars.
The proof comes from [SS77, SS78].
Theorem 3.5 (Solovay–Strassen). Let n be an
odd, positive, composite integer. The set
n−1
S = {a + (n)|a ∈ Z∗n & gcd(a, n) = 1, a 2 ≡ na (mod n)} is not equal to Z∗n .
Proof. We first note that S is a subgroup of Z∗n , since S only contains some of the elements
relatively prime to n. We now see why we only need to prove that S = ̸ Z∗n . This is because
by Lagrange’s Theorem, |S| | |Z∗n |. At maximum, |S| = |Z∗n |/2, which is less than or equal to
n−1
2
(since S ̸= Z∗n contains only all integers relatively prime to n). Therefore, we have the
∗
inequality |S| ≤ |Z2n | ≤ n−1
2
, which is what we are trying to prove.
We try to find a contradiction, by stating that S = Z∗n . This means that
n−1
a
(3.1) a 2 ≡ (mod n),
n
for all a relatively prime to n. We consider cases of n to show this:
Case 1 n = px , for some prime p and integer x: This means we have:
 
px −1 a
a 2 ≡ (mod px ).
px
x
Squaring both sides gives us: ap −1 ≡ 1 (mod px ). Since Z∗px is cyclic with order
ϕ(px ) = px−1 (p − 1) by Theorem 2.14, we know that px−1 (p − 1) | px − 1. We now
 PRIMALITY TESTING 15

see that x ≤ 1. This is because px−1 (p − 1) | px − 1 implies that there is some integer
d such that:
px − 1
d = x−1 .
p (p − 1)
We can simply the fraction giving us:
px − 1
d = x−1
p (p − 1)
px−1 + px−2 + . . . + 1
=
px−1
1 1 1
= 1 + + 2 + . . . + x−1 .
p p p
In order for this to be an integer, x ≤ 1, since otherwise, the sum evaluates to a
fraction. However, this is a contradiction, since this implies that n is a prime number,
however, we defined that n was composite.
Case 2 n = pq, for square-free integers p and q: By Equation 1, we know that it
implies that:
n−1
(3.2) a 2 ≡ ±1 (mod n).
We will now show that the conditions of this case mean:
n−1
(3.3) a 2 ≡ 1 (mod n),
n−1
for all a relatively prime to n. Assume that a 2 ≡ −1 (mod n) (the only other
possibility). Since p and q are relatively prime, this means we can apply CRT to give
us the system of equations:
b ≡ 1 (mod r)
b ≡ a (mod s)
n−1
Raising each congruence to the 2
, we have that:
n−1
b 2 ≡ 1 (mod r)
n−1
b 2 ≡ −1 (mod s)
However, this is a contradiction to Equation 2, as both of the equations would either
have to be congruent to 1 or −1 to not have a contradiction (by CRT). Therefore, we
know that
Equation 3 is true. However, Equation 3 (by Euler’s Criterion) implies
a
that n = 1 for all a relatively prime to n, which is false because it is impossible for
all relatively prime integers a to n be quadratic residues to it.
Case 3 n = px · q, where x > 1, p is an odd prime and gcd(p, q) = 1: This case as-
sumes that n is not square-free. From earlier in the proof, we know that an−1 ≡
1 (mod n), for all a relatively prime to n. By CRT, we know that an−1 ≡ 1 (mod px ),
16 AADITYA BILAKANTI

meaning that px−1 (p − 1) | n − 1 (since Z∗px ) is cyclic and the order is ϕ(px )). Since
x > 1, this means that p | n − 1 as well as n. However, by Euclid’s Algorithm, we
know that gcd(n − 1, n) = 1, so therefore, this is a contradiction. This means that n
is square-free. However, we already have a case covering if n is square-free, which has
a contradiction. Thus, we have proved this case.
These three cases encapsulate all the possible forms of a composite number n, and since
we have derived a contradiction for each, we have shown that S ̸= Z∗n , our original goal.
Therefore, we have proved the theorem. ■

By Theorem 3.5, we know that if we were to run k iterations of the Solovay–Strassen test
as outlined in Definition 3.4, then the probability of erroneously classifying a composite
integer as a prime is 2−k . This is of course much better than the Fermat Primality test. We
now look at a way to make it to determinstic, if n is less than a certain bound.
By using a pre-selected bases, we can treat the Solovay–Strassen test as a determinstic test
up till when the test identifies a number n wrong.
Selected bases Determistic Up To Some Value of n (non-inclusive)
{2} 561
{2, 3} 1729
{2, 3, 5, 7} 399001
{2, 3, 5, 7, 11} 399001
{2, 3, 5, 11} 15841
{2, 3, 5, 7, 11, 13} 15841
{2, 3, 5, 7, 11, 13, 17} 1857421
{2, 3, 5, 7, 11, 13, 17, 19} 6189121
{2, 3, 5, 7, 11, 13, 17, 23} 14469841
{3, 5, 11, 13} 416641
{2, 37} 1729
{2,25} 561
{2, 24} 1729
{24, 88} 15841
{24, 88, 71} 15841
{24, 71} 1729
{26, 71} 217
{2, 26} 561
{2, 200} 561
{2, 300} 1729
{2, 1000} 1729
{2, 1001} 162401
{2, 88} 2047
 PRIMALITY TESTING 17

The values in the table demonstrate that while this is a useful feature for certain n, these
bounds are not comparable to size of primes used in cryptography.
3.3. Miller–Rabin Test.
Definition 3.6 (Miller Rabin Primality Test). The Miller–Rabin test determines if a number
is a strong probable prime, which means that it satisfies the following conditions, given that
n is an odd positive integer > 1, and we write n − 1 as 2s · d, where d is odd:
ad ≡ 1 (mod n)
rd
a2 ≡ −1 (mod n), for 0 ≤ r < s,
where a is defined to be a random number relatively prime to n. As stated previously, if n
passes the test, it is considered a strong probable prime to base a. By contraposition, if n is
not a strong probable prime, then n is definitely composite. In this case, the base a is called
a “witness” (for the “compositeness” of n). However, some composite numbers n do pass the
test, in which case, n is called a strong pseudoprime and a is known as a strong liar.
We now prove that if n is prime, then the test returns that n as a strong probable prime.
Theorem 3.7. If p is a prime number, then it passes the Miller–Rabin test.
Proof. Factor p − 1 as 2s · d, where d is odd. We now use the expression xp−1 − 1 (where x
s−1
is relatively prime to p). We can factor this with difference of two squares as so: (x2 ·d −
s−1 s−1
1)(x2 ·d + 1).We can continue to factor (x2 ·d − 1) using difference of squares, provided
that the exponent of x is not odd. Therefore, we can factor xp−1 − 1 as (xd − 1)(xd + 1)(x2d +
s−2 s−1
1)(x4d + 1) . . . (x2 ·d + 1)(x2 ·d + 1). However, note that by Fermat’s Little Theorem,
we know that xp−1 ≡ 1 (mod p). We can replace xp−1 with a factorization, giving us:
s−2 s−1
(xd − 1)(xd + 1)(x2d + 1)(x4d + 1) . . . (x2 ·d + 1)(x2 ·d + 1) ≡ 0 (mod p). Since p is prime,
we know that one of these factors must be 0 (mod p). Therefore, either xd ≡ 1 (mod p), or
r
x2 ·d ≡ −1 (mod p), where 0 ≤ r < s. Therefore, a prime number would pass the test. ■
As with the Solovay–Strassen test, no composite number can be a strong pseudoprime
to all bases (once again contrasting the Fermat Primality test). In fact, at most 14 of the
bases relatively prime to n can be strong liars (which will be proven later). While we could
try all possible passes a relatively prime to n (and less than n), this would only give a slow,
deterministic test. We instead pick the bases randomly, yielding a fast probabilistic test.
Instead, we can pick k different values of a (similar to previous test), meaning the probability
of a composite number passing the test becomes 4−k , which becomes extremely small very
quickly. This makes the Miller–Rabin test a very good probabilistic test, as it is able to
produce high accuracy extremely quickly.
We now take a more in-depth look at the time complexity/speed of the algorithm itself.
The test has a time complexity of O(k(log(n)))3 , where n is the number being tested for
primality, and k is the amount of iterations run, by using efficient methods for modular
18 AADITYA BILAKANTI

exponentiation. However, we can make the algorithm even more efficient. Using the Harvey-
Hoeven algorithm for Fast Fourier Transform(FFT) based multiplication, the Miller Rabin
test can be sped up further to Õ(log2 (n)), which comes from the fact that the time complexity
of the Harvey-Hoeven is O(n log(n)).
We now look at the accuracy of the Miller–Rabin test, which will prove our claims made
previously. The following theorem is inspired by [Sch08].
Theorem 3.8 (Rabin–Monier theorem). Let n be an odd composite integer greater than 9.
We write n − 1 = 2k · m, for some odd integer m. Let B = {x ∈ (Z/nZ)∗ | xm ≡ 1 (mod n)
i
or xm·2 ≡ −1 (mod n) for some 0 ≤ i < k}. Then we have that #(B)ϕ(n)
≤ 14 , where ϕ(n) is
Euler’s Totient function.
Proof. We let 2l be the largest power of 2 that divides p − 1 for all prime divisors p of n.
l−1
We now create the set B ′ = {x ∈ (Z/nZ)∗ | xm·2 ≡±1 (mod n) }. We prove that B ⊂ B ′ . If
y ∈ B such that y m ≡ 1 (mod n), then y must also be an element of B ′ . This is because
l−1
y m·2 ≡ 1 (mod n) as well, which can be seen by “taking out” an m from the exponent, and
using the fact that y m ≡ 1 (mod n).
i i
We now deal with the case where y 2 ·m ≡ −1 (mod n). We first observe that y 2 ·m ≡
−1 (mod p), for any prime p dividing n because of the following:
i
y 2 ·m = nk − 1, for some positive integer k
i
y 2 ·m + 1 = nk
i
y 2 ·m + 1 = cpk, for some positive integer c
i
y 2 ·m + 1 ≡ 0 (mod p)
i
y 2 ·m ≡ −1 (mod p).
i
Therefore, we have y 2 ·m ≡ −1 (mod p), for all p | n. Squaring this equation gives us
2i+1 ·m
y ≡ 1 (mod p). This implies that the order t of y modulo p divides 2i+1 · m. By
definition, since y m ≡ −1 (mod n), we know that t and 2i+1 share factors. However, we now
show that 2i+1 is the exact power of 2 dividing t. We prove this in the following lemma:
Lemma 3.9. 2i+1 is the exact power of 2 dividing t.
Proof. Assume that t = 2c · g (we know that t is even), where g is odd and c ∈ Z < i + 1. We
i
try to derive a contradiction to the fact that y 2 ·m ≡ −1 (mod n) for some 0 ≤ i < k. If the
c−1
order of y modulo p was t = 2c · g, then we know that y 2 ·g ≡ −1 (mod p). We also know
that if 2c · g | 2i+1 · m, then 2c · g · v = 2i+1 · m, for some positive integer v. This tells us that
v must be even, since c < i + 1, and g and m are both odd (and therefore do not contribute
any factors of 2). Dividing by two on both sides gives us: 2c−1 · g · v = 2i · m. Therefore,
c−1 c−1
raising y 2 ·g to the v power would give us 2i · m. Since we have y 2 ·g ≡ −1 (mod n), we
i i
have that y 2 ·m ≡ (−1)v (mod n). However, since v is even, we have that y 2 ·m ≡ 1 (mod n).
 PRIMALITY TESTING 19
i
However, this contradicts the fact that y 2 ·m ≡ −1 (mod n) for some 0 ≤ i < k, which is
what we assumed in this case. Therefore, we have derived a contradiction and showed that
the exact power of 2 dividing t is 2i+1 (since this contradiction means c = i + 1). ■

The above lemma tells us that 2i+1 divides p − 1 for p dividing n. We can see this using
Fermat’s Little Theorem. We know that y p−1 ≡ 1 (mod p). The order of y modulo p is t, so
we have t | p − 1. However, since 2i+1 | t, we have that 2i+1 | p − 1. However, we also know
that l is the largest power of 2 dividing p − 1. Therefore, l ≥ i + 1. Therefore, we can write
l−1 i l−i−1 l−i−1
y 2 ·m (mod p) as (y 2 ·m )2 (mod p), which is (−1)2 (mod p). This is ±1, depending
′
on whether l = i + 1 or l > i + 1. It follows that B ⊂ B .
By the Chinese Remainder Theorem, the number of elements x ∈ (Z/nZ)∗ for which
l l−1
x2 ·m ≡ 1 (mod n) is equivalent to the equation X 2 ·m ≡ (mod p)pb , where p | n, p is a
prime, pb is the exact power of p dividing n. We now prove the following lemma:

Lemma 3.10. All groups stated are finite and abelian. For any n ∈ Z and a cyclic group G,
we let sn (G) := {g ∈ G : g n = 1}. Then the above definitions imply |sn (G)| = gcd(n, |G|).

Proof. We let d = gcd(n, |G|) and S = sn (G). We know that S ≤ G, so therefore, since G is
cyclic, S must be cyclic as well. This means that S = ⟨a⟩ where a ∈ G, and therefore, the
multiplicative order of a is the order of group S. Since a ∈ S, an = 1, and hence, |a| | n,
where |a| denotes the multiplicative order of a. We can also use the fact that since a ∈ G,
a|G| = 1, so therefore, |a| | |G|. From these two divisibility requirements for |a|, we can see
that |a| | gcd(|G|, n) = d. Since G is cyclic and d divides |G|, there exists some subgroup S ′
′
of G of order d. If g ∈ S ′ , then g |S | = g d = 1, which implies that g n = 1, which results from
the fact that d | n. Therefore, this shows that S ′ ≤ S, and by Lagrange’s Theorem, |S ′ | | |S|.
However, these can be replaced by d and |a|, giving us d | |a|. However, we also know that
|a| | d. Therefore, |a| = |S| = d. We have thus proved the lemma. ■
l−1
We now use Lemma 3.10 to find the number of solutions to X 2 ·m ≡ (mod ppb ).
The ossible solutions for X are in (Z/ppb Z)∗ , which is cyclic (since it is modulo a prime
power). Therefore, by Lemma 3.10, we have that the number of solutions to the congruence is
gcd(2l−1 ·m, |(Z/ppb Z)∗ |), which let d be equal to. Since this is the multiplicative group modulo
ppb , the order of the group is ϕ(ppb ) = ppb −1 (p − 1). Therefore, d = gcd(2l−1 · m, ppb −1 (p − 1)),
l−1
which is the number of solutions to X 2 ·m ≡ 1 (mod ppb ). Since m ∤ p, we see that the
ppb −1 term in the “gcd expression” does not contribute to its value. Therefore, we have that
l−1
d = gcd(p − 1, m) · 2l−1 . Therefore, the total number of solutions to X 2 ·m ≡ 1 (mod n) is
the product of the number of solutions for each of the modular equations modulo a prime
power. This gives us the following equation:
l−1
Y
#{x ∈ (Z/nZ)∗ | xm2 ≡ 1 (mod n)} = gcd(p − 1, m)2l−1 .
p|n
20 AADITYA BILAKANTI

l
Using the same method as before, we find that the number of solutions to X 2 m ≡ 1 (mod ppb )
l−1
is gcd(p − 1, m)2l , which is twice the number of solutions to X 2 m ≡ 1 (mod ppb ). Therefore,
l−1
the number of solutions to X 2 m ≡ −1 (mod ppb ) is also gcd(p − 1, m)2l−1 . Therefore, we
can express the cardinality of B ′ as:

Y
#(B ′ ) = 2 gcd(p − 1, m)2l−1 ,
p|n

and therefore,

#(B ′ ) Y gcd(p − 1, m)2l−1

=2 .
ϕ(n) ppb −1 (p − 1)
p|n

The denominator of the product results from the fact thatwe are “breaking down” n into
its prime powers. We now try to derive a contradiction by assuming that #(B)
ϕ(n)
> 14 . Since
B ⊂ B ′ , we have:

Y gcd(p − 1, m)2l−1 1
(3.4) > .
ppb −1 (p − 1) 4
p|n

l−1
We note that gcd(p − 1, m)2l−1 divides p−1
2
, so therefore, we have that gcd(p−1,m)2
ppb −1
≤ 2pp1b −1 .
Since ppb −1 ≥ 1 and we want to minimize the denominator, we have 2pp1b −1 ≤ 12 . If we let t be
the number of prime factors of n, then the maximum value is 2 · 2−t = 21−t . Since 21−t > 14 ,
t ≤ 2. We now do casework on the value of t:

Case 1 t = 2: This means that n has only two prime divisors. We now show that n
must be squarefree. If one the divisors has the property such that p2 | n, this would
1
mean that the maximum value would be 2·3 (since p must be an odd prime), which
1 1−2
is 6 . This is because we have 2 /3 = 1/6, which is a contradiction, since this is
less than 14 . Rather than 2, if we said that pn | n, this would only mean that the
maximum value of left hand side would become smaller (and be even less than 14 ).
Therefore pb = 1, and n = pq for distinct primes p and q. We can now transform the
 PRIMALITY TESTING 21

inequality using the fact that pb = 1:

gcd(p − 1, m)2l−1 gcd(q − 1, m)2l−1 1
2· · >
p−1 q−1 4
l l−1
gcd(p − 1, m)2 gcd(q − 1, m)2 1
· >
p−1 q−1 4
p−1 q−1
· <4
gcd(p − 1, m)2l gcd(q − 1, m)2l−1
p−1 q−1 1 1
· · < 4 ·
gcd(p − 1, m)2l gcd(q − 1, m)2l−1 2 2
p−1 q−1
· <2
gcd(p − 1, m)2 gcd(q − 1, m)2l
l

We know that each of the left hand side are each integers, so therefore, each of the
fractions are 1 (in order to be less than 2). This means that p − 1 = gcd(p − 1, m)2l
and q − 1 = gcd(q − 1, m)2l . However, since we know that m is odd and p − 1 is even,
the gcd of those two numbers are odd. Therefore, the exact power of 2 dividing q − 1
and p − 1 is 2l . Furthermore, this implies that the odd “parts” of p − 1 and q − 1
must divide m. We then use the fact that n = 2k · m + 1, and now replace n with pq,
giving us pq = 2k · m + 1. We then take this modulo the odd part of p − 1, using the
fact that p − 1 is divisible by m. Let o(x) denote the largest odd part of x:
pq = 2k · m + 1 (mod o(p − 1))
q = 1 (mod o(p − 1))
q − 1 = 0 (mod o(p − 1)).
However, since o(p − 1) is odd(by definition) we can disregard the even part of q − 1,
meaning that the odd part of p − 1 divides the odd part of q − 1. By taking the
equation modulo q − 1, we find that o(q − 1) | o(p − 1). Therefore, the odd parts
of p − 1 and q − 1 are equal. However, since we also established that 2l is the exact
power of 2 dividing both p − 1 and q − 1, this means that both the even and odd
parts of p − 1 and q − 1 are equal. However, this means that p − 1 = q − 1, or p = q.
However, this contradicts the fact that p and q are distinct primes, so therefore t = 2
gives us a contradiction.
Case 2 t = 1: This means that n = pa , where a is an integer a ≥ 2. The first inequality
now states that pa−1 < 4, meaning that the only solution is p = 3 and a = 2. This
means that n = 9, contradicting the fact that we defined that n > 9.
Therefore, following from the result that B ′ ⊂ B, we have #(B)
ϕ(n)
≤ 14 . We have thus proved
the theorem (as we have found contradictions in both cases). ■
This is of course an improvement over the Solovay–Strassen test, and we will see that
this makes the test much more effective when choosing bases to make a deterministic test
22 AADITYA BILAKANTI

(as we did with Solovay–Strassen test). The following table compiles the results from
[PSW80, Jae93, Fei13].

Selected bases Deterministic Up To Some Value of n (non-inclusive)

{2} 2,047
{2, 3} 1,373,653.
{31, 73} 9,080,191
{2, 3, 5} 25,326,001
{2, 3, 5, 7} 3,215,031,751
{2, 7, 61} 4,759,123,141
{2, 13, 23, 1662803} 1,122,004,669,633
{2, 3, 5, 7, 11} 2,152,302,898,747
{2, 3, 5, 7, 11, 13} 3,474,749,660,383
{2, 3, 5, 7, 11, 13, 17} 341,550,071,728,321
{2, 3, 5, 7, 11, 13, 17, 19, 23} 3,825,123,056,546,413,051
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 18,446,744,073,709,551,616 = 264
As we can see, making the Miller–Rabin a deterministic test up to a certain value of n is
much more fruitful than the Solovay–Strassen test (which definitely makes sense considering
the probability bound for each iteration of each of the tests).

3.4. Lucas Probable Prime Tests.

Definition 3.11 (Lucas Probable Prime Test). Theorem 2.17 forms the basis of the Lucas
Probable Prime Tests. For a given pair (a, b) such that a2 − 4b is not a perfect square, and a
number n such that gcd(n, 2b · ∆) = 1, then if n satisfies Theorem 2.17, n is known as a Lucas
Probable Prime. If n is composite and satisfies the congruence, then n is a Lucas pseudoprime.
However, if n does not satisfy the theorem, then by contraposition, n is composite.
When we perform the Lucas Probable Prime test, we need to pick a value for a and b,
since this determines the sequence Uj . However, it is important to keep in mind that we
defined ∆ to not be a perfect square. This is because if this was the case, then ∆ = c2 for
some integer c, implying that Dn = 1. This would mean that a = c + 2 and b = c + 1.

Solving for the roots of the equation x2 − ax + b and using this to create an explicit formula
n −1 n −1 n−1
for Uj gives us: (c+1)
c+1−1
= bb−1 . For j = n − 1, we have that Un−1 = b b−1−1 , meaning that
the Lucas
Probable Prime test becomes an ordinary primality test. Therefore, it is better to
have ∆ n
= −1. A method of picking ∆ created by John Selfridge was to find the first term
∆


in the sequence 5, −7, 9, −11, 13, −15, . . . that satisfies n = −1. We then
let a = 1 and
b = 1−∆
4
. However, since this is a primality test, if we find a ∆ such that ∆ n
= 0, then we
can immediately output that n is composite (since ∆ shares factors with n besides 1 and n,
meaning n is composite). Additionally, if n is a square, this means that the Jacobi Symbol
will always greater than −1. We quickly show why this is true, by first recalling that the
 PRIMALITY TESTING 23

formula for the Jacobi Symbol is (where we define n to be factorized as pa11 · pa22 · . . . · pakk ,
where p1 , p2 , . . . , pk are prime numbers and a1 , a2 , . . . , ak are positive integers):
   a1  a2  ak
b b b b
(3.5) = · · ... · .
n p1 p2 pk
Since n is a perfect square, a1 , a2 , . . . , ak must all be even, meaning that when we calculate
the Jacobi Symbol, each of the terms will be nonnegative. Therefore, if we do not find a
suitable ∆ after a few tries using Selfridge’s method, we should check if n is a square.
Once we find a suitable value of D, we can then choose a and b as outlined above and
conduct the Lucas Probable Prime Test as stated in Definition 3.11. However, we can
strengthen the test by taking some inspiration from the Miller–Rabin test to create the Strong
Lucas Probable Prime Test.
Definition 3.12 (Strong Lucas Probable Prime Test). Let n is an odd composite integer
∆


such that the gcd(n, ∆) = 1. Factor n − n as 2s · d where d is odd. The Strong Lucas
Probable Prime Test is as follows: If n satisfies at least one of the followign conditions:
Ud ≡ 0 (mod n)
Vd·2r ≡ 0 (mod n), for some 0 ≤ r < s,
then n is declared a Strong Lucas Probable Prime. If n is a composite number and passes
the test, it is considered a Strong Lucas Probable Prime.
We now prove the following theorem:
Theorem 3.13. If n is a prime p, then at least one of the conditions are satisfied of the
Strong Lucas Probable Prime Test, provided that gcd(p, 2b∆) = 1.
Proof. Since p ∤ ∆, x2 − ax + b has distinct roots y and z in Fp . We now divide the proof
into two cases:   
Case 1 ∆p = 1: If ∆p = 1, this means that ∆ is a quadratic residue modulo p. In
other words, ∆ is a square in Fp , meaning that f (x) factors modulo p. This means
that y, z are roots in Fp , and we can therefore apply Fermat’s Last Theorem to get:
p−1 −z p−1
y p−1 ≡ z p−1 ≡ 1 (mod p). This gives us that: Up−1 ≡ y y−z ≡ 0 (mod p). We
p−1 p−1 p−1 p−1
know that y −z ≡ 0 (mod p), so we can factor y −z can be factored as
follows by difference of two squares:
p−1 p−1 p−1 p−1
(y 2 −z 2 )(y 2 +z 2 ) ≡ 0 (mod p)
p−1 p−1 p−1 p−1 p−1 p−1
(y 4 −z 4 )(y 4 +z 4 )(y 2 +z 2 ) ≡ 0 (mod p)
...
s−1 d s−1 d
(y d − z d )(y d + z d )(y 2d + z 2d ) . . . (y 2 + z2 ) ≡ 0 (mod p)
24 AADITYA BILAKANTI

Note that one of these factors must be 0 (mod p). Therefore, y d − z d ≡ 0 (mod p).
d −z d
We know that Ud ≡ yy−z (mod p), and since y d − z d 0 (mod p), we have that
p−1 p−1
Ud ≡ 0 (mod p). Otherwise, y 2r d + z 2r d ≡ 0 (mod p), for some 0 ≤ r < s. However,
notice that this is the definition of V2r d , so therefore, we have that V2r d ≡ 0 (mod p).
We have therefore
 proved the first case.
∆
Case 2 p = −1: This means that the discriminant is not a square in Fp , and there-
fore, the roots are in the field Fp2 , as this means that f (x) is irreducible modulo p.
Note that since y · z = b (by Vieta’s Formulas) and b, z ̸= 0, y is nonzero as well. We
have that:
s s
y2 d − z2 d
U2s d ≡ ≡ 0 (mod p)
y−z
s s
y 2 d − z 2 d ≡ 0 (mod p)
sd sd
y2 ≡ z2
(mod p)
y 2s d
( ) ≡ 1 (mod p)
z

If we take the square root of the final equation, since the only square roots of 1
r
are 1 and -1, we either have (y/z)2 d ≡ −1 (mod p), or (y/z)d ≡ 1 (mod p). By
rearranging the terms of the congruences, we find that the first condition implies
that V2r d ≡ 0 (mod p), for some 0 ≤ r < s, and the second condition corresponding
to Ud ≡ 0 (mod p) (using similar logic as in the previous case). We have therefore
proved this case as well.
We have proved both cases and therefore the theorem. ■
4
Arnault (1997) showed that a composite number n is a pseudoprime to at most 15 of
k
the
 possible
 bases, unless
 nis the product of two twin primes 2 q 1 ± 1 (where q 1 is odd),
∆ ∆
2k q1 −1
= −1 and 2k q1 +1 = 1. For a deeper discussion of the topic and the full proof,
see [Arn97].
We now define the Extra Strong Lucas Probable Prime Test:
Definition 3.14 (Extra Strong Lucas Probable Prime Test). Let Un = Un (a, 1) and
Vn =
2 s ∆
Vn (a, 1). Therefore, ∆ = a − 4. Assume that gcd(n, 2∆) = 1, and let n = 2 d + n , where
d is odd. Then, either one of the following congruences hold:
Ud ≡ 0 (mod n) and Vd ≡ ±2 (mod n)
V2r d ≡ 0 (mod n) for some 0 ≤ r < s − 1.
If n passes the test, then n is known as an Extra Strong Lucas Probable Prime. However, if
n is composite and passes the test, then n is known as an Extra Strong Lucas Pseudoprime.
We now prove the following theorem:
 PRIMALITY TESTING 25

Theorem 3.15. Let p be a prime number. Then it must pass the Extra Strong Lucas Probable
Prime Test.
Proof. We can use the Theorem 3.13 to our advantage. Most of the test is the same, except
for some conditions; it suffices to show that V2s−1 d ̸≡ 0 (mod p), and that if Ud ≡ 0 (mod n),
then Vd ≡ ±2 (mod n).
We first prove the latter condition, using the following lemma:
Lemma 3.16. Vn2 − ∆Un2 = 4bn .
Proof. Let c and d be roots of the polynomial x2 − ax + b (the recurrence polynomial for
n −dn
the sequences Uj (a, b) and Vj (a, b)). We have Vn = cn + dn and Un = c c−d , by our previous
definitions of the sequences. This gives us (keeping in mind that ∆ = (c − d)2 ):
(cn + dn )2 − (cn − dn )2 = c2n + 2(cd)n + d2n − (c2n − 2(cd)n + d2n )
= 4(cd)n
Note that since cd = b by Vieta’s Formulas, we have that Vn2 −∆Un2 = (cn +dn )2 −(cn −dn )2 =
4bn , and we have proved the lemma. ■
By Lemma 3.16 and the fact that b = 1, we have that Vd2 − ∆Ud2 = 4. Taking this
equation modulo p, we have Vd2 − ∆Ud2 ≡ 4 (mod p). Since we are trying to prove that if
Ud ≡ 0 (mod p), then Vd ≡ ±2 (mod p), we assume that Ud ≡ 0 (mod p). This means that
we have that Vd2 ≡ 4 (mod p), or Vd ≡ ±2 (mod p). Therefore, we have proved the latter
condition.
We now prove that V2s−1 d ̸≡ 0 (mod p). We first assume that g is a root of the polynomial
x − ax + 1. This would imply that g −1 is the other root, since by Vieta’s Formulas,
2
s−1 s−1
the product of the two roots is 1. This means that V2s−1 d = g 2 d + g −2 d . We now
try to derive a contradiction. Suppose that V2s−1 d ≡ 0 (mod p). This would mean that:
s−1 s−1 s
g 2 d + g −2 d ≡ 0 (mod p), which implies that g 2 d ≡ −1 (mod p). We now divide this into
two different cases:
Case 1 ∆ = 1: This would mean that 2s · d = p − 1. However, since ∆



n n
= 1, we
know that g ∈ Fp (since g is a root of f (x), and f (x) is reducible modulo p). However,
this means that FLT holds true, meaning g p−1 ≡ 1 (mod p). However, we know that
s
V2s−1 d ≡ 0 (mod p) implies that g 2 d ≡ −1 (mod p), or g p−1 ≡ −1 (mod p). Therefore,
we have proved a contradiction.
Case 2 n = −1: This implies that g p ≡ g − 1 (mod p), which means that g p+1 ≡ 1 ̸≡
∆


−1 (mod p), and we have again derived a contradiction.
We have derived contradictions in both of the cases, and therefore have proved the theorem. ■

3.5. Baillie–PSW Primality Test. The Baillie–PSW Primality Test is a combination of

two previous tests that have been mentioned in this paper. It combines a base 2 Miller–Rabin
test and a standard or strong Lucas Probable Prime test.
26 AADITYA BILAKANTI

Definition 3.17 (Baillie–PSW Primality Test). The Baillie–PSW Primality Test goes as
follows:
(1) First perform a Miller–Rabin test with base 2. If the test fails, then n is composite.
Otherwise, proceed to the next step.
(2) Perform a Strong Probable Lucas Test, using Definition 3.12. If n succeeds, then n
is most likely prime.
Carl Pomerance stated that in an exhaustive search to 25 · 109 , no composite number was
found to pass the test [Pom84]. In fact, even if the Miller Rabin test base 2 was weakened
to a Fermat Probable Prime test base 2, every composite n ≤ 25 · 109 would fail at least
one of the conditions. In fact, no examples of any composite number passing the test are
known. The Elliptic Curve primality proving program PRIMO has been checking all probable
primes with this test for years, and no counterexample has been found yet. This has led M.
Martin to conclude that no number with less than 10,000 digits will pass the Baillie-PSW
test [Wei18]. However, a heuristic argument by Pomerance indicates that there are an infinite
number of counterexamples to the Baillie-PSW Primality test [Pom84].

4. Deterministic Tests
4.1. AKS Primality Test. The AKS Primality test was the first general, unconditional,
and determinstic primality test to run in polynomial time. While it is of immense theoretical
importance, it is not used in practice, rendering it as a galactic algorithm. For example, the
Baillie–PSW conjecture runs much faster for 64-bit integers. Furthermore, other algorithms
such as Elliptic Curve Primality Proving are also unconditionally correct and are much
better than the AKS Primality test. The original primality test was published in 2002 by
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. The AKS Primality Test is based off of
the following theorem:
Theorem 4.1. Given an integer n ≥ 2 and an integer a relatively prime to n, n is prime if
and only if the following congruence
(X + a)n ≡ X + a (mod n)
is true within the polynomial ring Z/nZ[X]. Note that X is the indeterminate generating the
polynomial ring.
This theorem can be easily proven using the binomial theorem, and we in fact do something
very similar to this in our proof of Theorem 2.13. While Theorem 4.1 could be its own
primality test, verifying it would take exponential time (as we would have to expand (X + a)n
and reduce modulo n).
However, there is a way to make the test a bit faster. We can instead take the polynomial
modulo another polynomial, X r − 1, for a small value of r. In other words, the following
equation must be satisfied:
 PRIMALITY TESTING 27

(4.1) (X + a)n − (X n + a) = (X r − 1)g(x) + nf (x),

for some polynomials f (x) and g(x). Note that all primes satisfy this equation, since if we
let g(x) = 0, then we arrive at Theorem 4.1. The congruence can be checked in polynomial
time when r is appropriately chosen as a small value (in other words, r is polynomial to the
digits in n). The AKS algorithm evaluates Equation 4.1 for a large range of a values.
We now define the AKS Primality Test algorithm below:
Definition 4.2 (AKS algorithm). The AKS Primality Test is as follows:
(1) Check if n = ab for for positive integer a and b > 1.
(2) Find the smallest r such that ordr (n) > log22 n. If r and n are not relatively prime,
then output that n is composite.
(3) For all 2 ≤ a ≤ min(r, n − 1), check that a ∤ n, if it does, then output that n is
composite.
(4) If n ≤ r, thenj output that nkis prime.
p
(5) For a = 1 to ϕ(r) log2 (n) perform Equation 4.1 with n. If n does not satisfy the
equation, then n is composite.
(6) Output that n is prime.
We now prove the following theorem:
Theorem 4.3. If n is prime, then it passes the AKS Algorithm ( 4.2)
Proof. A prime number would of course pass steps 1 and 3 since these are divisibility tests.
A prime would also pass step 5 because of Equation 4.1. Therefore, the algorithm would
either identify n as a prime in step 4 or 6. ■

We now prove the converse of the Theorem 4.3, through a sequence of lemmas. Note that
the following lemmas to come are inspired by [AKS04].
Lemma 4.4. There exists an r ≤ max 3, log52 (n) such that Step 2 in Definition 4.2 is true.
 

Proof. This theorem is of course true when n = 2, since this would imply that r = 3, which
satisfies all the conditions of the problem. Therefore,
 we assume that n > 2. This means that
n is at least 3 (since n is an integer), meaning that log52 (n) > 10. We now use the following

lemma, which will allow us to use this fact in a beneficial way (see [Nai82] for a proof):
Lemma 4.5. Let m be an integer greater than or equal to 7. Then the following inequality is
true:
LCM(1, 2, 3, . . . , m) ≥ 2m ,
where LCM means the Least Common Multiple of the numbers “passed into” the function.
28 AADITYA BILAKANTI

Let B = log52 (n) . Since Lemma 4.5 applies to m ≥ 7, this means that it also works for
 
B as well. Note that we also have that for an integer m ≥ 2 and an integer k, and a number
of the form mk ≤ B, the largest value of k is ⌊log2 (B)⌋. This is because we have that:

k · log2 (m) ≤ log2 (B)

log2 (B)
k≤
log2 (m)
k ≤ log2 (B),

where the last step results from the fact that the minimum of the denominator is log2 (2) = 1
(since m ≥ 2). Therefore, since k is an integer, we have that k can at maximum be ⌊log2 (B)⌋.
Note that therefore, this means that nlog2 (B) ≤ B. We now consider the smallest number r
that does not the divide the product

⌊logY
2 (n)⌋
2

n⌊log2 (B)⌋ · (ni − 1).

i=1

Notice that gcd(r, n) cannot be divisible by all the prime divisors pi of r, since this would
imply that r | n⌊log2 (B)⌋ . This is because this means that pi | gcd(r, n), and using the fact that
gcd(r, n) | n, meaning that pi | n. This means that n is divisible by all the prime divisors of
r and from our observation above, we know that this would imply that r | n⌊log2 (B)⌋ , which
r
is a contradiction to the fact that r does not divide the above product. Therefore, gcd(r,n)
cannot divide the product as well. We now use the fact that r is the smallest number to
not divide the product. If gcd(r, n) ̸= 1, this would mean that by our previous observation,
r
gcd(r,n)
wouldn’t divide the product. However, this contradicts the fact that r is the smallest
number to not divide the product. Therefore, gcd(r, n) = 1, or in other words, r is relatively
prime to n. Furthermore, since r does not divide ni − 1 for 1 ≤ i ≤ log22 (n) , this means
⌊logY
2 (n)⌋
2

2
that ordr (n) > log2 (n). We now create a nicer bound for (ni − 1).
i=1
⌊logY
2 (n)⌋
2
⌊log22 (n)⌋
i
Y
i
⌊log22 (n)⌋(⌊log22 (n)⌋+1)
i i
Note that since n − 1 < n , we have that (n − 1) < n =n 2 .
i=1 i=1
However, we can replace log22 (n) with log22 (n) − 1. This is because while this would
 
⌊log22 (n)⌋(⌊log22 (n)⌋+1)
create a value that is less than n 2 , the product would still be greater than
Q⌊log22 (n)⌋ i Q⌊log22 (n)⌋ i log2 2
2 (n)(log2 (n)−1)
i=1 (n − 1). Therefore, we have that i=1 (n − 1) < n 2 . We can now
 PRIMALITY TESTING 29

use this to make our original product much “nicer”. This gives us the inequality:
2 (n)⌋
⌊logY
2
log2 2
2 (n)(log2 (n)−1) 4 5
n⌊log2 (B)⌋ · (ni − 1) < n⌊log2 (B)⌋+ 2 ≤ nlog2 (n) ≤ 2log2 (n) ≤ 2B .
i=1

Note that the above inequality only holds for n ≥ 2. By  Lemma  4.5, we know that
B 5
LCM(1, 2, 3, . . . , B) ≥ 2 . Therefore, we know that r ≤ B = log2 (n) . Therefore, we proved
the lemma. ■
The main importance of the above lemma is to show that r = O(log5 (n)), which makes the
test extremely inefficient. As we shall see later, certain conjectures will speed up this process
to find r greatly, and thus reduce the overall time complexity of the algorithm. However,
we shall first prove the converse of Theorem 4.3. Since ordr (n) > 1, there exists a prime
divisor of n, p, such that ordr (p) > 1. We know that p > r, otherwise Step 3 or 4 would have
∗
already ended the test. Using this fact, we know that gcd(rn, ) = 1, we know jp that p, r ∈kZr .
For the remainder of the proof, we let p and r be fixed. We also let c = ϕ(r) log2 (n) .
Step 5 of the algorithm verifies c equations based on Theorem 4.1. Since the algorithm
does not out output whether the number is composite or not in this step, we have:
(4.2) (X + a)n ≡ X n + a (mod X r − 1, n),
for every 0 ≥ a ≤ c. This also gives us
(4.3) (X + a)n ≡ X n + a (mod X r − 1, p),
for 0 ≥ a ≤ c. We also have by Theorem 4.1
(4.4) (X + a)p ≡ X p + a (mod X r − 1, p).
The previous two equations imply that
n
(4.5) (X + a)n/p ≡ X p + a (mod X r − 1, p).
Therefore, n and np both behave like p in the above equation. We give a name to this
property (the same name as given in the original paper):
Definition 4.6. For a polynomial f (x) and a positive integer m, m is known as introspective
for f (x) if:
[f (X)]m ≡ f (X m ) (mod X r − 1, p).
From Equations 4.3 and 4.4, we can see that np and p are both introspective for X + a,
when 0 ≤ a ≤ c. We now prove the following lemma, which shows that introspective numbers
are closed under multiplication.
Lemma 4.7. If a and b are introspective numbers for f (X), then ab is also introspective for
f (X).
30 AADITYA BILAKANTI

Proof. We first use the property that a is introspective for f (X). This means that we have:
[f (X)]a ≡ f (X a ) (mod X r − 1, p).
We can raise both sides of the congruence to power of b, giving us:
(4.6) [f (X)]ab ≡ [f (X a )]b (mod X r − 1, p).
However, note that since b is also introspective for f (X), we have that:
[f (X a )]b ≡ f (X ab ) (mod X ar − 1, p).
However, since X r − 1 divides into X ar − 1, the above equation can become:
(4.7) [f (X a )]b ≡ f (X ab ) (mod X r − 1, p).
Therefore, combining Equations 4.6 and 4.7 and gives us [f (X)]ab ≡ f (X ab ) (mod X r − 1, p).
Therefore, we have proved the lemma. ■
We also prove that for a number a, the set of polynomials that a is introspective to is also
closed under multiplication.
Lemma 4.8. If m is introspective to f (X) and g(X), then m is introspective to f (X) · g(X).
Proof. We have
[f (X) · g(X)]m ≡ [f (X)]m · [g(X)]m (mod X r − 1, p) ≡ [f (X m )] · [g(X m )] (mod X r − 1, p).
The above equation uses the fact that m is both introspective to f (X) and g(X). Therefore,
we have proved the lemma. ■
The above two lemmas together imply that the set I = {( np )i · pj | i, j ≥ 0} is introspective
for all polynomials in the set P = { ca=0 (X +a)ea | ea ≥ 0}. This is because from our previous
Q
observations, we know that p and np are both introspective for X + a (where 0 ≤ a ≤ c).
Therefore, by Lemma 4.7, we know that their product will also be introspective for X + a. In
set P , since the elements are products of X + a, we know that by Lemma 4.8, the elements
of I must be introspective to set P . We now define two groups that will important for later
lemmas.
We define the group G to be the set of all residues of I modulo r. Note that this is a
subgroup of Z∗r , because we showed that gcd(n, r) = 1 and gcd(r, p) = 1. We also let |G| = t.
G is generated by n and p (these numbers create I). Since ordr (n) > log22 (n), we know that
t > log22 (n). This is because we know that the residue of n modulo r is in G, and the order of
n must be divisible by t by Lagrange’s Theorem. Therefore, t > log22 (n).
We now define the second group using properties of cyclotomic polynomials. We let Qr (X)
be the rth cyclotomic polynomial over Fp . This means that Qr (X) factorizes into irreducible
polynomials of degree ordr (n) and also divides X r − 1. We let k(X) be one of the irreducible
factors. Since ordr p > 1, the degree of k(X) is greater than one (since each of the factors
have a degree equal to ordr p > 1 as stated previously). The second group H is the set
of all polynomials in P modulo k(X) and p (written as P (X) (mod k(X), p)). This group
 PRIMALITY TESTING 31

is generated by X, X + 1, X + 2, . . . , X + c (these are what create the set p) in the field

F = Fp [X]/(k(X)), and is also a subgroup of the multiplicative group of F . We now prove
the following lemma which puts a lower bound on |H|.
t+c


Lemma 4.9. |H| ≥ t−1 .
Proof. It is important to note that since k(X) is a factor of Qr (X), X is a primitive rth root
of unity in F (all roots of a cyclotomic polynomial are primitive roots of unity).
We now show that any two distinct polynomials of degree less than t in P will map to
different elements in H. We let f (X) and g(X) be two polynomials in P . Suppose that
f (X) = g(X) in the field F , and let m ∈ I. We therefore have [f (X)]m = [g(X)]m in F
(since f (X) = g(X) in F ). However, note that m is also introspective for both f (X) and
g(X) (all elements of I are introspective to the polynomials in P ). Therefore, we have that
f (X m ) = g(X m ) as well. Subtracting g(X m ) from both sides gives us f (X m ) − g(X m ) = 0,
meaning that X m is a root for Q(Y ) = f (Y ) − g(Y ), for every m ∈ G (we never assumed
anything about m). Since gcd(m, r) = 1 (G ≤ Z∗r , meaning that all elements of G are relatively
prime to r), we know that X m is a primitive root of unity. This is because at the beginning
of the proof, we stated that X was a primitive root of unity, and since gcd(m, r) = 1, this
means that X m is also a primitive root of unity. Therefore, there will be t distinct roots of
Q(Y ) in F , meaning deg(Q(Y )) = t. However, this contradicts the fact that we chose f (X)
and g(X) to have a degree less than t, so their difference could not have produced a new
polynomial of degree t. Therefore, f (X) ̸= g(X).
Note
p that y and z in F cannot be equal to each other, for 1 ≤ y = ̸ z ≤ c. This is because
√ p
c = ϕ(r) log2 (n) < r log2 (n) < r < p. Therefore, there are more elements in Fp than the
̸ j. This means X, X + 1, X + 2, . . . , X + c are all distinct. Since
value of c, so therefore, i =
deg(h(X)) > 1, X + a ̸= 0 for 0 ≤ a ≤ c in F . This is because all elements of H are the
polynomials of P (which are products of the polynomials of X + a) taken modulo h(X) and
p. However, since deg(X + a) < deg(h(X)), X + a ̸= 0 in F . This means that there are at
t+c


least c + 1 polynomials of degree 1 in H. Therefore, there are at least t−1 polynomials of
t+c


degree less than t in H, meaning that |H| ≥ t−1 . We have thus proved the lemma. ■
We give an upper bound for |H|:
√
Lemma 4.10. If n is not a power of p, then |H| ≤ n t .
Proof. We first consider a subset of I, which we shall call I ′ :
n √
I ′ = {( )i · pj |0 ≤ i, j ≤ t}.
p
If n is not a power of p (if it were then the np would reduce into another power of p), there are
√  √ 
( t + 1)2 > t distinct members (since i and j can be any value from 0 to t , meaning
√ 
that they have t + 1 options each). This means that there must be at least two elements
in I ′ that have equal residues modulo r. This is because since I ′ is larger than G, at least
32 AADITYA BILAKANTI

two of the numbers must share residues, since G is the set of all residues in I modulo r. We
let these numbers be a and b, with a > b. Therefore, we have:
X a ≡ X b (mod X r − 1).
We now let f (X) ∈ P . Since a is introspective to all polynomials in P , we have:
[f (X)]a ≡ f (X a ) (mod X r − 1, p)
≡ f (X b ) (mod X r − 1, p)
≡ [f (X)]b (mod X r − 1, p),
implying that [f (X)]a = [f (X)]b in the field of F . This is because if they weren’t equal, there
wouldn’t exist polynomials g(X) and h(X) as outlined in Equation 4.1. Therefore, f (X) ∈ H
is a root of the polynomial S(X) = Y a − Y b in F . Since we picked f (X) from H with no
assumptions, S(X) must have √
at least |H| distinct roots in F . We know that √
the degree of
S(X) is a, so a ≤ (n/p · p) ⌊ t⌋
. This follows from the fact that (n/p · p) ⌊ t⌋
is the largest
′ ′
element in √
I , and since a is an element of √
I , it must be less than or√equal to it. However,
(n/p · p)⌊ t⌋
is also less than or equal to n . This means that |H| ≤ n t , and we have proved
t

the lemma. ■
Using these estimates, we can finally prove that if the algorithm outputs that n is prime,
then n is truly prime.
Theorem 4.11 (Converse of Theorem 4.3). If the AKS algorithm outputs that n is prime,
then n must be prime.
√
Proof. It is important to note that t > t log√ 2 (n). This is because we showed earlier that
2
t > log2 (n), which can
√ be transformed into t > t log2 (n) (taking the square root of both sides
and multiplying by t). We also note that c > ⌊t log2 (n)⌋. This is because we remember that
G is a subgroup of Z∗r , which has jpan order of ϕ(r),
k meaning that |G| = t ≤ ϕ(r). Therefore,
√ 
c> t log2 (n) , because c = ϕ(r) log2 (n) . Using the above inequalities and Lemma
4.9, we have:
 
t+c
|H| ≥
t−1
 √ 
c+1+ t log2 (n)
≥ √ 
t log2 (n)
 √ 
2 t log2 (n) + 1

≥ √ 
t log2 (n)
√ √ √ √
2⌊ t log2 (n)⌋+1
(2⌊ t log2 (n)⌋+1)·(2⌊ t log2 (n)⌋)·...·(⌊ t log2 (n)⌋+2)
We now expand √ , giving us: √ √
(⌊ t log2 (n)⌋)·(⌊ t log2 (n)⌋−1)·...·1
. We
√ ⌊ t log
 2 (n)⌋ √  √ 
now “pair” 2 t log2 (n) with t log2 (n) , and so on to t log2 (n) + 2 with 2. Therefore,
 PRIMALITY TESTING 33
√  √ 
2 t log2 (n) + 1 is paired with 1. Excluding the pair with 2 t log2 (n) + 1, since the
√
quotient of each of these pairs√is at least 2, we have 2⌊ t log2 (n)⌋−1 . We multiply this by
2 t log2 (n) + 1, giving us 2⌊ t log2 (n)⌋−1 · (2 t log2 (n) + 1). We pull out a 2 from the
√  √ 
√
latter term, giving us 2⌊ t log2 (n)⌋ · ( t log2 (n) + 12 ). ( t log2 (n) + 12 ) can be estimated
√  √ 
√
as 2. Therefore, we have 2⌊ t log2 (n)⌋+1 . We can now continue our “inequality chain”:
 √ 
2 t log2 (n) + 1

|H| ≥ √ 
t log2 (n)
√
> 2⌊ t log2 (n)⌋+1
√
≥ n t.
√ √
By Lemma 4.10, |H| ≤ n t if n is not a power of p. However, we just showed that |H| ≥ n t ,
meaning that n must be a power of p. Therefore, n = pv , for some integer v greater than 0.
However, if v > 1, then step 1 would have determined n as composite. Therefore, n must be
prime and we have proved the theorem. ■
The above theorem definitively shows that the AKS primality test is deterministic. We
now look at the time complexity. The time complexity of the algorithm itself was shown to
be Õ((log n)12 ). However, if the following widely-held conjecture about the distribution of
Sophie-Germain primes were true, then the time complexity would be cut down to Õ((log n)6 ).
Note that these reductions all come from the fact that we can minimize the size of r, which
reduces the amount of computations needed for other steps (especially step 5).
We now give the conjecture:
Conjecture 4.12 (Sophie Germain Prime Density Conjecture). The number of primes q less
than or equal to a number m such that 2q + 1 is also prime is asymptotically ln2C2 (m)
2m
, where C2
is the twin prime constant (which is approximately 0.66).
The above conjecture implies that r = Õ(log2 (n)). This is because by Conjecture 4.12, we
know that there are at least log22 (n) such primes between 8 log22 (n) and c log22 (n)(log2 log2 n),
for a suitable value of c. Note that for any such prime q, the possible orders of n modulo q
are ordq (n) ≤ 2 or ordq (n) ≥ q−1
2
. If ordq (n) ≤ 2, then q must divide n2 − 1, meaning that it
is bounded by O(log n). This is because there are at most ln(n2 − 1) prime factors of n2 − 1,
which is approximately 2 ln n. This implies that there exists an r = Õ(log2 (n)), such that
ordr (n) > log22 (n). This value of r gives us an algorithm of Õ(log6 (n)).

5. Future Directions and Conclusion

5.1. Euler Jacobi Pseudoprimes and Carmichael Numbers. At the end of Section
3.2, I gave a table that outlines bounds on when the Solovay–Strassen test is deterministic.
The results in the table may lead us to the following observation (excluding the last row):
34 AADITYA BILAKANTI

Observation 5.1. If a pair of pre–selected bases for the Solovay–Strassen contains the
number 2, the test is deterministic until some Carmichael Number.
This observation was disproved by the set {2, 88} (in the table), which had a “bound” that
was not a Carmichael Number (which was 2047). Analyzing the number of counterexamples
to the above observation, specifically the primes, gives us some interesting results/graphs.
Below I give step counting functions for the set {2, n}, where the maximum values of n are
100, 000 in Figure 1 and 2 and 1, 000, 075 in Figure 3 and 4(generated by implementing
code and graphing my results on Matplotlib). Each of the figures give a “zoomed in” and
“zoomed out” plot of our prime counterexamples, to get a better sense for their distribtuion. I
also give the approximate ratios for the number of counterexamples to the total amount of
numbers tested (they are given in the tables following the figures).

Figure 1. Prime Counterexamples To Our Observation Until 100,000

Figure 2. Prime Counterexamples To Our Observation Until 100,000

 PRIMALITY TESTING 35

From the “zoomed in” version of the graph, we can definitely see that there are certain
ranges that have fewer amounts of counterexamples to our observation than others. This
trend also seems to continue when increase the range of n. In other words, the amount of
counterexamples within a given range is relatively inconsistent. However, the zoomed out
picture shows us that the graph still increases relatively smoothly asymptotically, which may
allow us to create an analogue to the prime counting function for these prime counterexamples.

Figure 3. Prime Counterexamples To Our Observation Until 1,000,075

Figure 4. Prime Counterexamples To Our Observation Until 1,000,075

n ≤ 100, 000 Count Approximated Ratio

Total Counterexamples 36436 36436/100000 = 0.36436
Prime Counterexamples 3093 3093/100000 = 0.03093
36 AADITYA BILAKANTI

n ≤ 1, 000, 075 Count Approximated Ratio

Total Counterexamples 337040 337040/1000075 = 0.337
Prime Counterexamples 20930 20930/1000075 = 0.0209
As stated previously, the main difficulty in analyzing these counterexamples and the ratios
is that the graph does not increase “smoothly”. While we do know that each of the above
figures are bounded from above by the prime counting function, this is of course not the best
estimate. I am currently trying to find a better heuristic estimate to find the number of
these prime counterexamples that exist less than a number n. Using these results, I hope
to find a method that can generalize this to all counterexamples, and not just the prime
counterexamples.
It is also important to note that some of the numbers that are products of twin primes are
counterexamples to this hypothesis. I list the first 10 twin prime numbers that are counterex-
amples to my hypothesis: 143, 323, 3599, 5183, 19043, 32399, 57599, 72899, 97343, 186623.
To see a comprehensive list of the counterexamples, go to this link that I have created:
Counterexamples To Hypothesis.

5.2. Conclusion. While we have covered a wide range of primality tests, there are still
many others, each with their own merits. These include the Frobenius Tests [Kha20, Gra98],
Elliptic Curve Primality Proving [Uzu04], etc. The author encourages the reader to learn
about these primality tests as well, as they offer even more unique perspectives on prime
numbers and ultimately shows the diversity in the field of Primality Testing.

6. Acknowledgements
The author would like to thank Katherine Martin and Dr. Simon Rubinstein-Salzedo for
insightful conversations and guidance.

References
[AGP94] W. R. Alford, Andrew Granville, and Carl Pomerance. There are infinitely many Carmichael
numbers. Ann. Math. (2), 139(3):703–722, 1994.
[AKS04] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Ann. Math. (2), 160(2):781–
793, 2004.
[Arn97] F. Arnault. The Rabin-Monier theorem for Lucas pseudoprimes. Math. Comput., 66(218):869–881,
1997.
[Bur10] David Burton. Elementary Number Theory. McGraw Hill, seventh edition, 2010.
[Con16] Keith Conrad. Carmichael Numbers And Korselt’s Criterion, 2016.
[CP05] Richard Crandall and Carl Pomerance. Prime numbers. A computational perspective. New York,
NY: Springer, 2nd ed. edition, 2005.
[Fei13] Jan Feitsma. Tables of pseudoprimes and related data, 2013.
[Gra98] Jon Grantham. A probable prime test with high confidence. J. Number Theory, 72(1):32–47, 1998.
[Jae93] Gerhard Jaeschke. On strong pseudoprimes to several bases. Math. Comput., 61(204):915–926, 1993.
[Kha20] Sergei Khashin. Evaluation of the effectiveness of the frobenius primality test, 2020.
[Nai82] M. Nair. On Chebyshev-type inequalities for primes. Am. Math. Mon., 89:126–129, 1982.
 PRIMALITY TESTING 37

[Pom84] Carl Pomerance. ARE THERE ANY COUNTEREXAMPLES TO THE BAILLIE–PSW PRIMAL-
ITY TEST, 1984.
[PSW80] Carl Pomerance, J. L. Selfridge, and Samuel S. jun. Wagstaff. The pseudoprimes to 25 · 109 . Math.
Comput., 35:1003–1026, 1980.
[Sch08] René Schoof. Four primality testing algorithms. In Algorithmic number theory. Lattices, number
fields, curves and cryptography, pages 101–126. Cambridge: Cambridge University Press, 2008.
[SS77] R. Solovay and V. Strassen. A fast Monte-Carlo test for primality. SIAM J. Comput., 6:84–85, 1977.
[SS78] R. Solovay and V. Strassen. Erratum: A fast Monte-Carlo test for primality. SIAM J. Comput.,
7:118, 1978.
[Uzu04] Osmanbey Uzunkol. ATKIN’S ECPP (Elliptic Curve Primality Proving) ALGORITHM. Master’s
thesis, TECHNICAL UNIVERSITY OF KAISERSLAUTERN, 2004.
[Wei18] Eric W. Weisstein. Tree. From MathWorld—A Wolfram Web Resource, 2018.
Email address: abilak@gmail.com