Last Updated:

Euclidean algorithm's algorithm in Pascal

Euclidean's algorithm

Maybe Pascal isn't as popular today, but it's great for educational purposes. It is on his example that one of the main algorithms for cryptography will be shown, namely the Euclidean algorithm

What is Euclidean's algorithm

 

Euclidean's algorithm is the fastest way to find the largest common divisor (NOD) of two numbers. Unlike the usual search, Euclidean's algorithm looks for an answer ten times faster.

A little bit about history. Euclidean was a mathematician who was born in 325 B.C. Euclidean's algorithm was published in his "beginning" writings, where, by the way, the theory of an infinite set of prime numbers was put forward.

 

Euclidean's algorithm with division

Scope of the algorithm

 

For programmers, NOD is not only a familiar topic from elementary school. The principles of divisor search are laid down in cryptographic methods of encryption, namely in the type of encryption RSA.

Euclidean's subtraction algorithm

 

 

Let's look at the algorithm with an example. We need to find the greatest common divisor in the numbers 68 and 323:

A = 68
B = 323

1. A>B – No, then b = 323 – 68 = 255;
2. A>B – No, then b = 255 – 68 = 187;
3. A>B – No, then b = 187 – 68 = 119;
4. A>B – No, then b = 119 – 68 = 51;
5. A>B – Yes, then a = 68 – 51 = 17;
6. A>B – No, then b = 51 – 17 = 34;
7. A > B – No, then b = 34 – 17 = 17
8. A = B, Yes, then NOD = A = 17

Answer: NOD = 17

Euclidean's algorithm with division

 

Euclidean's algorithm with division

Let's check with the same example:

A = 68
B = 323

1. A>B – no, then B = 323 modulo 68 = 51;
2. A > B – Yes, then A = 68 modulo 51 = 17;
3. A>B – No, then B = 51 modulo 17 = 0;
4. A and B = 0, then the answer is 17 + 0 = 17.

Answer: NOD(68,323) = 17

This method is much faster than the first.

Comparison with brute force

 

Now let's find the NOD in the most primitive way – by searching. Our numbers are 68, 323. Unexpectedly?


To be sure that our method works, we need to check 68 operations. And Euclidean managed in just 5. That's the difference. No one uses the brute-force method.

Implementation on Pascal

All that's left is to execute the code in pascal:

vara, b: integer;
begin
write(‘a = ‘);
readln(a);
write(‘b = ‘);
readln(b);
while a <> b do
if a > b then
a := a – b
else
b := b — a; writeln(‘NOD = ‘, a);
end.

Conclusion

 

Euclidean's algorithm is the most practical way to find the largest common divisor. It is necessary to know everyone who wants to learn the basics of algorithms in programming.