Cryptography Reference
In-Depth Information
//A nonrecursive version of euclid. It returns an array answer of 3 BigIntegers
//answer[0] is the gcd, answer[1] is the coefficient of a, answer[2] the coeff
//of b
public static BigInteger[] euclid(BigInteger a,BigInteger b) throws
IllegalArgumentException {
//Throw an exception if either argument is not positive
if (a.compareTo(ZERO)<=0||b.compareTo(ZERO)<=0) throw new
IllegalArgumentException(“Euclid requires both arguments to be positive!”);
BigInteger[] answer=new BigInteger[3];
//Set up all the initial table entries
BigInteger r0=new BigInteger(a.toByteArray());
BigInteger r1=new BigInteger(b.toByteArray());
BigInteger s0=new BigInteger(“1”);
BigInteger s1=new BigInteger(“0”);
BigInteger t0=new BigInteger(“0”);
BigInteger t1=new BigInteger(“1”);
BigInteger q1=r0.divide(r1);
BigInteger r2=r0.mod(r1);
BigInteger s2,t2;
//When r2 becomes zero, the previous table entries are the answers
while (r2.compareTo(ZERO)>0) {
s2=s0.subtract(q1.multiply(s1)); s0=s1; s1=s2;
t2=t0.subtract(q1.multiply(t1)); t0=t1; t1=t2;
r0=r1; r1=r2; q1=r0.divide(r1); r2=r0.mod(r1);
}
answer[0]=r1; answer[1]=s1; answer[2]=t1;
return answer;
}
}
TestEuclidApplet is on the topic's website. Run it to test the algorithm (see Figure 3.6).
3.3
THE FUNDAMENTAL THEOREM OF ARITHMETIC
The following propositions lead us to the pinnacle of number theory: the Fundamental The-
orem of Arithmetic, which states that every integer factors uniquely into a product of prime
powers. Of course, we've been using this fact since we were children, but we rarely see the
proof until after we've left high school, and most people never see it at all. But first, two
other theorems:
PROPOSITION 13
If
a
,
b
, and
c
are positive integers with
a
and
b
relatively prime, and
such that
a
|
bc
, then
a
|
c
.
Proof.
Since
a
and
b
are relatively prime,
integers
x
and
y
such that
ax
+
by
= 1. Mul-
tiply both sides of the equation by
c
to get
acx
+
bcy
=
c
. Now, since
a
|
a
, and
a
|
bc
by hypoth-
esis, proposition 2 says
a
|(
acx
+
bcy
), a linear combination of
a
and
bc
. Hence,
a
|
c
.
Search WWH ::
Custom Search