Modular Arithmetic

Nov 2, 2024
Set of Integers (z)

Nov 2, 2024
Modulo Operator
Find the result of the following
operations:

a) 27 mod 5
b) 36 mod 12
c) −18 mod 14
d) −7 mod 10

Nov 2, 2024
Modulo Operator
a) 27 mod 5 27/5 gives remainder

=2

b) 36 mod 12 36/12 gives remainder

=0

c) −18 mod 14 -18/14 gives remainder

= -4 , Ans= (-4+14)=10
Nov 2, 2024
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.

Nov 2, 2024
 Congruence (≡ operator)
To show that two integers are congruent,
we use the congruence operator ( ≡ ).
It indicates equality in modulus.

2 mod 10= 2
12 mod 10=2

3 mod 5=3
8 mod 5=3

Nov 2, 2024
 Residue Classes
A residue class [a] or [a]n is the set
of integers congruent modulo n.
For example n=5
Z5={0, 1, 2, 3, 4}
Then we have 5 residue classes.

Nov 2, 2024
Comparison of Z and Zn using
graphs

Nov 2, 2024
Operation in Zn

Nov 2, 2024
 Operation in Zn
Perform the following operations (the
inputs come from Zn):
1. Add 7 to 14 in Z15.
2. Subtract 11 from 7 in Z13.
3. Multiply 11 by 7 in Z20.

Nov 2, 2024
Zn Operation properties

Nov 2, 2024
 Zn Operation properties

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
Nov 2, 2024
 Inverses
In modular arithmetic, we often need
to find the inverse of a number.
Additive Inverse
Multiplicative Inverse

Nov 2, 2024
Additive Inverse
In Zn, two numbers a and b are
additive inverses of each other if

The sum of an integer and its

additive inverse is congruent to 0
modulo n.
In modular arithmetic, each integer
has an additive inverse.

Nov 2, 2024
Additive Inverse
Find all additive inverse pairs in
Z10.

The six pairs of additive inverses

are (0, 0), (1, 9), (2, 8),
(3, 7), (4, 6), and (5, 5).

Nov 2, 2024
 Multiplicative Inverse
In Zn, two numbers a and b are the multiplicative
inverse of each other if

When it does, the product of the integer and its

multiplicative inverse is congruent to 1 modulo n.
The number ‘a’ has multiplicative inverse in Zn if
and only if
gcd (n, a) = 1.
 In modular arithmetic, an integer may or may
not have a multiplicative inverse.
Nov 2, 2024
 Multiplicative Inverse
Find the multiplicative inverse of 8 in Z10.

 As gcd (10, 8) = 2 ≠ 1 , number 8 has no

multiplicative inverse in Z10.

Find all multiplicative inverses in Z10.

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. As gcd with 10 is not
equal to 1.

Nov 2, 2024
 Euclidean Algorithm to
find GCD
Fact 1: gcd (a, 0) = a
Fact 2: gcd (a, b) = gcd (b, r), where r is
the remainder of dividing a by b

Fact 1: if second number is 0 then gcd is first number.

Fact 2: change values of a and b until b becomes 0.


gcd(36,10)=gcd(10,6)=gcd(6,4)=gcd(4,2)=gcd(2,0)
=2

Nov 2, 2024
 find GCD

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

Nov 2, 2024
 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.

Nov 2, 2024
Extended Euclidean Algorithm

Nov 2, 2024
Extended Euclidean Algorithm

Nov 2, 2024
 Extended Euclidean Algorithm
Example 1:
Given a = 161 and b = 28, find gcd (a,
b) and the values of s and t.

gcd (161, 28) = 7, s = −1 and t = 6.

Nov 2, 2024
 Extended Euclidean Algorithm
Example 2:
Given a = 17 and b = 0, find gcd (a, b) and
the values of s and t.

Nov 2, 2024
 Extended Euclidean Algorithm
Example 2:
Given a = 17 and b = 0, find gcd (a, b) and
the values of s and t.

gcd (17, 0) = 17, s = 1, and t = 0.

Nov 2, 2024
Multiplicative Inverse using Extended
Euclidean Algorithm

The extended Euclidean algorithm finds the

multiplicative inverses of ‘b’ in Zn when n and

a are given and gcd (n, b) = 1.
The multiplicative inverse of ‘b’ is the value

of t after being mapped to Zn.

Nov 2, 2024
Multiplicative Inverse using Extended Euclidean Algorithm

Nov 2, 2024
Multiplicative Inverse using Extended Euclidean Algorithm
 Find the multiplicative inverse of 11 in Z26.
 n=r1=26
 B=r2=11

 The gcd (26, 11) is 1; the inverse of 11 is 7 or 19.

Nov 2, 2024
Multiplicative
 Inverse using Extended Euclidean Algorithm
Find the multiplicative inverse of 23 in Z100.
n=r1=100
b=r2=23

The gcd (100, 23) is 1; the inverse of 23 is 13 or

87. Nov 2, 2024
 Multiplicative Inverse using Extended Euclidean Algorithm
Find the inverse of 12 in Z26.

Nov 2, 2024
 Multiplicative
Find Inverse using
the inverse of Extended
12 in ZEuclidean
26.
Algorithm

