Chapter 2

Mathematics of
Cryptography
Part I: Modular Arithmetic, Congruence,
and Matrices

2.1 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 In mathematics, the greatest common divisor (GCD) of two or
more integers, which are not all zero, is the largest positive integer
that divides each of the integers. For two integers x, y, the greatest

common divisor of x and y is denoted .

For example, the GCD of 8 and 12 is 4, that is,

In the name "greatest common divisor", the adjective "greatest" may be
replaced by "highest", and the word "divisor" may be replaced by "factor",
so that other names include highest common factor (hcf), etc.
Historically, other names for the same concept have included greatest
common measure

2.2
 What is the GCD? (Definition)

The GCD (for greater common divisor) of two integers is the largest natural integer is
a divisor of these two integers.

How to calculate the GCD? (Algorithm)

GCD Method 1: list divisors of each number and find the greatest common divisor.
Example: GCD of the numbers 10 and 12.

10 has for divisors' list: 1,2,5,10

12 has for divisors' list: 1,2,3,4,6,12

The greatest common divisor (of these lists) is 2 (The largest number in all lists).

So, GCD(10,12) = 2

2.3
 The Euclidean algorithm is a way to find the greatest common divisor
of two positive integers. GCD of two numbers is the largest number
that divides both of them. A simple way to find GCD is to factorize
both numbers and multiply common prime factors.

2.4
 GCD Method 2: use Euclidean algorithm (prefered method for calculators)

Step 1. Make an euclidean division of the largest of the 2 numbers A by the

other one B, to find a dividend D and a remainder R. Keep the numbers B and R.

Step 2. Repeat step 1 (with numbers kept, B becomes the new A and R becomes
the new B) until the remainder is zero.

Step 3. GCD of A and B is equal to the last non zero remainder.

Example: A=12 and B=10, and (step 1) compute A/B = 12/10 = 1 remainder
R=2.

(step 2) 10/2 = 5 remainder 0, the remainder is zero.

The last remainder not null is 2, so GCD(10, 12) = 2.

2.5
 Divisibility in numbers
Division algorithm for integers

2.6
 Divisbility

If a is not zero and we let r = 0 in the division relation,

we get

a=q×n

If the remainder is zero,

If the remainder is not zero,

2.7
 Note

Fact 1: The integer 1 has only one

divisor, itself.

Fact 2: Any positive integer has at least

two divisors, 1 and itself (but it
can have more).

2.8
 Figure 2.6 Common divisors of two integers

2.9
 Note Greatest Common Divisor

The greatest common divisor of two

positive integers is the largest integer
that can divide both integers.

Note Euclidean Algorithm

Fact 1: gcd (a, 0) = a

Fact 2: gcd (a, b) = gcd (b, r), where r is
the remainder of dividing a by b
2.10
 Figure 2.7 Euclidean Algorithm

Note

When gcd (a, b) = 1, we say that a and b

are relatively prime.
2.11
 Note

When gcd (a, b) = 1, we say that a and b

are relatively prime.

2.12
 Example 2.7
Find the greatest common divisor of 2740 and 1760.
Solution
We have gcd (2740, 1760) = 20.

2.13
 Example 2.8
Find the greatest common divisor of 25 and 60.

Solution
We have gcd (25, 65) = 5.

2.14
 Extended Euclidean Algorithm
Given two integers a and b, we often need to find other two
integers, s and t, such that

The extended Euclidean algorithm can calculate the gcd ( a, b)

and at the same time calculate the value of s and t.

2.15
 Figure 2.8.a Extended Euclidean algorithm, part a

2.16
 Figure 2.8.b Extended Euclidean algorithm, part b

2.17
 Example 2.9

Given a = 161 and b = 28, find gcd (a, b) and the values of s
and t.

Solution
We get gcd (161, 28) = 7, s = −1 and t = 6.

2.18
 Example 2.10
Given a = 17 and b = 0, find gcd (a, b) and the values of s
and t.

Solution
We get gcd (17, 0) = 17, s = 1, and t = 0.

2.19
 Example 2.11

Given a = 0 and b = 45, find gcd (a, b) and the values of s

and t.

Solution
We get gcd (0, 45) = 45, s = 0, and t = 1.

2.20
 2-2 MODULAR ARITHMETIC

The division relationship (a = q × n + r) discussed in

the previous section has two inputs (a and n) and two
outputs (q and r). In modular arithmetic, we are
interested in only one of the outputs, the remainder r.

Topics discussed in this section:

2.2.1 Modular Operator
2.2.2 Set of Residues
2.2.3 Congruence
2.2.4 Operations in Zn
2.2.5 Addition and Multiplication Tables
2.2.6 Different Sets
2.21
 2.2.1 Modulo Operator

The modulo operator is shown as mod. The second input

(n) is called the modulus. The output r is called the
residue.
Figure 2.9 Division algorithm and modulo operator

2.22
 2.2.2 Set of Residues

The modulo operation creates a set, which in modular

