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