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.
Chapter 2
Objectives
 To review integer arithmetic, concentrating on divisibility
and finding the greatest common divisor using the Euclidean
algorithm
 To understand how the extended Euclidean algorithm can be
used to solve linear Diophantine equations, to solve linear
congruent equations, and to find the multiplicative inverses
 To emphasize the importance of modular arithmetic and
the modulo operator, because they are extensively used in
cryptography
 To emphasize and review matrices and operations on residue
matrices that are extensively used in cryptography
 To solve a set of congruent equations using residue matrices
2.2
2-1 INTEGER ARITHMETIC

In integer arithmetic, we use a set and a few

operations. You are familiar with this set and the
corresponding operations, but they are reviewed here
to create a background for modular arithmetic.

Topics discussed in this section:

2.1.1 Set of Integers
2.1.2 Binary Operations
2.1.3 Integer Division
2.1.4 Divisibility
2.1.5 Linear Diophantine Equations

2.3
2.1.1 Set of Integers

The set of integers, denoted by Z, contains all integral

numbers (with no fraction) from negative infinity to
positive infinity (Figure 2.1).

Figure 2.1 The set of integers

2.4
2.1.2 Binary Operations
In cryptography, we are interested in three binary
operations applied to the set of integers. A binary
operation takes two inputs and creates one output.

Figure 2.2 Three binary operations for the set of integers

2.5
2.1.2 Continued
Example 2.1

The following shows the results of the three binary operations

on two integers. Because each input can be either positive or
negative, we can have four cases for each operation.

2.6
2.1.3 Integer Division

In integer arithmetic, if we divide a by n, we can get q

And r . The relationship between these four integers can
be shown as

a=q×n+r

2.7
2.1.3 Continued
Example 2.2
Assume that a = 255 and n = 11. We can find q = 23 and R = 2
using the division algorithm.

Figure 2.3 Example 2.2, finding the quotient and the remainder

2.8
2.1.3 Continued
Figure 2.4 Division algorithm for integers

a is called the dividend; q, the quotient; n, the divisor; and r, the

remainder.

2.9
2.1.4 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.10
2.1.4 Continued
Example 2.4

a. The integer 4 divides the integer 32 because 32 = 8 × 4.

We show this as

b. The number 8 does not divide the number 42 because

42 = 5 × 8 + 2. There is a remainder, the number 2, in the
equation. We show this as

2.11
2.1.4 Continued
Properties

Property 1: if a|1, then a = ±1.

Property 2: if a|b and b|a, then a = ±b.

Property 3: if a|b and b|c, then a|c.

Property 4: if a|b and a|c, then

a|(m × b + n × c), where m
and n are arbitrary integers

2.12
2.1.4 Continued
Example 2.5

2.13
2.1.4 Continued
Example 2.6

Here a=3 ,b=15, c=9 ; m=2,n=4;

=>3|(2X15+4X9)
=>3|3(2X5+4X3)
=>3|66.
2.14
2.1.4 Divisors

A positive integer can have more than one divisor. For

example, the integer 32 has six divisors: 1, 2, 4, 8, 16, and
32.

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.15
2.1.4 Continued (Greatest Common Divisor)

One integer often needed in cryptography is the greatest common divisor of

two positive integers.
Two positive integers may have many common divisors, but only one
greatest common divisor.
For example, the common divisors of 12 and 140 are 1, 2, and 4. However,
the greatest common divisor is 4

2.16
Figure 2.6 Common divisors of two integers
2.1.4 Continued

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.17
2.1.4 Continued

Note Euclidean Algorithm

Fact 1: gcd (a, 0) = a

The first fact tells us that if the second integer is
0, the greatest common divisor is the first one.

Fact 2: gcd (a, b) = gcd (b, r), where r is

the remainder of dividing a by b
The second fact allows us to change the value of
a, b until b becomes 0.

2.18
2.1.4 Continued
Note Euclidean Algorithm

Fact 2: example
gcd(36,10)=gcd(10,6)=gcd(6,4)=gcd(4,2)=gcd(2,0=2
)
gcd(36,10)=> 36=3×10+6
gcd(10,6)=> 10=1×6+4
gcd(6,4)=> 6=1×4+2
gcd(4,2)=> 4=2×2+0
gcd(2,0)=> 2

2.19
2.1.4 Continued
Figure 2.7 Euclidean Algorithm

2.20
2.1.4 Continued
Note

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

are relatively prime.

