Cryptography

and Network
Security
Eighth Edition
by William Stallings

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Chapter 2
Introduction to Number Theory

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Divisibility
• We say that a nonzero b divides a if a = mb for
some m, where a, b, and m are integers
• b divides a if there is no remainder on division

• The notation b | a is commonly used to mean b

divides a
• If b | a we say that b is a divisor of a
The positive divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24
13 | 182; - 5 | 30; 17 | 289; - 3 | 33; 17 | 0

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Properties of Divisibility
• If a | 1, then a = ±1

• If a | b and b | a, then a = ±b

• Any b ≠ 0 divides 0

• If a | b and b | c, then a | c
11 | 66 and 66 | 198 = 11 | 198

• If b | g and b | h, then b | (mg + nh) for arbitrary

integers m and n
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
 Properties of Divisibility
• To see this last point, note that:
• If b | g , then g is of the form g = b * g1 for some integer g1
• If b | h , then h is of the form h = b * h1 for some integer h1
• So:
• mg + nh = mbg1 + nbh1 = b * (mg1 + nh1 )
and therefore b divides mg + nh

b = 7; g = 14; h = 63; m = 3; n = 2
7 | 14 and 7 | 63.
To show 7 (3 * 14 + 2 * 63),
we have (3 * 14 + 2 * 63) = 7(3 * 2 + 2 * 9),
and it is obvious that 7 | (7(3 * 2 + 2 * 9)).

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Division Algorithm

• 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 that obey the following
relationship:

a = qn + r 0 ≤ r < n; q = [a/n]

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
 • One of the basic
techniques of number
Euclidean theory

Algorithm
• Procedure for
determining the greatest
common divisor of two
positive integers

• Two integers are

relatively prime if their
only common positive
integer factor is 1

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Greatest Common Divisor
(GCD)
• The greatest common divisor of a and b is the largest
integer that divides both a and b
• We can use the notation gcd(a,b) to mean the greatest
common divisor of a and b
• We also define gcd(0,0) = 0

• Positive integer c is said to be the gcd of a and b if:

• c is a divisor of a and b
• Any divisor of a and b is a divisor of c

• An equivalent definition is:

gcd(a,b) = max[k, such that k | a and k | b]

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
 GCD
• Because we require that the greatest common divisor be
positive, gcd(a,b) = gcd(a,-b) = gcd(-a,b) = gcd(-a,-b)
• In general, gcd(a,b) = gcd(| a |, | b |)
gcd(60, 24) = gcd(60, - 24) = 12

• Also, because all nonzero integers divide 0, we have gcd(a,0) =

|a|
• We stated that two integers a and b are relatively prime if their
only common positive integer factor is 1; this is equivalent to
8saying
and 15 are relatively
that a and prime
b are because theprime
relatively positiveifdivisors
gcd(a,b)of 8=are
1 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.
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
 Table 2.1
Euclidean Algorithm Example

(This table can be found on page 30 in the textbook)

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
 Modular Arithmetic
• The modulus
• If a is an integer and n is a positive integer, we
define a mod n to be the remainder when a is
divided by n; the integer n is called the modulus
• Thus, for any integer a:
a = qn + r 0 ≤ r < n; q = [a/ n]
a = [a/ n] * n + ( a mod n)

11 mod 7 = 4; - 11 mod 7 = 3

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Modular Arithmetic

• Congruent modulo n
• Two integers a and b are said to be congruent
modulo n if (a mod n) = (b mod n)
• This is written as a = b(mod n)2
• Note that if a = 0(mod n), then n | a

73 = 4 (mod 23); 21 = - 9 (mod 10)

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Properties of Congruences
• Congruences have the following properties:

1. a = b (mod n) if n (a – b)

2. a = b (mod n) implies b = a (mod n)

3. a = b (mod n) and b = c (mod n) imply a = c (mod n)

• To demonstrate the first point, if n (a - b), then (a - b) = kn
for some k
• So we can write a = b + kn
• Therefore, (a mod n) = (remainder when b + kn is divided by
n) = 23
(remainder
= 8 (mod when b is divided
5) because 23 - 8 =by
15n)
= =5(b
* 3mod n)
- 11 = 5 (mod 8) because - 11 - 5 = - 16 = 8 * (- 2)
81 = 0 (mod 27) because 81 - 0 = 81 = 27 * 3
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
 Modular Arithmetic
• Modular arithmetic exhibits the following properties:
1. [(a mod n) + (b mod n)] mod n = (a + b) mod n

2. [(a mod n) - (b mod n)] mod n = (a - b) mod n

3. [(a mod n) * (b mod n)] mod n = (a * b) mod n

