Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
CSE-103
Lecture-07: Number Theory
IIT, JU
Integer Arithmetic: The Set of Integers
In integer arithmetic, we use a set and a few operations.
We are already familiar with this set and the corresponding
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
operations, but they are reviewed here to create a background for
modular arithmetic.
The set of integers, denoted by Z, contains all integral numbers (with
no fraction) from negative infinity to positive infinity.
Figure below shows the set of integers.
Figure: The set of integers
IIT, JU
Binary Operations
❖ A binary operation takes two inputs (e.g. a and b) and creates one
output (e.g. c).
❖ In cryptography, we are interested in three binary operations applied
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
to the set of integers: addition, subtraction and multiplication.
Figure: Three binary operations for the set of integers
IIT, JU
Binary Operations
❖ The following examples shows the results of the three binary
operations on two integers.
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
❖ Because each input can be either positive or negative, we can
have four cases for each operation.
IIT, JU
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
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
a=q×n+r
Where,
❖ a dividend
❖ n divisor
❖ q quotient
❖ r remainder
Note:
Division is not a binary operation, because it produces two output
instead of one (q and r). Instead, we can call it division relation.
IIT, JU
Integer Division
Example:
Assume that a = 255 and n = 11. We can find q = 23 and r = 2
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
using the division algorithm.
Figure: Finding the quotient and the remainder
IIT, JU
Integer Division
When we use the above division relationship in cryptography, we
impose two restrictions:
1. The divisor be a positive integer (i.e. n>0)
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
2. The remainder be a non-negative integer (i.e. r>=0)
Figure: Division algorithm for integers
IIT, JU
Integer Division
Example:
When we use a computer or a calculator, r and q are negative
when a is negative.
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
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.
n r r=n+r
q q = q-1
IIT, JU
Divisibility
Division relation is: a=q×n+r
Where
a dividend
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
n divisor
q quotient
r remainder
If a is not zero and we let r = 0 in the division relation, we get:
a=q×n
We then say that
▪ n divides a
▪ or, n is a divisor of a
▪ or, a is divisible by n
Therefore, when a is divisible by If a is not divisible by n (i.e. if r
n and we are not interested in is not zero), then we can write
the value of q, we can write the the above relation as
above relation as a|n
IIT, JU
Divisibility
Example :
a. The integer 4 divides the integer 32 because 32 = 8 × 4. We
show this as
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
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
Example:
IIT, JU
GCD: Greatest Common Divisor
A positive integer can have more than one divisor. For example, the
integer 32 has six divisors: 1, 2, 4, 8, 16, 32.
We can mention two interesting facts about divisors of positive
integers:
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
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).
The greatest common divisor (GCD) of two positive integers is the
largest integer that can divide both integers.
GCD is often needed in cryptography.
Two positive integers may have many common divisors, but only one is
the greatest of them.
For example, the common divisors of 12 and 140 are: 1, 2, and 4.
However, the greatest common divisor is 4.
IIT, JU
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
GCD: Greatest Common Divisor
Figure: Common divisors of two integers
IIT, JU
GCD Using Euclidean Algorithm
Finding the GCD of two positive integers by listing all common
divisors is not practical when the two integers are large.
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
More than 2000 years ago, a mathematician named Euclid
developed an algorithm that can find the GCD of two large positive
integers.
The Euclidian algorithm is based on the two facts:
Fact 1: When 2nd integer is zero, then gcd (a, 0) = a
Example: gcd(5, 0) = 5
Fact 2: When both integer is positive, then gcd (a, b) = gcd (b, r),
where r is the remainder of dividing a by b (here the value
of first and second integer is changed until the second
integer becomes zero.
Example:
Gcd(36, 10) = gcd(10, 6) = gcd(6, 4) = gcd(4,2) = gcd(2, 0) = 2
IIT, JU
GCD Using Euclidean Algorithm
Figure below shows how we use Fact 1 and Fact 2 to calculate gcd (a, b)
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
Figure: Euclidean Algorithm
Note:
When gcd (a, b) = 1, we say that a and b are relatively prime or they are
coprime.
IIT, JU
GCD Using Euclidean Algorithm
Example:
Find the greatest common divisor of 2740 and 1760.
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
Solution:
We have gcd (2740, 1760) = 20.
IIT, JU
GCD Using Euclidean Algorithm
Example:
Find the greatest common divisor of 25 and 60.
Solution:
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
We have gcd (25, 60) = 5.
Note:
The above example shows that it does not matter if the first number is
smaller than the second number. We immediately get our correct
ordering gcd(60, 25).
IIT, JU
Modular Arithmetic
Given any positive integer n and any nonnegative integer a, if we
divide a by n, we get an integer quotient q and an integer
remainder r such that a = q × n + r.
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
This division relation 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. In other words, we want to know what
is the value of r when we divide a by n. This implies that, using
modular arithmetic, we can change the division relation into a
binary operator (called modulo operator) with two inputs a and n
and one output r.
Several important cryptosystems make use of modular
arithmetic.
IIT, JU
Modular Arithmetic
The modulo operator is shown as mod. The second input (n) is
called the modulus. The output r is called the residue.
Figure below shows the division relation compared with the modulo
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
operator.
Figure: Division relation Vs. modulo operator
In the figure we see that the modulo operator (mod) takes an
integer (a) from the set of integers (Z) and a positive modulus
(n). The operator creates a non-negative residue (r) where 0 <=
r <= n-1. We can say that:
a mod n = r
IIT, JU
Modular Arithmetic
Calculation of a mod n:
There are three cases:
Case-1: When both of a and n is positive integer where a<n:
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
In this case, we add as many multiples of n with a as necessary
to get a greater than n. Then divide a by n to get the remainder
r. The result will be in the range 0 to n-1.
For example, 2 mod 7 = 9 mod 7 = 2.
Case-2: When both of a and n is positive integer where a>=n:
In this case, just divide a by n to get the remainder r. The result
will be in the range 0 to n-1.
For example, 9 mod 7 = 2.
Case-3: When a is negative and n is positive integer:
In this case, we add as many multiples of n with a as necessary to
get a positive and greater than n. Then divide a by n to get the
remainder r. The result will be in the range 0 to n-1. The process
is known as modulo reduction.
For example, -12 mod 7 = -5 mod 7 = 2 mod 7 = 9 mod 7
IIT, JU
Modular Arithmetic
Example:
Find the result of the following operations:
a. 27 mod 5 b. 36 mod 12
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
c. −18 mod 14 d. −7 mod 10
Solution:
a. Dividing 27 by 5 results in r = 2. Therefore 27 mod 5 = 2
b. Dividing 36 by 12 results in r = 0. Therefore 36 mod 12 = 0
c. Dividing −18 by 14 results in r = −4. After adding the modulus
(14) with the result to make it non-negative, we have r = -4 +
14 = 10. Therefore -18 mod 14 = 10
d. Dividing −7 by 10 results in r = −7. After adding the modulus
(10) with the result to make it non-negative, we have r = -7 +
10 = 3. Therefore –7 mod 10 = 3
IIT, JU
Zn: Set of Residues
The result of a mod n is always an integer between 0 and n-1.
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
Therefore, the modulo operation creates a set, which in modular
arithmetic is referred to as the set of least residues modulo n, or Zn.
Figure below shows the set of residues Z n and three instances of the
set of residues Z2, Z6, Z11.
Figure: Some Zn sets
IIT, JU
Congruence
The result of 2 mod 10 = 2, 12 mod 10 = 2, 22 mod 10 = 2, 32 mod
10 = 2 and so on.
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
In modular arithmetic, integers like 2, 12, 22 and 32 are called
congruent mod 10.
To show that two integers are congruent, we use the congruence
operator ( ≡ ). For example, we write:
IIT, JU
Congruence
Figure below shows the idea of congruence.
Prepared by: K M Akkas Ali, Associate Professor, IIT, Jahangirnagar University, Dhaka
Figure 2.11 Concept of congruence
IIT, JU