The gcd (26, 12) is 2; the inverse does not

exist.

Nov 2, 2024
 Addition and Multiplication Tables
Addition table for Z10

Check row and column of element 0, they are

additive inverse to each other in Z10.
 (0,0) , (1,9) , (2,8) , (3, 7) , (4, 6) , (5, 5) , (6, 4) , (7, 3) , (8, 2) , (9, 1)
Nov 2, 2024
 Addition and Multiplication Tables
Multiplication table for Z10

Check row and column of element 1, they are

multiplicative inverse to each other in Z10.
(1,1) , (3, 7) , (7, 3) , (9, 9)

Nov 2, 2024
Different Sets : Zn and Zn* sets

Zn= set of additive inverse numbers.

Zn*= set of multiplicative inverse numbers.

Nov 2, 2024
Different Sets : Zn and Zn* sets
Find Z6 and Z6* sets

Nov 2, 2024
 Different Sets : Zn and Zn* sets
 Find Z6 and Z6* sets
0 1 2 3 4 5 0 1 2 3 4 5
0 0 1 2 3 4 5 0 0 0 0 0 0 0

1 1 2 3 4 5 0 1 0 1 2 3 4 5

2 2 3 4 5 0 1 2 0 2 4 0 2 4

3 3 4 5 0 1 2 3 0 3 0 3 0 3

4 4 5 0 1 2 3 4 0 4 2 0 4 2

5 5 0 1 2 3 4 5 0 5 4 3 2 1

Addition table for Z6 Multiplication table for Z6

 Z6 ={0, 1, 2, 3, 4, 5}
Z 6* ={1, 5}
Compiled By Rohini Temkar Nov 2, 2024
Two More Sets

Cryptography often uses two more sets:

Zp and Zp*.
 The modulus in these two sets is a
prime number.

Zp ={0, 1, ………, p-1}

Zp* ={1, 2, ………, p-1}

Nov 2, 2024
MATRICES
A matrix of size l  m

Nov 2, 2024
Examples of matrices

Nov 2, 2024
Matrix Addition and Subtraction

Nov 2, 2024
Matrix Multiplication
Product of a 2 × 3 matrix by a 3 × 4
matrix.

The result is a 2 × 4 matrix.

Nov 2, 2024
Scalar multiplication of Matrix

Nov 2, 2024
Determinant of Matrix

The determinant is defined only for a

square matrix.
The determinant of a square matrix A of
size m × m denoted as det (A) is a
scalar calculated recursively as shown
below:

Nov 2, 2024
Determinant of Matrix

Nov 2, 2024
Inverse of Matrix
Matrices have both additive and
multiplicative inverses.

Additive inverse
Additive inverse of matrix A is defined -A .
Additive inverse of matrix A is matrix B,
such that A+B=0

Multiplicative Inverse
Multiplicative inverses are only defined for
square matrices.
Multiplicative of matrix A is matrix B, such
Nov 2, 2024
 Residue Matrices
Cryptography uses residue matrices: matrices
where all elements are in Zn.
Operations on matrix are done in modular
arithmetic.
A residue matrix has a multiplicative inverse if
gcd (det(A), n) = 1

A residue matrix in Z26 and its multiplicative inverse

Nov 2, 2024
LINEAR CONGRUENCE

Cryptography often involves

solving an equation or a set of
equations of one or more variables
with coefficient in Zn.

Single-Variable Linear Equations

Set of Linear Equations

Nov 2, 2024
Single-Variable Linear Equations

Equations of the form ax ≡ b (mod

n ) might have no solution or a
limited number of solutions.

Nov 2, 2024
Single-Variable Linear Equations
Steps to find Solution:
Reduce equation by dividing both
sides of equation(including modulus)
by ‘d’.
Multiply both sides of equation by
multiplicative inverse of ‘a’ to find
particular solution ‘x0’.
The general solutions are
x = x0 +k (n/d) for k=0, 1, ……, (d-1)

Nov 2, 2024
 Single-Variable Linear Equations
Example 1
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.

Nov 2, 2024
 Single-Variable Linear Equations
Example 2
Solve the equation 14 x ≡ 12 (mod 18).
Solution: d= gcd(a,n) = gcd(14, 18) = 2

Steps to find Solution:

• Reduce equation by dividing both sides of
equation(including modulus) by ‘d’.
• Multiply both sides of equation by multiplicative
inverse of ‘a’ to find particular solution ‘x0’.
• The general solutions are
• x = x0 +k (n/d) for k=1, ……, (d-1)
Nov 2, 2024
Set of Linear Equations
Nov 2, 2024
 Without
Fermat’s
theorem

With
Fermat’s
theorem

Compiled By Rohini Temkar Nov 2, 2024

Without Fermat’s theorem

Nov 2, 2024
Compiled By Rohini Temkar Nov 2, 2024
Nov 2, 2024
Compiled By Rohini Temkar Nov 2, 2024
Compiled By Rohini Temkar Nov 2, 2024
Compiled By Rohini Temkar Nov 2, 2024
Compiled By Rohini Temkar Nov 2, 2024
Compiled By Rohini Temkar Nov 2, 2024
Compiled By Rohini Temkar Nov 2, 2024