2

Information Security System
(CSPC-307)
Mathematics of Cryptography 3e
Modular Arithmetic, Congruence,
and Matrices
Dr Samayveer Singh
Assistant Professor
Department of Computer Science & Engineering
National Institute Technology Jalandhar, Punjab, India
[email protected]
Copyright © 2015 by McGraw Hill Education (India) Private Limited. All rights reserved.
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.
1.1 Set of Integers

1.2 Binary Operations
1.3 Integer Division
1.4 Divisibility
1.5 Linear Diophantine Equations
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 1).
Figure 1 The set of integers
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 Three binary operations for the set of integers
1.2 Continued
Example 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.
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
1.3 Continued
Example 2
Assume that a = 255 and n = 11. We can find q = 23 and R = 2
using the division algorithm.
Figure 3 Example 2, finding the quotient and the remainder
1.3 Continued
Figure 4 Division algorithm for integers
1.3 Continued
Example 3
When we use a computer or a calculator, r and q are

negative when a is negative. How can we apply the
restriction that r needs to be positive? The solution is
simple, we decrement the value of q by 1 and we add the
value of n to r to make it positive.
1.3 Continued
Figure 5 Graph of division alogorithm
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,
1.4 Continued
Example 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
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
1.4 Continued
Example 5
1.4 Continued
Example 6
1.4 Continued
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).
1.4 Continued
Figure 6 Common divisors of two integers
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
1.4 Continued
Figure 7 Euclidean Algorithm

Note
When gcd (a, b) = 1, we say that a and b are relatively
prime.
1.4 Continued
Note
When gcd (a, b) = 1, we say that a and b

are relatively prime.
1.4 Continued
Example 7
Find the greatest common divisor of 2740 and 1760.
Solution
We have gcd (2740, 1760) = 20.
1.4 Continued
Example 8
Find the greatest common divisor of 25 and 60.
Solution
We have gcd (25, 65) = 5.
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.
1.4 Continued
Figure 8.a Extended Euclidean algorithm, part a
1.4 Continued
Figure 8.b Extended Euclidean algorithm, part b
1.4 Continued
Example 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.
1.4 Continued
Example 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.
1.4 Continued
Example 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.
1.4 Continued
Linear Diophantine Equation
Note
A linear Diophantine equation of two

variables is ax + by = c.
1.4 Continued
Linear Diophantine Equation
Note
Particular solution:
x0 = (c/d)s and y0 = (c/d)t
Note
General solutions:
x = x0 + k (b/d) and y = y0 − k(a/d)
where k is an integer
1.4 Continued
Example 12
Find the particular and general solutions to the equation

21x + 14y = 35.
Solution
1.4 Continued
Example 13
For example, imagine we want to cash a $100 check and

get some $20 and some $5 bills. We have many choices,
which we can find by solving the corresponding
Diophantine equation 20x + 5y = 100. Since d = gcd (20, 5)
= 5 and 5 | 100, the equation has an infinite number of
solutions, but only a few of them are acceptable in this
case The general solutions
with x and y nonnegative are
(0, 20), (1, 16), (2, 12), (3, 8), (4, 4), (5, 0).
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.
2.1 Modular Operator
2.2 Set of Residues
2.3 Congruence
2.4 Operations in Zn
2.5 Addition and Multiplication Tables
2.6 Different Sets
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 9 Division algorithm and modulo operator
1.4 Continued
Example 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. After adding the
modulus r = 10
d. Dividing −7 by 10 results in r = −7. After adding the
modulus to −7, r = 3.
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 10 Some Zn sets
2.3 Congruence
To show that two integers are congruent, we use the
congruence operator ( ≡ ). For example, we write:
2.3 Continued
Figure 11 Concept of congruence
2.3 Continued
Residue Classes
A residue class [a] or [a]n is the set of integers

congruent modulo n.
2.3 Continued
Figure 12 Comparison of Z and Zn using graphs
2.3 Continued
Example 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.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 13 Binary operations in Zn
2.4 Continued
Example 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.4 Continued
Example 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.4 Continued
Properties
2.4 Continued
Figure 14 Properties of mode operator
2.4 Continued
Example 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.4 Continued
Example 19
In arithmetic, we often need to find the remainder of

powers of 10 when divided by an integer.
2.4 Continued
Example 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.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.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.5 Continued
Example 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.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.5 Continued
Example 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 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.5 Continued
Example 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).
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.5 Continued
Figure 15 Using extended Euclidean algorithm to

find multiplicative inverse
2.5 Continued
Example 25
Solution
The gcd (26, 11) is 1; the inverse of 11 is -7 or 19.
2.5 Continued
Example 26
Solution
The gcd (100, 23) is 1; the inverse of 23 is -13 or 87.
2.5 Continued
Example 27
Find the inverse of 12 in Z26.

Solution
The gcd (26, 12) is 2; the inverse does not exist.
2.6 Addition and Multiplication Tables
Figure 16 Addition and multiplication table for Z10
2.7 Different Sets
Figure 17 Some Zn and Zn* sets
Note
We need to use Zn when additive

inverses are needed; we need to use Zn*
when multiplicative inverses are needed.
2.8 Two More Sets
Cryptography often uses two more sets: Zp and

