The Integers - Introduction to Cryptography with Java Applets - page 77

252 = 1 · 198 + 54
198 = 3 · 54 + 36
54 = 1 · 36 + 18
36 = 2 · 18 + 0
The last nonzero remainder is 18, so (252, 198) = 18. We can write this process out very
quickly as
(252, 198) = (198, 54) = (54, 36) = (36, 18) = (18, 0) = 18.
Java Algorithm Once we know the Euclidean algorithm, writing a method to compute
the gcd should be simple. Though the BigInteger class supplies a method to compute the gcd
of two BigIntegers, it may be interesting to write our own. Here, we use a static recursive
method. Recursion is natural for this algorithm, because if we have positive ints m and n in
Java such that m > n , proposition 10 says that ( m , n ) = ( n , m % n ). This makes an easy sub-
stitution in a recursive call. The recursion is not particularly wasteful in this case since the
Euclidean algorithm arrives at the gcd so quickly. The following test program simply asks
the user to enter two integers, then computes and displays their gcd (see Figures 3.4a-c).
import java.io.*;
import javax.swing.*;
import java.math.BigInteger;
public class TestGCD {
public static void main(String[] args) {
BigInteger i=new BigInteger(JOptionPane.showInputDialog(“Enter an integer: “));
BigInteger j=new BigInteger(JOptionPane.showInputDialog
(“Enter another integer: “));
JOptionPane.showMessageDialog(null,”The gcd of “+i+” and “+j+” is “+gcd(i,j));
System.exit(0);
}
static BigInteger ZERO=new BigInteger(“0”);
//Compute the gcd recursively using the Euclidean algorithm
private static BigInteger gcd(BigInteger first, BigInteger second) {
//Make sure both are nonnegative
first=first.abs();
second=second.abs();
//Call the recursive method
return recurseGCD(first,second);
}
private static BigInteger recurseGCD(BigInteger x, BigInteger y) {
if (y.equals(ZERO)) return x;
else return recurseGCD(y,x.mod(y));
}
}