MINISTRY OF EDUCATION AND TRAINING
HANOI PEDAGOGICAL UNIVERSITY 2

DEPARTMENT OF MATHEMATICS

NGUYEN THI KIM CHI

MILLER – RABIN PRIMALITY TESTING

Major: Algebra

GRADUATION THESIS

Hanoi – 2019


MINISTRY OF EDUCATION AND TRAINING
HANOI PEDAGOGICAL UNIVERSITY 2

DEPARTMENT OF MATHEMATICS

NGUYEN THI KIM CHI

MILLER - RABIN PRIMALITY TESTING

GRADUATION THESIS

SUPERVISOR:
Dr. TRAN NAM TRUNG

Hanoi – 2019

1

Thesis Acknowledgement
I would like to express my gratitudes to the teachers of the Department of Mathematics, Hanoi Pedagogical University 2, the teachers in the algebra group as well
as the teachers involved. The lecturers have imparted valuable knowledge and facilitated for me to complete the course and the thesis.
In particular, I would like to express my deep respect and gratitude to Dr. Tran
Nam Trung, who has direct guidance, help me complete this thesis.
Due to time, capacity and conditions are limited, so the thesis can not avoid
errors. Then, I look forward to receiving valuable comments from teachers and
friends.
Ha Noi, May - 2019
Student

Nguyen Thi Kim Chi


Graduation thesis

NGUYEN THI KIM CHI

Thesis Assurance
I assure that the data and the results of this thesis are true and not identical to other topics. I also assure that all the help for this thesis has been acknowledged and that the results presented in the thesis has been indentified clearly.
Ha Noi, May - 2019
Student

Nguyen Thi Kim Chi

i



Contents

Thesis Acknowledgement

1

Thesis Assurance

i

Preface

1

1 Congruence

2

1.1

Congruence . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2

Fermat’s Little theorem . . . . . . . . . . . . . . . . .


5

2 Miller - Rabin primality testing

10

2.1

Prime number . . . . . . . . . . . . . . . . . . . . . . .

10

2.2

Miller-Rabin primality test . . . . . . . . . . . . . . . .

11

2.3

Testing against small sets of bases . . . . . . . . . . . .

16

ii


Graduation thesis

NGUYEN THI KIM CHI


Preface
A prime number (or a prime) is a natural number greater than 1
that cannot be formed by multiplying two smaller natural numbers. A
natural number greater than 1 that is not prime is called a composite
number. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is
either a prime itself or can be factorized as a product of primes that
is unique up to their order.
A primality test, the topic of this thesis, is simply an algorithm
that tests, either probabilistically or deterministically, whether or not
a given input number is prime. The larger the number, the greater
will be the time required to test this and this is what prompts us to
search for efficient primality tests that are polynomial in complexity.
There are some primality tests which conclusively determine whether
a number is prime or composite and are therefore deterministc, while
others, such as the Fermat and the Miller-Rabin tests, despite correctly
classifying all prime numbers, may allow some some composites to filter through, incorrectly labelling them as primes or probably primes,
and this makes these tests probabilistic.
Therefore, I chose a primality testing by Miller - Rabin that is a
thesis title for me.

1


Chapter 1
Congruence
This chapter will recall congruence theory, Euler’s theorem, Fermat’s
little theory and Wilson’s theorem (see e.g. [2]).

1.1


Congruence

Let a, b and n > 0 be integer numbers.
Definition 1.1.1. If n divides the diference a − b then a and b are
said to be congruent modulo n, denoted by a ≡ b (mod n). If n not
divides the difference a − b then a and b are said to be incongruent
modulo n, denoted by a ≡ b (mod n).
Remark 1.1.2. a ≡ b (mod n) if and only if a and b have the same
remainder on division by n.
Example 1.1.3. We have
1. 13 ≡ 123 (mod 11) since 13 − 123 = −110 = (−10).11;
2. −15 ≡ −64 (mod 7) since −15 − (−64) = 7.7;

2


Graduation thesis

NGUYEN THI KIM CHI

3. 23 ≡ 122 (mod 11) since 23 and 122 have remainder 1 on division
by 11.
The following theorem give basic properties of congruences.
Theorem 1.1.4. Let n > 1 be a fixed and a, b, c, d be arbitrary integers. Then,
1. a ≡ a (mod n).
2. If a ≡ b (mod n), then b ≡ a (mod n).
3. If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n).
4. If a ≡ b (mod n) and c ≡ d (mod n), then a+c ≡ b + d (mod n)
and a.c ≡ b.d (mod n).

