Scribd
Upload
6 views10 pages

Understanding GCD and Its Applications

The document explains the concept of the greatest common divisor (GCD) and its properties, including the Euclidean algorithm for calculating GCD. It also introduces the concept of relatively prime integers and provides examples. Additionally, it outlines the Extended Euclid’s algorithm and demonstrates its application in encryption and decryption processes using public and private keys.

Uploaded by

laddhruvrcf
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
6 views10 pages

Understanding GCD and Its Applications

The document explains the concept of the greatest common divisor (GCD) and its properties, including the Euclidean algorithm for calculating GCD. It also introduces the concept of relatively prime integers and provides examples. Additionally, it outlines the Extended Euclid’s algorithm and demonstrates its application in encryption and decryption processes using public and private keys.

Uploaded by

laddhruvrcf
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

GCD (greatest common divisor )

The GCD of two integers is the largest positive integer that exactly divides both integers.

gcd(a, b) = gcd(a, -b) = gcd (-a, b) = gcd(-a,-b).

In general, gcd(a, b) = gcd(|a | , | b | ) gcd(60, 24) = gcd(60, -24) = 12

gcd(a, 0) = | a |

For example

gcd(20,28) = 4

and gcd of 70 and 56 is 14.


Relatively prime (or coprime)
Two integers are relatively prime if their only common (positive integer) factor is 1.

If GCD(a,b) =1 then a and b are relatively prime or coprime.

8 and 15 are relatively prime because the positive divisors of 8 are 1, 2, 4, and 8, and

the positive divisors of 15 are 1, 3, 5, and 15. So 1 is the only integer on both lists.

For example, 12 and 13 are relatively prime, but 12 and 14 are not.

6 and 17 = ???
8 and 31 = ???
7 and 21 = ???
Euclidean Algorithm
• For any nonnegative integer a and b,

GCD(a, b) = GCD (b, a mod b)


Euclidean Algorithm (Example)
1) GCD(18,12) = GCD(12,18 mod 12) = GCD(12,6) = GCD(6,0) =6

2) GCD(11,10) = GCD(10,11 mod 10) = GCD(10,1) = GCD(1,0) =1

Now calculate

GCD (1970,1066) = ?
Extended Euclid’s algorithm
• It is a simple procedure for determining the greatest common divisor (GCD) of
two positive integers.

* Refer pdf file (Handwritten Notes)


For this example,

1. Select two prime numbers, p = 17 and q = 11.


2. Calculate n = pq = 17 × 11 = 187.
3. Calculate f(n) = (p - 1)(q - 1) = 16 × 10 = 160.
4. Select e such that e is relatively prime to f(n) = 160 and less than f(n); we
choose e = 7.
5. Determine d such that d*e mod 160 = 1 and d < [Link] correct value is
d = 23,
because 23 × 7 = 161 = (1 × 160) + 1;

d can be calculated using the extended Euclid’s algorithm.


The resulting keys are
public key PU = {7, 187} and private key PR = {23, 187}.

plaintext input of M = 88.

Perform Encryption process and calculate Cipher text.


The resulting keys are
public key PU = {7, 187} and private key PR = {23, 187}.

plaintext input of M = 88.


For encryption, we need to calculate C = 887 mod 187. Exploiting the properties
of modular arithmetic
The resulting keys are
public key PU = {7, 187} and private key PR = {23, 187}.

cipher text C = 11.

• Perform Decryption Process and calculate Plaintext M.

You might also like