Euclid's Algorithm to find greatest common divisior

Greatest common divisor

One integer often needed in cryptography is the greatest common divisor of two positive integers. Two positive integer may have many common divisor but only one greatest common divisor. For example, the common divisor of 12 and 140 are 1, 2 and 4. However, 4 is the greatest common divisor.

      The greatest common divisor of two integers is largest integer which can divide both given integers.

The following block diagram illustrate the basic of the greatest common divisor of 12 and 140.

" Euclidean Algorithm "

Finding the greatest common divisor ( GCD ) of two positive integers by listing all common divisor is not practical, when the two number integers are large. Fortunately, more than 2000 years ago a mathematician named Euclid develop an algorithm that can find the greatest common divisor of two positive integers.

The Euclidean algorithm is based on the following two facts:

1. gcd ( a, 0 ) = a

2. gcd ( a, b ) = gcd ( b, r ); where r is the remainder of dividing a by b.

The first fact tells us that if the second integer is zero, then the gcd is the first one;

The second fact allow us to change the value of  ( a, b ) until 'b' becomes '0'. For example, to calculate the gcd( 36 , 10 ). We can use the second fact several time and the first fact once as shown below.

gcd ( 36, 10 )

gcd ( 10, 6 )

gcd ( 6, 4 )

gcd ( 4, 2 )

gcd ( 2, 0 ) = 0

Algorithm of GCD

Algorithm

r1  ⬅ a;   r2 ⬅  b;

while ( r2 > 0 )

{
 q  ⬅ r1 / r2;
 r   ⬅ r1 - q * r2 ;
 r1 ⬅ r2;
 r2 ⬅ r;
}
gcd ( a , b ) ⬅ r;



Example :

  Find the gcd of  2740 and 1760.

  gcd ( 2740, 1760 )
  gcd ( 1760, 980 )
  gcd ( 980, 780 )
  gcd ( 780, 200 )
  gcd ( 200, 180 )
  gcd ( 180, 20 )
  gcd ( 20, 0 )


  gcd ( 2740, 1760 )  = 20.

Find the gcd of 75 and 5 

So, gcd ( 75, 5 ) is 5.