5. If a ≡ b (mod n), then a + c ≡ b + c (mod n) and a.c ≡ b.c
(mod n).
6. If a ≡ b (mod n), then ak ≡ bk (mod n), for any integer k

1.

Example 1.1.5. Prove that 11 divides 215 + 1.
Solution. We have 25 ≡ −1 (mod 11). Hence,
(25 )3 ≡ (−1)3 ≡ −1

(mod 11),

and hence
215 + 1 ≡ −1 + 1 ≡ 0

(mod 11).

Example 1.1.6. Find the remainder obtained upon dividing the sum
1! + 2! + 3! + ... + 100! by 10.
3


Graduation thesis

NGUYEN THI KIM CHI

Solution. Put A = 1! + 2! + 3! + ... + 100!. We have
1! + 2! + 3! + 4! = 1 + 2 + 6 + 24 = 33.
Moreover, 33 ≡ 3 (mod 10). If k


5, then

k! = 5! · 6 · 7 · · · k ≡ 0

(mod 10).

Thus, A ≡ 0 + 3 ≡ 3 (mod 10). It follows that the sum leaves the
remainder of 3 when divided by 10.
In the thesis we use (a, b) for the greatest common divisor of a and
b. Observer that
1) If b | a and b = 0, then (a, b) = |b|.
2) If a = qb + r for some integers q and r, then (a, b) = (b, r).
From this observation we can find (a, b), b > 0, by Euclidean algorithm as follows:
Euclidean Algorithm:
We use the division algorithm successively:
0 ≤ r1 < b

a = bq1 + r1 ,
b = r1 q2 + r2 ,

0 ≤ r2 < r1

r1 = r2 q3 + r3 ,

0 ≤ r3 < r2

···
rn−2 = rn−1 qn + rn ,
rn−1 = rn qn+1 .
4


0 ≤ rn < rn−1


Graduation thesis

NGUYEN THI KIM CHI

Then, (a, b) = rn .
Example 1.1.7. Find the greatest common divisor of 2266 and 1276.
Solution. Since
2266 = 1276.1 + 990
1276 = 990 · 1 + 286
990 = 286 · 3 + 132
286 = 132 · 2 + 22
132 = 22.6
we obtain (2266, 1276) = 22.

1.2

Fermat’s Little theorem

Definition 1.2.1. (Euler’s phi-function) For n ∈ N, let
ϕ(n) = #{a ∈ N : a ≤ n and (a, n) = 1}.
In particular, if p is any prime number then
ϕ(p) = #{1, 2, ..., p − 1} = p − 1.
Example 1.2.2.
ϕ(1) = #{1} = 1, ϕ(2) = #{1} = 1,
ϕ(3) = #{1, 2} = 2, ϕ(4) = #{1, 3} = 2.
We can compute ϕ(n) by the following formula.

5


Graduation thesis

NGUYEN THI KIM CHI

Proposition 1.2.3. If n = p1 k1 · p2 k2 · · · pr kr where n ∈ N and pj are
primes distinct, then
ϕ(n) = (p1 − 1)p1 k1 −1 · · · (pr − 1)pr kr −1 = n
p|n

1
(1 − )
p

where the product runs over prime divisors p of n.
Example 1.2.4. Compute ϕ(100).
Solution. Since 100 = 22 .52 , we have
ϕ(100) = (2 − 1).22−1 .(5 − 1).52−1 = 40.

Theorem 1.2.5. (Euler’s theorem) Let a be an integer and n a positive
integer with (a, n) = 1. Then,
aϕ(n) ≡ 1

(mod n).

Proof. The set of units in Z/nZ is a group
(Z/nZ)∗ = {a ∈ Z/nZ : gcd(a, n) = 1}
which has order ϕ(n).

The theorem then proclaim that the order of an element of (Z/nZ)∗
divides the order ϕ(n) of (Z/nZ)∗ . This is a special case of the more
general fact (Lagrange’s theorem) that if G is a finite group and g ∈ G,
then the order of g divides the cardinality of G.
Example 1.2.6. Find the two last digits of the following numbers:
6


Graduation thesis

NGUYEN THI KIM CHI

1) 20172019 .
2018

2) 20172019

.

Solution. 1) We have: ϕ(100) = 40. By Euclidean algorithm, we have
(2017, 100) = 1. By Euler’s theorem,
2017ϕ(100) = 201740 ≡ 1

