Scribd
Upload
22 views

Euclidean and ExtdndEuclodean Algo

The document summarizes modular arithmetic and the Euclidean algorithm. It discusses how modular arithmetic maps integers into sets defined by a modulus and exhibits properties when performing operations. It then describes the Euclidean algorithm and extended Euclidean algorithm, which can be used to find the greatest common divisor (GCD) of two integers and the multiplicative inverse of an integer modulo another integer. The extended Euclidean algorithm returns values that satisfy an equation to determine the multiplicative inverse.

Uploaded by

triaz7191
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
22 views

Euclidean and ExtdndEuclodean Algo

The document summarizes modular arithmetic and the Euclidean algorithm. It discusses how modular arithmetic maps integers into sets defined by a modulus and exhibits properties when performing operations. It then describes the Euclidean algorithm and extended Euclidean algorithm, which can be used to find the greatest common divisor (GCD) of two integers and the multiplicative inverse of an integer modulo another integer. The extended Euclidean algorithm returns values that satisfy an equation to determine the multiplicative inverse.

Uploaded by

triaz7191
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 18

Cryptography and Security

Mechanisms

Lecture 2B – Modular Arithmetic

Nazar Abbas Saqib


[email protected]
Modular Arithmetic

Modular Arithmetic
Euclid’s Algorithm
Extended Euclid’s Algorithm

2
Modular Arithmetic
Modular arithmetic refers to perform all arithmetic operations using
the mod n operator.
Given any positive integer n and any non-negative integer a, if we
divide a by n, we get a= qn + r, where q= quotient r=remainder
a=11; n=7; 11=1 x 7 + 4; r=4, q=1
a= -11; n=7; -11=(-
11=(-2) x 7 + 3; r=3, q=-
q=-2
When a is divided by n, a mod n is defined to be the remainder r and
the integer n is called the modulus.

It maps all integers into the set of integers { 0,1,2,….n-1},

3
Modular Arithmetic Operation

Modular arithmetic exhibits the following properties:


[(a mod n) + (b mod n)] mod n = (a + b) mod n
[(a mod n) - (b mod n)] mod n = (a - b) mod n
[(a mod n) x (b mod n)] mod n = (a x b) mod n

4
Congruence
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)
(11 mod 4) ≡ (7 mod 4) 11 ≡ 7 (mod 4 )
(21 mod 10) ≡ (-9 mod 10) 21 ≡ - 9 (mod 10)

Congruence for mod 3

5
Arithmetic Modulo 8
a + b mod 8
Arithmetic Modulo 8
a x b mod 8
Arithmetic Modulo 8
• The additive inverse, opposite of a number a is the number that,
inverse or opposite,
when added to a, yields zero. The additive inverse of F is denoted −F
The multiplicative inverse or reciprocal for a number x, denoted by 1/x
or x−1, is a number which when multiplied by x yields the multiplicative
identity, 1
Greatest Common Divisor (GCD)

The positive integer c is said to be the GCD of a and b if


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

GCD(a, b)= GCD(a, -b)= GCD(-a,b)= GCD(-a, -b)= GCD(|a|, |b|)


GCD(60,24)= GCD(60,-24)=12
The Euclidean Algorithm
The Euclidean algorithm is used to find the GCD of two
positive integers
Finding the Greatest Common Divisor (GCD)
The Euclidean algorithm is based on the following theorem,
For any non-negative integer a and any positive integer b,
GCD (a, b) = GCD(b, a mod b)
GCD(55,22)= GCD(22, 55 mod 22)= GCD(22, 11) =11
The Euclidean Algorithm

Relatively prime or Co-


Co-Prime
Two integers a and b are said to be co-
co-prime or
relatively prime if they have no common positive
factor other than 1 or, equivalently, if their greatest
common divisor is 1
The fast way to determine it is through Euclidean
algorithm
The Euclidean Algorithm
The Euclidean Algorithm makes repeated use of GCD(a, b) =
GCD(b, a mod b) to determine GCD of two positive integers a &
b, the algorithm can be described as follows:
The Euclidean Algorithm
GCD(a,b)=GCD(120,23)
Initialization: r1 <- a, r1=120 & r2 <- b, r2=23
r = r1 - q x r2 , q=r1/r2

q = r1/r2 r1 r2 r = r1 – qxr2
5 120 23 5
4 23 5 3
1 5 3 2
1 3 2 1
2 2 1 0
1 0

GCD(a,b)= r1 when r2=0


GCD(120,23)=1
The Euclidean Algorithm
GCD(a,b)=GCD(2740,1760)
Initialization: r1 <- a, r1=2740 & r2 <- b, r2=1760
r = r1 - q x r2 , q=r1/r2

GCD(a,b)=GCD(2740,1760)=20
The Extended Euclidean Algorithm
The Extended Euclidean Algorithm can be used to find the
multiplicative inverse of a positive integer a mod n

Multiplicative Inverse
The multiplicative inverse of a is an element a-1 Є Zm, such
that aa-1≡ 1 (mod m)

How to Find Multiplicative Inverse


Use the Extended Euclidean Algorithm to find
integers s and t, such that n*s + b*t=1
b-1≡ t mod n
The Extended Euclidean Algorithm

16
How to Find Multiplicative Inverse
Use the Extended Euclidean Algorithm to find
integers s and t, such that n*s + b*t=1
b-1≡ t mod n

When r2=0, gcd(a,b)= r1, s=s1, t=t1 And a-1 =t


17
The Extended Euclidean Algorithm
Find the multiplicative inverse of 23 mod 120
Initialization:
r1 <- a, r1=120 & r2 <- b, r2=23
s1=1,s2=0
t1=0, t2=1
r = r1 - q x r2 , q=r1
q=r1/r2
/r2
s = s1 – qxs2
t = t1 – qxt2

q = r1/r2 r1 r2 r = r1 – qxr2 s1 s2 s = s1 – qxs2 t1 t2 t = t1 – qxt2

5 120 23 5 1 0 1 0 1 -5

4 23 5 3 0 1 -4 1 -5 21
1 5 3 2 1 -4 5 -5 21 -26
1 3 2 1 -4 5 -9 21 -26 47
2 2 1 0 5 -9 23 -26 47 -120
1 0 -9 23 47 -120

When r2=0, gcd(120,23)= r1=1, s=s1 =-9, t=t1 =47 And a-1 =t=47 mod 120

You might also like