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