(mod 100).

It follows that
20172019 = 201719 · (201740 )50 ≡ 201719

(mod 100).


In the other hand, 2017 ≡ 17 (mod 100). Thus,
20172019 ≡ 1719 ≡ 17.(173 )6 ≡ 17.136 ≡ 17.9 ≡ 53

(mod 100).

Therefore, the two last digits of the number 20172019 is 53.
2) We have ϕ(40) = 16. By Euclidean algorithm, (2019, 40) = 1.
By Euler’s theorem, we get:
2019ϕ(40) = 201916 ≡ 1

(mod 40).

It follows that 20192018 ≡ 20192 (mod 40). Thus,
20192018 ≡ 192 ≡ 1

(mod 40)

and thus 20192018 = 1 + 40n for some integer n.
2018

Hence, 20172019

= 20171+40n ≡ 2017 ≡ 17 (mod 100). It implies
2018

that the last two digits of the number 20172019
7

is 17.



Graduation thesis

NGUYEN THI KIM CHI

As a consequence of Euler’s theorem, we have:
Theorem 1.2.7. (Fermat’s Little theorem) Let p be a prime and a an
integer. If p a, then ap−1 ≡ 1 (mod p)
We conclude this chapter with Wilson’s theorem.
Theorem 1.2.8 (Wilson’s theorem). An integer p > 1 is prime if and
only if (p − 1)! ≡ −1 (mod p).
Proof. (=⇒) Assume that p is a prime and we need to show that
(p − 1)! ≡ −1 (mod p).
It is obvious when p = 2. Assume that p > 2.
If a ∈ {1, 2, . . . , p − 1}, then the equation ax ≡ 1 (mod p) has a
unique root a ∈ {1, 2, . . . , p − 1}.
If a = a , then a2 ≡ 1 (mod p). Hence, p | a2 − 1 = (a − 1)(a + 1).
Since p is a prime, p | (a−1) or p | (a+1). It follows that a ∈ {1, p−1}.
Thus pair of the elements of {2, 3, ..., p−2}, each with their inverse.
So 2 · 3 · · · (p − 2) ≡ 1 (mod p).
Multiplying both sides by p − 1 proves that (p − 1)! ≡ −1 (mod p).

(⇐=) Suppose that (p − 1)! ≡ −1 (mod p). We will prove that p
must be prime.
Assume that p is not a prime, so that p > 4 is a composite number.
Let m be a prime divisor of p. Then m < p, so m|(p − 1)!.
By hypothesis, m | p | ((p−1)!+1). This is a contradiction, because
a prime can not divide a number a and also divide a+1, since it would
then have to divide (a + 1) − a = 1. This implies that p is a prime.
8



Graduation thesis

NGUYEN THI KIM CHI

Remark 1.2.9. Wilson’s theorem could be viewed as a primality test
but it is probably one of the word’s least efficient primality tests since
computing (p − 1)! take so many steps.
Example 1.2.10.

1. With p = 7 then (7 − 1)! ≡ 6! ≡ 720 ≡ −1

(mod 7)
2. With p = 12 then (12 − 1)! ≡ 11! ≡ 39916800 ≡ 0 (mod 12).
Therefore, 12 is composite.

9


Chapter 2
Miller - Rabin primality testing
The Miller-Rabin primality test, due to Michael O. Rabin and Gary
L. Miller, is an unconditional but probabilistic algorithm for primality
testing. We start with the definition of prime numbers and some
simple primality tests.

2.1

Prime number


Definition 2.1.1. An integer p > 1 is called a prime number (or a
prime) if there is no divisor d of p satisfying 1 < d < p. If an integer
a > 1 is not a prime number, then it is called a composite number.
Example 2.1.2. We have
(1) 2 is a prime since its divisors are 1 and 2.
(2) 4 is a composite number because 2 is a divisor of 4.
Theorem 2.1.3. The smallest divisor and different 1 of a composite
√
a is not greater than a.

10


Graduation thesis

NGUYEN THI KIM CHI

Proof. Let p be a smallest divisor different 1 of a composite a, so p is
a prime.
Suppose that a = pa1 . Since p is a smallest divisor and a is a
composite, we have p ≤ a1 . Thus, p2 ≤ a1 p = a. It follows that
√
p ≤ a, as required.
Corollary 2.1.4. A natural number a > 1 is a prime if and only if it
√
has no prime divisors in the interval from 1 to a.
From this corollary we have a primality test as follows:
—————————————————————————————–
ALGORITHM Primality Test (n)