Zp*. The modulus in these two sets is a prime
number.
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.
3.1 Definitions
3.2 Operations and Relations
3.3 Determinants
3.4 Residue Matrices
3.1 Definition
Figure 18 A matrix of size l  m
3.1 Continued
Figure 19 Examples of matrices
3.2 Operations and Relations
Example 28
Figure 20 shows an example of addition and

subtraction.
Figure 20 Addition and subtraction of matrices
3.2 Continued
Example 29
Figure 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 21 Multiplication of a row matrix by a column matrix
3.2 Continued
Example 30
Figure 22 shows the product of a 2 × 3 matrix by

a 3 × 4 matrix. The result is a 2 × 4 matrix.
Figure 22 Multiplication of a 2 × 3 matrix by a 3 × 4 matrix
3.2 Continued
Example 31
Figure 23 shows an example of scalar multiplication.
Figure 23 Scalar multiplication
3.3 Determinant
The determinant of a square matrix A of size m ×
m denoted as det (A) is a scalar calculated
recursively as shown below:
Note
The determinant is defined only for a

square matrix.
3.3 Continued
Example 32
Figure 24 shows how we can calculate the

determinant of a 2 × 2 matrix based on the
determinant of a 1 × 1 matrix.
Figure 24 Calculating the determinant of a 2  2 matrix
3.3 Continued
Example 33
Figure 25 shows the calculation of the

determinant of a 3 × 3 matrix.
Figure 25 Calculating the determinant of a 3  3 matrix
3.4 Inverses
Note
Multiplicative inverses are only defined

for square matrices.
3.5 Residue Matrices
Cryptography uses residue matrices: matrices

where all elements are in Zn. A residue matrix has
a multiplicative inverse if gcd (det(A), n) = 1.
Example 34
Figure 26 A residue matrix and its multiplicative inverse
4 LINEAR CONGRUENCE
Cryptography often involves solving an equation

or a set of equations of one or more variables with
coefficient in Zn. This section shows how to solve
equations when the power of each variable is 1
(linear equation).
4.1 Single-Variable Linear Equations

4.2 Set of Linear Equations
Equations of the form ax ≡ b (mod n ) might have

no solution or a limited number of solutions.
4.1 Continued
Example 35
Solve the equation 10 x ≡ 2(mod 15).
Solution
First we find the gcd (10 and 15) = 5. Since 5 does not divide
2, we have no solution.
Example 36
Solve the equation 14 x ≡ 12 (mod 18).
Solution
4.1 Continued
Example 37
Solve the equation 3x + 4 ≡ 6 (mod 13).
Solution
First we change the equation to the form ax ≡ b (mod n).
We add −4 (the additive inverse of 4) to both sides, which
give 3x ≡ 2 (mod 13). Because gcd (3, 13) = 1, the equation
has only one solution, which is x0 = (2 × 3−1) mod 13 = 18
mod 13 = 5. We can see that the answer satisfies the
original equation: 3 × 5 + 4 ≡ 6 (mod 13).
We can also solve a set of linear equations with
the same modulus if the matrix formed from the
coefficients of the variables is invertible.
Figure 27 Set of linear equations

4.2 Continued
Example 38
Solve the set of following three equations:
Solution
The result is x ≡ 15 (mod 16), y ≡ 4 (mod 16), and z ≡ 14 (mod

16). We can check the answer by inserting these values into the
equations.

2

Uploaded by

Copyright:

Available Formats

2

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

2

Uploaded by

Copyright:

Available Formats

Information Security System

In integer arithmetic, we use a set and a few

1.1 Set of Integers

The set of integers, denoted by Z, contains all

Figure 1 The set of integers

Figure 2 Three binary operations for the set of integers

The following shows the results of the three binary

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

Figure 3 Example 2, finding the quotient and the remainder

Figure 4 Division algorithm for integers

When we use a computer or a calculator, r and q are

Figure 5 Graph of division alogorithm

If the remainder is zero,

If the remainder is not zero,

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

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

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

Fact 1: The integer 1 has only one divisor,

Fact 2: Any positive integer has at least

Figure 6 Common divisors of two integers

Note Greatest Common Divisor

The greatest common divisor of two

Note Euclidean Algorithm

Fact 1: gcd (a, 0) = a

Figure 7 Euclidean Algorithm

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

Given two integers a and b, we often need to find other

The extended Euclidean algorithm can calculate the gcd (a,

Figure 8.a Extended Euclidean algorithm, part a

Figure 8.b Extended Euclidean algorithm, part b

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

A linear Diophantine equation of two

Find the particular and general solutions to the equation

For example, imagine we want to cash a $100 check and

Figure 9 Division algorithm and modulo operator

Find the result of the following operations:

The modulo operation creates a set, which in modular

Figure 10 Some Zn sets

Figure 11 Concept of congruence

A residue class [a] or [a]n is the set of integers

Figure 12 Comparison of Z and Zn using graphs

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

Figure 13 Binary operations in Zn

Perform the following operations (the inputs come from

Perform the following operations (the inputs come from

Figure 14 Properties of mode operator

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

In arithmetic, we often need to find the remainder of

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

In modular arithmetic, each integer has

Find all additive inverse pairs in Z10.

In modular arithmetic, an integer may or

Find the multiplicative inverse of 8 in Z10.

Find all multiplicative inverses in Z10.

Find all multiplicative inverse pairs in Z11.