example-
8 and 15 are relatively prime because the positive divisors of 8 are 1, 2, 4,
and 8, and the positive divisors of 15 are 1, 3, 5, and 15. So 1 is the only
integer on both lists.

Question:
Find the greatest common divisor of 2740 and 1760?
Find the greatest common divisor of 25 and 60?

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

2.22
2.1.4 Continued
Example 2.8
Find the greatest common divisor of 25 and 60.

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

2.23
2.1.4 Continued
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.

S and t are cofft. Of Bezout’s identity.S

2.24
2.1.4 Continued
Figure 2.8.a Extended Euclidean algorithm, part a

2.25
2.1.4 Continued
Figure 2.8.b Extended Euclidean algorithm, part b

2.26
2.1.4 Continued
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.
s=s1-qs2
t=t1-qt2

2.27
2.1.4 Continued
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.28
2.1.4 Continued
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.29
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.33
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.34
2.1.4 Continued
Example 2.14
Find the result of the following operations:
a. 27 mod 5 b. 36 mod 12
c. −18 mod 14 d. −7 mod 10

Solution
a. Dividing 27 by 5 results in r = 2
b. Dividing 36 by 12 results in r = 0.
c. Dividing −18 by 14 results in r = −4. However, we need to add
the modulus (14) to make it nonnegative. We have r = −4 + 14 =
10. This means that −18 mod 14 = 10 After adding the modulus r
= 10
d. Dividing −7 by 10 results in r = −7. After adding the modulus
to −7, r = 3. This means that −7 mod 10 = 3.
35
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.
Note-
one set of integers (Z) but infinite instances of the set of
residues (Zn), one for each value of n
Figure 2.10 Some Zn sets

2.36
2.2.3 Congruence

To show that two integers are congruent, we use the

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

2.37
2.2.3 Continued
Figure 2.11 Concept of congruence

2.38
2.2.3 Continued
Example 2.15

We use modular arithmetic in our daily life; for example, we

use a clock to measure time. Our clock system uses modulo 12
arithmetic. However, instead of a 0 we use the number 12.

2.39
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.40
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.41
2.2.4 Continued
Properties

2.42
2.2.4 Continued
Figure 2.14 Properties of mode operator

2.43
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.44
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.45
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.46
2.2.5 Continued
Example 2.21

Find all additive inverse pairs in Z10.

Solution

In Zn, the additive inverse of a can be calculated as b = n − a.

For example, the additive inverse of 4 in Z10 is 10 − 4 = 6

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

2.47
1. Additive inverse of 144mod97

=144mod97
=47
Now, additive inverse of 47mod97
47+(-47) ≡0 mod97
97-47=50

=Additive inverse of 144mod97 is 50

2.Additive inverse of 123mod47

=29mod47
29+(-29) ≡0mod47
=47-29=18

=Additive inverse of 123mod47 is 18

2.48
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.49
multiplicative inverse of 26 mod 11
q a b r t1 t2 t
0 11 26 11 0 1 0
2 26 11 4 1 0 1
2 11 4 3 0 1 -2
1 4 3 1 1 -2 3
3 3 1 0 -2 3 -11
1 0 3

multiplicative inverse of 26 mod 11 is 3

2.50
multiplicative inverse of 3 mod 11

q a b r t1 t2 t
3 11 3 2 0 1 -3
1 3 2 1 1 -3 4
2 2 1 0 -3 4 -11
1 0 4 -11

multiplicative inverse of 3 mod 11 is 4

2.51
Questions on multiplicative inverse:

1.17mod29

2.27mod392

3.2021mod4032

4.9mod26
2.52
2-3 MATRICES

In cryptography we need to handle matrices. Although

this topic belongs to a special branch of algebra called
linear algebra, the following brief review of matrices is
necessary preparation for the study of cryptography.

Topics discussed in this section:

2.3.1 Definitions
2.3.2 Operations and Relations
2.3.3 Determinants
2.3.4 Residue Matrices

2.53
2.3.1 Definition

Figure 2.18 A matrix of size l  m

2.54
2.3.1 Continued

Figure 2.19 Examples of matrices

2.55
2.3.2 Operations and Relations
Example 2.28

Figure 2.20 shows an example of addition and

subtraction.

Figure 2.20 Addition and subtraction of matrices

2.56
2.3.2 Continued
Example 2. 29

Figure 2.21 shows the product of a row matrix (1 × 3)

by a column matrix (3 × 1). The result is a matrix of
size 1 × 1.

Figure 2.21 Multiplication of a row matrix by a column matrix

2.57