—————————————————————————————–
1. If n = 2, then n is a prime and stop the algorithm.
√
2. For each primes in range (2, n), if p | n, then n is a composite
number and stop algorithm.
3. Output n is a prime.
—————————————————————————————–
Example 2.1.5. 101 is a prime.
√
Solution. We have [ 101] = 10; and the primes in range (2, 10) are
2, 3, 5, 7. They are not divisors of 101, so 101 is a prime.

2.2

Miller-Rabin primality test

We first describe the Miller-Rabin primality test (see e.g. [4]). Let
n > 1 be an integer. If n = 2, then n is a prime, and so we assume
11


Graduation thesis

NGUYEN THI KIM CHI

that n > 2 is an odd number.
Write n = 2s r + 1 where r is odd and s

1. Now assume that n


is a prime, then for any a with (a, n) = 1, the congruence an−1 ≡ 1
(mod n) by Fermat’s little theorem, implying
s

a2 r ≡ 1

(mod n).
s−1

Taking square roots on both sides, we get a2

r

≡ ±1 (mod n). This

s

because a2 r ≡ 1 (mod n), it implies that
s

n | a2 r − 1, and so n | (a2
s−1

Since n is a prime, we have n | a2
s−1

that a2

r


r

s−1

r

s−1

− 1)(a2

r

s−1

− 1, or n | a2

r

+ 1).
+ 1. This means

≡ ±1 (mod n).

If we continue to take square roots repeatedly, we will get the conj

gruence a2 r ≡ −1 (mod n) for some j ∈ {0, 1, 2, . . . , s − 1}, or otherwise, we will get ar ≡ 1 (mod n). So, whenever n is a prime, either
j

ar ≡ 1 (mod n) or a2 r ≡ −1 (mod n) for some j ∈ {0, 1, 2, . . . , s−1}.
If both fail to hold, the algorithm outputs a composite number, but

if they do, we say that n passes the Miller-Rabin test. Even if n passes
the test, we cannot say with certainty that n is prime, but must check
for another value of a to improve our accuracy.
—————————————————————————————–
ALGORITHM Miller-Rabin Test (n)
—————————————————————————————–
1. Write n − 1 = 2s r, where s is odd.
12


Graduation thesis

NGUYEN THI KIM CHI

2. Choose a random value a such that 1 < a ≤ n − 1.
3. Compute T = ar (mod n).
4. If T = 1, return n is a prime.
5. For j from 0 to s − 1,
if T = −1 (mod n) then return n is a prime, else T = T 2
(mod n).
6. Return n is a composite.
—————————————————————————————–
Remark 2.2.1. If n passes the Miller-Rabin test, it may be not a
prime, and then it is often called a pseudo-prime number.
Definition 2.2.2. Let n be an odd composite number and let n =
2s r + 1 with r odd, and let 1 ≤ a ≤ n − 1. If ar ≡ 1 (mod n),
j

and a2 r ≡ −1 (mod n) for all j ∈ {0, 1, 2, . . . , s − 1}, a is called a
strong witness for n. If either of the two congruences holds for some

0 ≤ j ≤ s − 1, then a is called a strong liar for n.
The Miller-Rabin primality test based on the following result, which
states that there is no n for which all 1 ≤ a ≤ n − 1 with (a, n) = 1
are strong liars.
Theorem 2.2.3 (see [4]). If n is an odd composite integer, the number
of strong liars for n is less than or equal to ϕ(n)/4, where ϕ(n) is the
Euler’s function for n.

13


Graduation thesis

NGUYEN THI KIM CHI

Example 2.2.4. Consider the number 133, which is a composite number. The set of strong liars for it is (18 numbers):
{1, 11, 12, 27, 30, 31, 39, 58, 64, 69, 75, 94, 102, 103, 106, 121, 122, 132}.
Remark 2.2.5 (The probability for a composite number passing the
test). Since n is composite, ϕ(n) < n − 1, implying that n can pass
the Miller-Rabin’s test, i.e., will be labelled composite by it, for at
most (n − 1)/4 values of a with 1 ≤ a ≤ n − 1 and (a, n) = 1. So
the probability that a random number a in this set is a strong liar for
n is at most 1/4, and if we carry out the test for k different bases,
i.e., k different values of a, the failure probability is at most 1/4k . For
example if we carry the Miller-Rabin primality test 20 times, then the
probability of failure is about 1/420 , which is very small.
Example 2.2.6. Let us carry out the Rabin-Miller primality test on
the number 1729, using a = 621.
Solution. We have 1729 − 1 = 1728 = 26 · 27. So s = 6, r = 27.
62127 ≡ 1084


