Number Theory

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.

a = qn + r

◼ The integer n is called the modulus. And r is also called

residue.

◼ In modular arithmetic we are only interested in the remainder

(or residue) after division by some modulus

11 August 2024 2
Modular Arithmetic

◼ 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.

◼ Ex. 11 mod 7 = 4; - 11 mod 7 = 3

◼ We "usually" want to find the positive remainder after dividing by the

modulus.
◼ For positive numbers, this is simply the normal remainder.
◼ For negative numbers we have to "overshoot" (ie find the next multiple
larger than the number) and "come back" (ie add a positive remainder to
get the number); rather than have a "negative remainder".

11 August 2024 3
Congruent modulo

11 August 2024 4
Congruent modulo

Modular Arithmetic Operations

◼ Modular arithmetic exhibits the following properties:

11 August 2024 5
Modular Arithmetic Operations

◼ Exponentiation is performed by repeated multiplication,

11 August 2024 6
Solve

◼ 913 mod 11

11 August 2024 7
Solve
◼ 6783 mod 115

11 August 2024 8
Solve
◼ 8364 mod 115

11 August 2024 9
Modular Arithmetic Operations
◼ Table provides an illustration of modular addition and
multiplication modulo 8.

◼ There is an additive inverse, or negative, to each integer in

modular arithmetic.

◼ The additive inverse or negative of an integer x is the integer

y such that (x+y) mod 8 =0.

◼ To find the additive inverse of an integer in the left-hand

column, scan across the corresponding row of the matrix to
find the value 0; the integer at the top of that column is the
additive inverse;
11 August 2024 10
Modular Arithmetic Operations

◼ Thus (2 + 6) mod 8 = 0
◼ So additive inverse of 2 is 6 in Z8

11 August 2024 11
Modular Arithmetic Operations
◼ In modular arithmetic mod 8,the multiplicative inverse of x is the
integer y such that (x × y) mod8 = 1 mod 8.

◼ To find the multiplicative inverse of an integer from the

multiplication table, scan across the matrix in the row for that
integer to find the value 1; the integer at the top of that column is the
multiplicative inverse.

◼ Thus (3 × 3) mod8 = 1

◼ Note that not all integers

mod 8 have a multiplicative
inverse;

11 August 2024 12
Properties of Modular Arithmetic

◼ We can write the following

◼ However, the following statement is true only with the

attached condition:

◼ Two integers are relatively prime if their only common

positive integer factor is 1.

11 August 2024 13
Polynomial Arithmetic

◼ Byte b7b6b5b4b3b2b1b0 will have the representation as

b(x) = b7x7 + b6x6+ b5x5+ b4x4 + b3x3 + b2x2 + b1x + b0
◼ Therefore, 01010111 would have the representation as
x6 + x4 + x2 + x + 1

◼ Ordinary Polynomial
Arithmetic

11 August 2024 14
Addition in Finite field GF(28)

◼ Addition in a finite field achieved by adding the coefficients for the corresponding
powers in the polynomials for the two elements

◼ Addition performed by EX-OR operation

❑ denoted as <F, > modulo 2

11 August 2024 15
Multiplication in Finite field

◼ Denoted by <F{0}, • > or < F{0},

◼ Mmultiplication in GF(28) corresponds to

❑ multiplication of polynomials modulo an irreducible polynomial of

degree 8

◼ A polynomial F(x) over a field F is called irreducible if and only if F(x)

cannot be expressed as a product of two polynomials, both over F, and
both of degree lower than that of F(x).

◼ for AES, the irreducible polynomial is m(x) = x8 + x4 + x3 + x + 1 (i.e.

{01}{1B} )

11 August 2024 16
Multiplication in Finite field

11 August 2024 17
Multiplication in Finite field
◼ Example
◼ Consider the two polynomial

In Hexadecimal notation

As AES uses arithmetic in the finite field GF (28). With the irreducible
polynomial m(x) = x8 + x4 + x3 + x + 1

11 August 2024 18
Multiplication in Finite field
◼ Dividing

11 August 2024 19
Polynomial Over GF(28)

11 August 2024 20
Prime Number

◼ An integer p > 1 is a prime number if and only if its only divisors

are 1 and itself.

◼ Ex. 2,3,5,7 are prime, 4,6,8,9,10 are not

◼ List of prime number less than 200 is:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79
83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163
167 173 179 181 191 193 197 199
◼ Prime Factorisation
◼ The prime factorisation of a number n is when its written as a
product of primes
❑ eg. 91=7x13 ; 3600=24x32x52

