Cryptography Reference
In-Depth Information
Table 3.3
j
j
r
j
s
j
t
j
0
252
1
0
1
1
198
0
1
2
3
54
1-0•1=1
0-1•1=-1
3
1
36
0-1•3=-3
1-(-1)•3=4
4
2
18
1-(-3)•1=4
-1- 4 • 1 = -5
5
0
Now, assume (*) is true for
j
= 2, . . . ,
k
1. The
k
th step of the Euclidean algorithm
tells us that
r
k
=
r
k
2
r
k
1
q
k
1
, and by using the induction hypothesis, we can then show
(*) is true when
j
=
k
as follows:
r
k
= (
s
k
2
x
+
t
k
2
y
)
(
s
k
1
x
+
t
k
1
y
)
q
k
1
= (
s
k
2
s
k
1
q
k
1
)
x
+ (
t
k
2
t
k
1
q
k
1
)
y
=
s
k
x
+
t
k
y
Induction then says
s
n
x
+
t
n
y
=
r
n
= (
x
,
y
), as desired.
Java Algorithm
We should write a euclid() method to calculate the values cited in the
foregoing theorem. The BigInteger class does not provide such a method, so we will write
a BigIntegerMath class to place methods in. The BigInteger class will be used to house
many of the methods used in this topic. In particular, this class defines a euclid(BigInteger
x
, BigInteger
y
) method, which returns an array (say, arr[]) of three BigIntegers. We will set
arr[0] to (
x
,
y
) =
r
n
(from Proposition 12), arr[1] to
s
n
, and arr[2] to
t
n
. This method is not
recursive; an interesting exercise for you is to write it recursively.
import java.math.*;
import java.security.SecureRandom;
import java.util.*;
public class BigIntegerMath {
//Define some BigInteger constants; this is handy for comparisons
static final BigInteger ZERO=new BigInteger(“0”);
static final BigInteger ONE=new BigInteger(“1”);
static final BigInteger TWO=new BigInteger(“2”);
static final BigInteger THREE=new BigInteger(“3”);
static final BigInteger FOUR=new BigInteger(“4”);
Search WWH ::
Custom Search