(mod 1729)

62127·2 ≡ 10842 ≡ 1065
2

62127·2 ≡ 10652 ≡ 1

(mod 1729)

(mod 1729).

The test declares that 1729 is a composite number, and terminates.

Remark 2.2.7. Let a, n be integers and m a nonnegative integer. In

14


Graduation thesis

NGUYEN THI KIM CHI

order to compute am (mod n), we simply compute directly
am = a · a · · · a (mod n)
by repeatedly multiplying by a (m times) and reducing modulo n.
However, this direct method is inefficient because it takes m − 1 multiplications, which is huge if m has hundreds of digits.
A much more efficient algorithm for computing am (mod n) is the
method of repeated squaring based on the observation that


m

a ≡



(a2 )m/2

(mod n)


a · (a2 )(m−1)/2

if m is even

(mod n)

if m is odd.

This allows us to reduce the exponent half.
Example 2.2.8. Compute 141513 (mod 2537) by using the method
of repeated squaring.
Solution. We have
141513 = 1415 · ((1415)2 )6 = 1415 · (2002225)6 ≡ 1415 · 5326
= 1415 · (5322 )3 = 1415 · 2830243 ≡ 1415 · 14173
= 1415 · 1417 · 14172 = 1415 · 1417 · 2007889
≡ 1415 · 1417 · 1122 ≡ 2182
The result is 2182 (mod 2537).

15


(mod 2537).


Graduation thesis

2.3

NGUYEN THI KIM CHI

Testing against small sets of bases

In the Miller-Rabin primality test, when the number n to be tested
is small, then smaller sets of potential witnesses are known to suffice.
For example, Pomerance, Selfridge and Wagstaff (see [3]) and Jaeschke
(see [1]) have verified that:
1. If n < 2, 047, it is enough to test a = 2;
2. If n < 1, 373, 653, it is enough to test a = 2 and 3;
3. If n < 9, 080, 191, it is enough to test a = 31 and 73;
4. If n < 25, 326, 001, it is enough to test a = 2, 3, and 5;
5. If n < 3, 215, 031, 751, it is enough to test a = 2, 3, 5, and 7;
6. If n < 4, 759, 123, 141, it is enough to test a = 2, 7, and 61;
7. If n < 1, 122, 004, 669, 633, it is enough to test a = 2, 13, 23, and
1662803;
8. If n < 2, 152, 302, 898, 747, it is enough to test a = 2, 3, 5, 7, and
11;
9. If n < 3, 474, 749, 660, 383, it is enough to test a = 2, 3, 5, 7, 11,
and 13;
10. If n < 341, 550, 071, 728, 321, it is enough to test a = 2, 3, 5, 7, 11, 13,
and 17.

Example 2.3.1. Testing 17 is a prime.

16


Graduation thesis

NGUYEN THI KIM CHI

Solution. Since n = 17 < 2047, we only need to carry the Miller-Rabin
primality test for the base a = 2.
Firstly, 17 = 24 · 1 + 1, so s = 4 and r = 1. Next, 21 ≡ 2 (mod 17),
1

2

22 ≡ 4 (mod 17), and 22 ≡ 16 ≡ −1 (mod 17). Thus 17 is a prime.

17


Conclusions
In this thesis, we have presented systematically the following topics

1. Recall the theory congruence;
2. Recall Fermat’s little theorem;
3. Recall the definition about the prime number;
4. State and apply the Miller - Rabin primality test;
5. Applying test against small sets of bases.
This is the first time I got acquainted with scientific research, despite

many attempts, I could not advoid may shortcomings. Therefore, I
look forward to receiving suggestions from teachers and readers.
I sincerely thanks the teachers and especially Dr. Tran Nam Trung
has been delicated to helping me in the past.

18


Bibliography
[1] G. Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation, 61 (204), 1993, 915-926.
[2] I. Niven, H.S. Zuckerman and H. L. Montgomery, An Introduction
to the Theory of Numbers, fifth edition, John Wiley & Sons, Inc.
[3] C. Pomerance, J. L. Selfridge and S. S. Wagstaff, The pseudoprimes to 25 · 109, Mathematics of Computation, 35 (151), 1980,
1003-1026.
[4] M.O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), 128-138.

19