Scribd
Upload
3 views8 pages

Unit 2

The document provides an introduction to cryptography and the use of the Euclidean algorithm for computing the greatest common divisor (gcd) and modular inverses. It outlines the steps for applying the Euclidean algorithm through examples, demonstrating how to find the gcd and compute the inverse modulo. The instructor for the course is Dr. Mohammad Wazid from Graphic Era University, India.

Uploaded by

auuhshsauus
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
3 views8 pages

Unit 2

The document provides an introduction to cryptography and the use of the Euclidean algorithm for computing the greatest common divisor (gcd) and modular inverses. It outlines the steps for applying the Euclidean algorithm through examples, demonstrating how to find the gcd and compute the inverse modulo. The instructor for the course is Dr. Mohammad Wazid from Graphic Era University, India.

Uploaded by

auuhshsauus
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

Introduction to cryptography and PKC (TCS

493)

B. Tech CSE Cyber Security IV Semester

Instructor:
Dr Mohammad Wazid
Professor, Department of CSE
Graphic Era (Deemed to be University), Dehradun, India
Email: wazidkec2005@[Link]
Homepage: [Link]
Use euclidean algorithm to compute gcd
• In order to find the largest common divisor, we can prime
factorize both numbers and examine which prime factors that
appear in both numbers, that is, the largest common divisor will
be the intersection of the sets of prime factors for both numbers.
• However, the procedure of prime factorizing numbers is very
tedious.
• Start by dividing the larger number m with the smaller n. This
gives a remainder r1.
• Then divide the smaller number n with the obtained remainder
r1.
Use euclidean algorithm to compute gcd
• This gives anew remainder r2. Now divide the remainder r1
with the remainder r2.
• This gives yet another remainder r3.
• Repeat the procedure until the remainder becomes zero.
• The last non-zero remainder is equal to the largest common
divisor.
Use euclidean algorithm to compute gcd
• Example:
• gcd(100,44)?
• In case if we get 0 in the
reminder then previous
reminder is the gcd.
Use euclidean algorithm to compute gcd
• Other case:
• Example:
• gcd(9,7)?
• 9=7x1+2
• 7=2x3+1
• Note: In the reminder if get 1 then 1 will be the gcd.
Use euclidean algorithm to compute gcd
• Another example:
• gcd(15,13)?
• 15=13x1+2
• 13=2x6+1
• Therefore gcd will be 1.
• Note: greatest common factor (G.C.F)or highest common
factor (H.C.F) or greatest common divisor (G.C.D), we know
that there is no difference between them.
Extended Euclidean algorithm to compute
inverse modulo
• Compute 7-1 (mod 20)
• To compute this first apply the steps of Euclidean algorithm
• 20=7*2+6 ---(eq. 1)
• 7=6*1+1 ---(eq. 2)
• If we get reminder as a 1 then inverse modulo is possible
otherwise not.
• Eq. 1 and 2 can also be written as
• 20=7*2+6 ---(eq. 1) or 6=20-7*2
• 7=6*1+1 ---(eq. 2) or 1=7-6*1
Extended Euclidean algorithm to compute
inverse modulo
• 6=20-7*2 --- (eq. 3)
• 1=7-6*1--- (eq. 4)
• Substitute the value of 6 from eq. 3 to eq. 4
• 1=7-1*(20-7*2)
• 1=7-1*20-7*2
• 1=7*1-1*20+7*2
• 1=7*3-1*20 (whatever we’ll have in the multiplication of 7 will
be the modulo inverse.
• Therefore, 7-1 (mod 20) will be 3.

You might also like