Page 109 - Hardware Implementation of Finite-Field Arithmetic

92 Cha pte r F o u r

4.1 Euclidean Algorithm
The classical Euclidean algorithm ([HMV04], [MOV96]) for computing
the gcd of two naturals a and b consists of a set of integer divisions:
r = a, r = b
0 1
r = r q + r
0 1 1 2
(4.5)
r = r q + r
1 2 2 3
. . .
r = r q + r
n − 2 n − 1 n − 1 n
As r > r > r > . . . , after a finite number of steps the remainder, say
1 2 3
r , will be equal to 0. Furthermore gcd(r , r ) = gcd(r , r ) = . . . =
n n − 1 n n − 2 n − 1
gcd(r , r ) = gcd(a, b). Thus,
0 1
gcd(a, b) = gcd(r , 0) = r (4.6)
n − 1 n − 1
In the particular case where a = p and b = y < p, the gcd is equal to 1,
that is,

r = 1 (4.7)
n − 1
− 1
For computing z = xy mod p, another set of values u , u , u , . . .
0 1 2
are computed in parallel with the computation of q , q , q , . . . :
1 2 3
u = 0, u = x
0 1
u = u − u q
2 0 1 1
u = u − u q (4.8)
3 1 2 2
. . .
u = u − u q
n n − 2 n − 1 n − 1
The following lemma is demonstrated by induction.

Lemma 4.1 u y ≡ r x mod p.
i i
Proof
For i = 0 and 1: u y = 0 and r x = px ≡ 0 mod p, u y = xy and r x = yx.
0 0 1 1
For i ≥ 2: uy = (u − u q )y = u y − u q y ≡ r x − r q x =
i i − 2 i − 1 i − 1 i − 2 i − 1 i − 1 i − 2 i − 1 i − 1
(r − r q )x = r x.
i − 2 i − 1 i − 1 i
Thus, according to Eq. (4.7) and Lemma 4.1, u y ≡ x mod p, that is,
n − 1
xy − 1 = u mod p (4.9)
n − 1
Algorithm 4.1—mod p division, Euclidean algorithm

a := p; b := y; c := 0; d := x;
while b > 1 loop