arithmetic is referred to as the set of least residues
modulo n, or Zn.

Figure 2.10 Some Zn sets

2.23
 2.2.3 Congruence

To show that two integers are congruent, we use the

congruence operator ( ≡ ). For example, we write:

2.24
 2.2.3 Continued
Figure 2.11 Concept of congruence

2.25
 2.2.3 Continued
Residue Classes
A residue class [a] or [a]n is the set of integers congruent
modulo n.

2.26
 2.2.3 Continued
Figure 2.12 Comparison of Z and Zn using graphs

2.27
 2.2.4 Operation in Zn

The three binary operations that we discussed for the set

Z can also be defined for the set Zn. The result may need
to be mapped to Zn using the mod operator.
Figure 2.13 Binary operations in Zn

2.28
 2.2.4 Continued
Example 2.16
Perform the following operations (the inputs come from Zn):
a. Add 7 to 14 in Z15.
b. Subtract 11 from 7 in Z13.
c. Multiply 11 by 7 in Z20.

Solution

2.29
 2.2.4 Continued
Example 2.17
Perform the following operations (the inputs come from
either Z or Zn):
a. Add 17 to 27 in Z14.
b. Subtract 43 from 12 in Z13.
c. Multiply 123 by −10 in Z19.

Solution

2.30
 2.2.4 Continued
Properties

2.31
 2.2.4 Continued
Figure 2.14 Properties of mode operator

2.32
 2.2.4 Continued
Example 2.18

The following shows the application of the above properties:

1. (1,723,345 + 2,124,945) mod 11 = (8 + 9) mod 11 = 6

2. (1,723,345 − 2,124,945) mod 16 = (8 − 9) mod 11 = 10

3. (1,723,345 × 2,124,945) mod 16 = (8 × 9) mod 11 = 6

2.33
 2.2.4 Continued
Example 2.19

In arithmetic, we often need to find the remainder of powers

of 10 when divided by an integer.

2.34
 2.2.4 Continued
Example 2.20

We have been told in arithmetic that the remainder of an

integer divided by 3 is the same as the remainder of the sum
of its decimal digits. We write an integer as the sum of its
digits multiplied by the powers of 10.

2.35
 2.2.5 Inverses

When we are working in modular arithmetic, we often need

to find the inverse of a number relative to an operation. We
are normally looking for an additive inverse (relative to an
addition operation) or a multiplicative inverse (relative to a
multiplication operation).

2.36
 2.2.5 Continue
Additive Inverse

In Zn, two numbers a and b are additive inverses of each

other if

Note

In modular arithmetic, each integer has

an additive inverse. The sum of an
integer and its additive inverse is
congruent to 0 modulo n.
2.37
 2.2.5 Continued
Example 2.21

Find all additive inverse pairs in Z10.

Solution
The six pairs of additive inverses are (0, 0), (1, 9), (2, 8), (3, 7),
(4, 6), and (5, 5).

2.38
 2.2.5 Continue
Multiplicative Inverse
In Zn, two numbers a and b are the multiplicative inverse of
each other if

Note

In modular arithmetic, an integer may or

may not have a multiplicative inverse.
When it does, the product of the integer
and its multiplicative inverse is
congruent to 1 modulo n.

2.39
 2.2.5 Continued

Example 2.22
Find the multiplicative inverse of 8 in Z10.
Solution
There is no multiplicative inverse because gcd (10, 8) = 2 ≠ 1.
In other words, we cannot find any number between 0 and 9
such that when multiplied by 8, the result is congruent to 1.
Example 2.23
Find all multiplicative inverses in Z10.

Solution
There are only three pairs: (1, 1), (3, 7) and (9, 9). The
numbers 0, 2, 4, 5, 6, and 8 do not have a multiplicative
inverse.
2.40
 2.2.5 Continued
Example 2.24
Find all multiplicative inverse pairs in Z11.
Solution
We have seven pairs: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8), (9, 9),
and (10, 10).

We have six pairs: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8), and (10,
10).

2.41
 2.2.5 Continued

Note

The extended Euclidean algorithm finds

the multiplicative inverses of b in Zn
when n and b are given and
gcd (n, b) = 1.
The multiplicative inverse of b is the
value of t after being mapped to Zn.

2.42
 2.2.5 Continued
Figure 2.15 Using extended Euclidean algorithm to
find multiplicative inverse

2.43
 2.2.5 Continued
Example 2.25
Find the multiplicative inverse of 11 in Z26.
Solution

The gcd (26, 11) is 1; the inverse of 11 is 7 or 19.

2.44
 2.2.5 Continued
Example 2.26
Find the multiplicative inverse of 23 in Z100.
Solution

The gcd (100, 23) is 1; the inverse of 23 is 13 or 87.

2.45
 2.2.5 Continued
Example 2.27
Find the inverse of 12 in Z26.
Solution

The gcd (26, 12) is 2; the inverse does not exist.

2.46
 2.2.6 Addition and Multiplication Tables
Figure 2.16 Addition and multiplication table for Z10

2.47