11 August 2024 21
Relative Prime Number

◼ Two numbers a, b are relatively prime if have no common

divisors apart from 1

◼ Ex. 8 & 15 are relatively prime

❑ since factors of 8 are 1,2,4,8 and of 15 are 1,3,5,15 and 1 is the
only common factor

11 August 2024 22
Euclid’s Algorithm

◼ It is a simple procedure for determining the greatest common

divisor of two positive integer.

◼ Greatest common divisor

◼ The positive integer c is said to be the greatest common

divisor of a and b if
❑ c is a divisor of a and of b;
❑ Any divisor of a and b is a divisor of c

◼ i.e gcd (a,b) = max [k, such that k/a and k/b]

11 August 2024 23
Euclid’s Algorithm

◼ The Euclidean algorithm can be based on the following theorem:

◼ For any nonnegative integer a and any positive integer b,

gcd(a, b) = gcd(b, a mod b)

◼ For Ex. gcd(55, 22) = gcd(22, 55 mod 22) = gcd(22, 11) = 11

◼ We can define the Euclidean algorithm concisely as the following

recursive function.
◼ Euclid(a,b)
if (b=0) then return a;
else return Euclid(b, a mod b);

11 August 2024 24
Euclid’s Algorithm

◼ Example of Euclidean algorithm to find gcd(1970,1066)

1970 = 1 x 1066 + 904 gcd(1066, 904)
1066 = 1 x 904 + 162 gcd(904, 162)
904 = 5 x 162 + 94 gcd(162, 94)
162 = 1 x 94 + 68 gcd(94, 68)
94 = 1 x 68 + 26 gcd(68, 26)
68 = 2 x 26 + 16 gcd(26, 16)
26 = 1 x 16 + 10 gcd(16, 10)
16 = 1 x 10 + 6 gcd(10, 6)
10 = 1 x 6 + 4 gcd(6, 4)
6 = 1 x 4 + 2 gcd(4, 2)
4 = 2 x 2 + 0 gcd(2, 0)

11 August 2024 25
Euclid’s Algorithm

◼ find gcd(24140,16762)

11 August 2024 26
Finding multiplicative inverse in GF(2n)

◼ If gcd (m, b) =1 then b has a multiplicative inverse modulo m.

◼ So Euclidean algorithm can be extended so that, in addition to

finding gcd (m, b), if gcd is 1 the algorithm returns the
multiplicative inverse of b.

11 August 2024 27
11 August 2024 28
Inverse of 550 in GF(1759)

11 August 2024 29
Inverse of 49 in GF(37)

11 August 2024 30
Solve following:

◼ 1234 mod 4321

◼ 550 mod 1769

11 August 2024 31
Euler Totient Function ø(n)

◼ The Euler’s totient function ø(n), defined as the number of

positive integers less than n & relatively prime to n.

◼ Ex. for n=10 ø(n) = {1,3,7,9}

◼ Term “residue” refers to numbers less than some modulus, and

the “reduced set of residues” to those numbers (residues)
which are relatively prime to the modulus (n).
❑ Ex for n=10,

❑ complete set of residues is {0,1,2,3,4,5,6,7,8,9}

❑ reduced set of residues is {1,3,7,9}

11 August 2024 32
Euler Totient Function ø(n)

◼ To compute ø(n) need to count number of residues to be

excluded

◼ in general need prime factorization, but

❑ for p (p prime) ø(p) = p-1

❑ for p.q (p,q prime) ø(pq) =(p-1)x(q-1)

◼ eg.
ø(37) = 36
ø(21) = (3–1)x(7–1) = 2x6 = 12

11 August 2024 33
Euler’s Theorem

◼ For every a and n that are relatively prime

aø(n) ≡ 1 (mod n) for any a,n where gcd(a,n)=1

◼ Ex.
a=3; n=10; ø(10)=4;
hence 34 = 81 = 1 mod 10

a=2; n=11; ø(11)=10;

hence 210 = 1024 = 1 mod 11

11 August 2024 34
Fermat’s Theorem

ap-1=1(mod p)
P is prime and a is a positive integer not divisible by p

3201mod 11
3 is not divisible by 11
Hence ap-1mod p
3(11-1) = 310=1mod11
(310)20*(3) mod 11
=1*3 mod 11
=3

11 August 2024 35
Fermat’s Theorem

Solve following:

2345 mod 11

350 by 7

5101mod31

11 August 2024 36
11 August 2024 37
11 August 2024 38