Page 118 - Hardware Implementation of Finite-Field Arithmetic

Operations over GF ( p ) 101

In order to demonstrate the convergence of this iteration, compare
a + b with a + b : in the first case a + b = a + b /2 ≤ a + b ; in
i + 1 i + 1 i i i + 1 i + 1 i i i i
the second case a + b = b < a + b (a is odd); in the third case a +
i + 1 i + 1 i i i i i + 1
b = a < a + b (b is odd). Thus a + b < a + b , unless b = 0. In
i + 1 i i i i i + 1 i + 1 i i i
conclusion, after a finite number of steps b = 0 so that, according to
i
Eq. (4.22), gcd(a, b) = gcd(a , 0) = a .
i i
Lemma 4.2 After a finite number of steps, a = gcd(a, b).
i
In the particular case where a = p (a prime greater than 2 and thus
an odd natural) and b = y, the gcd is equal to 1, that is, a = 1.
i
-1
For computing z = xy mod p, two additional set of values c , c ,
1 2
c , . . . and d , d , d , . . . are computed in parallel. The initial values
3 1 2 3
are c = 0 and d = x. Then
0 0
− 1
If b is even: c = c , d = b 2 mod p;
i i + 1 i i + 1 i
If b is odd and b ≥ a : c = c , d = d − c mod p;
i i i i + 1 i i + 1 i i
If b is odd and b < a : c = d , d = c − d mod p.
i i i i + 1 i i + 1 i i
The following lemma is demonstrated by induction:
Lemma 4.3 c y ≡ a x mod p and d y ≡ b x mod p
i i i i
Proof
For i = 0: c y = 0 and a x = px ≡ 0 mod p, d y = xy and b x = yx.
0 0 0 0
For i >1 the values of c and d in function of c and d are cal-
i + 1 i + 1 i i
culated in the same way as the values of a and b in function
i + 1 i + 1
of a and b , but for the substitution of the conventional arithmetic
i i
operations by mod p operations.
In conclusion after a finite number of steps a = 1 (Lemma 4.2) and
i
c y ≡ x mod p (Lemma 4.3), that is,
i
− 1
xy mod p = c (4.23)
i
Given an element w of Z , the value of w2 mod p is computed as
− 1
p
− 1
− 1
follows: If w is even w2 mod p = w/2; if w is odd w2 mod p = (w + p)/2.
Assume that a function
function divide_by_2(w, p: in integer) return integer
−1
returning w2 mod p has been defined.
Algorithm 4.4—mod p division, binary algorithm
a := p; b := y; c := 0; d := x;
while a > 1 loop
while (b mod 2) = 0 loop
b := b/2; d := Divide_By_2(d, P);