• We demonstrate the first property:
• Define (a mod n) = ra and (b mod n) = rb. Then we can write a =
ra + jn for some integer j and b = rb + kn for some integer k
• Then:
(a + b) mod n = (ra + jn + rb + kn) mod n
= (ra + rb + (k + j)n) mod n
= (ra + rb) mod n
= [(a mod n) + (b mod n)] mod n
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
 Remaining Properties:
• Examples of the three remaining properties:

11 mod 8 = 3; 15 mod 8 = 7
[(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2
(11 + 15) mod 8 = 26 mod 8 = 2
[(11 mod 8) - (15 mod 8)] mod 8 = - 4 mod 8 = 4
(11 - 15) mod 8 = - 4 mod 8 = 4
[(11 mod 8) * (15 mod 8)] mod 8 = 21 mod 8 = 5
(11 * 15) mod 8 = 165 mod 8 = 5

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Table 2.2(a)
Arithmetic Modulo 8

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

(This table can be found on page 33 in the textbook)
 Table 2.2(b)
Multiplication Modulo 8

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

(This table can be found on page 33 in the textbook)
 Table 2.2(c)

Additive
and
Multiplicative
Inverse
Modulo 8
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
(This table can be found on page 33 in the textbook)
 Table 2.3
Properties of Modular Arithmetic for Integers in Z n

(This table can be found on page 34 in the textbook)

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
 Table 2.4
Extended Euclidean Algorithm Example

Result: d = 1; x = –111; y = 355

(This table can be found on page 39 in the textbook)

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
 Prime Numbers
• Prime numbers only have divisors of 1 and itself
• They cannot be written as a product of other numbers

• Prime numbers are central to number theory

• Any integer a > 1 can be factored in a unique way as

a = p1 a1 * p2 a2 * . . . * pp1 a1

where p1 < p2 < . . . < pt are prime numbers and where

each ai is a positive integer

• This is known as the fundamental theorem of arithmetic

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Table 2.5
Primes Under 2000

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved. (This table can be found on page 40 in the textbook)
 Fermat's Theorem
• States the following:
• If p is prime and a is a positive integer not
divisible by p then

ap-1 = 1 (mod p)
• An alternate form is:
• If p is prime and a is a positive integer then

ap = a (mod p)

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Table 2.6
Some Values of Euler’s Totient Function ø(n)

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved. (This table can be found on page 44 in the textbook)
 Euler's Theorem

• States that for every a and n that are relatively

prime:

aø(n) = 1(mod n)
• An alternative form is:

aø(n)+1 = a(mod n)

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Miller-Rabin Algorithm
• Typically used to test a large number for primality

• Algorithm is:

TEST (n)
• Find integers k, q, with k > 0, q odd, so that (n – 1)=2kq ;
1.
• Select a random integer a, 1 < a < n – 1 ;
2.
• if aq mod n = 1 then return (“inconclusive") ;
3.
• for j = 0 to k – 1 do
4.
• if (a2jq mod n = n – 1) then return (“inconclusive") ;
5.
• return (“composite") ;
6.

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Deterministic Primality Algorithm
• Prior to 2002 there was no known method of
efficiently proving the primality of very large
numbers
• All of the algorithms in use produced a probabilistic
result
• In 2002 Agrawal, Kayal, and Saxena developed an
algorithm that efficiently determines whether a
given large number is prime
• Known as the AKS algorithm
• Does not appear to be as efficient as the
Miller-Rabin algorithm
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.
 Chinese Remainder Theorem (CRT)
• Believed to have been discovered by the Chinese mathematician
Sun-Tsu in around 100 A.D.
• One of the most useful results of number theory

• Says it is possible to reconstruct integers in a certain range from

their residues modulo a set of pairwise relatively prime moduli
• Can be stated in several ways

Provides a way to manipulate (potentially very large)

numbers mod M in terms of tuples of smaller numbers
• This can be useful when M is 150 digits or more
• However, it is necessary to know beforehand the
factorization of M

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

 Table 2.7
Powers of Integers, Modulo 19

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved. (This table can be found on page 53 in the textbook)
 Table 2.8
Tables of Discrete Logarithms, Modulo 19

© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

(This table can be found on page 56 in the textbook)
 Summary
• Understand the concept of
divisibility and the division • Understand Fermat’s theorem
algorithm
• Understand Euler’s theorem
• Understand how to use the
Euclidean algorithm to find the • Define Euler’s totient function
greatest common divisor
• Make a presentation on the
• Present an overview of the topic of testing for primality
concepts of modular arithmetic
• Explain the Chinese remainder
• Explain the operation of the theorem
extended Euclidean algorithm
• Define discrete logarithms
• Discuss key concepts relating to
prime numbers
© 2020 Pearson Education, Inc., Hoboken, NJ. All rights reserved.