Cryptography Reference
In-Depth Information
numbers; the largest number that divides both evenly. The idea of the algorithm
is to recursively subtract the smaller of the two numbers from the larger until
one is 0. The other one is the GCD. In code, this can be implemented recursively
as in Listing 3-27.
Listing 3-27: gcd (small numbers)
int gcd( int x, int y )
{
if ( x == 0 ) { return y; }
if ( y == 0 ) { return x; }
if ( x > y )
{
return gcd( x - y, y );
}
else
{
return gcd( y - x, x );
}
}
So, for example, given x
105, y
252:
ITERATION
X
Y
0
105
252
1
147
105
2
42
105
3
63
42
4
21
42
5
21
21
6
0
21
This tells you that 21 is the largest number that evenly divides both 105 and
252 — 105/21
12. The actual values of the division operations
aren't particularly important in this context. What's important is that 21 is the
largest number that divides both without leaving a fractional part.
It may not be intuitively clear, but it can be proven that this will always complete.
If nothing else, any two numbers always share a GCD of 1. In fact, running the
GCD algorithm and verifying that the result is 1 is a way of checking that two
numbers are coprime or relatively prime, in other words they share no common factors.
5, and 252/21
 
Search WWH ::




Custom Search