Scribd
Upload
4 views3 pages

Euclidean Algorithm (Unit - 2)

The Euclidean Algorithm is a method for finding the Greatest Common Divisor (GCD) of two positive integers through repeated division. It involves dividing the larger number by the smaller, replacing the larger with the smaller and the smaller with the remainder, until the remainder is zero. The last non-zero remainder is the GCD, and this algorithm is particularly useful in fields like Computer and Network Security.

Uploaded by

navidhabhargavisret
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
4 views3 pages

Euclidean Algorithm (Unit - 2)

The Euclidean Algorithm is a method for finding the Greatest Common Divisor (GCD) of two positive integers through repeated division. It involves dividing the larger number by the smaller, replacing the larger with the smaller and the smaller with the remainder, until the remainder is zero. The last non-zero remainder is the GCD, and this algorithm is particularly useful in fields like Computer and Network Security.

Uploaded by

navidhabhargavisret
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

Euclidean Algorithm

The Euclidean Algorithm is a method used to find


the Greatest Common Divisor (GCD) of two
positive integers by repeatedly applying division.

Step-by-Step Explanation
1. Start with two numbers
Let the numbers be a and b, where a > b.
2. Divide a by b
Find the remainder r.
( a = bq + r )
3. Replace values
Replace a with b and b with r.
4. Repeat the process
Continue dividing until the remainder becomes
0.
5. Final GCD
The last non-zero remainder is the GCD.

Algorithm Flow
Start
↓
Take two numbers a and b
↓
Divide a by b → remainder r
↓
If r ≠ 0, set a = b, b = r
↓
Repeat until r = 0
↓
GCD = b
End

Example
Find the GCD of 48 and 18
Step 1
48 ÷ 18 = 2 remainder 12
→ a = 18, b = 12
Step 2
18 ÷ 12 = 1 remainder 6
→ a = 12, b = 6
Step 3
12 ÷ 6 = 2 remainder 0
Result
GCD = 6

The Euclidean Algorithm is a fast and efficient way to


find the GCD of two numbers and is widely used in
Computer and Network Security (CNS), especially
in cryptographic algorithms like RSA.

You might also like