Linear Diophantine Equations and Linear Congruences - Introduction to Cryptography with Java Applets - page 91

FIGURE 4.1

BigInteger c) throws IllegalArgumentException {
if (a.compareTo(ZERO)<=0||b.compareTo(ZERO)<=0||c.compareTo(ZERO)<0)
throw new IllegalArgumentException
(“All constants must be positive in linear diophantine equation.”);
BigInteger[] euclidAnswers=euclid(a,b);
if (c.mod(euclidAnswers[0]).compareTo(ZERO)!=0)
throw new IllegalArgumentException
(“No solution since “+euclidAnswers[0]+” does not divide “+c+”.”);
BigInteger[] answer=new BigInteger[3];
BigInteger q=c.divide(euclidAnswers[0]);
answer[0]=euclidAnswers[0];
answer[1]=q.multiply(euclidAnswers[1]);
answer[2]=q.multiply(euclidAnswers[2]);
return answer;

}

There is an applet called TestDiophantineApplet on the topic's website you can use to
solve linear diophantine equations. A screen shot of the applet solving a sample equation is
shown in Figure 4.1.

4.2 LINEAR CONGRUENCES

Now we can begin the study of congruences, which are a special type of relation greatly influ-
enced by and related to diophantine equations. They are used heavily in many cryptosys-
tems. The definition of congruence follows.