Page 110 - Hardware Implementation of Finite-Field Arithmetic

Operations over GF ( p ) 93

q := a/b; r := a mod b; next_d := (c - d*q);
a := b; b := r; c := d; d := next_d;
end loop;
z := d mod p;
An executable Ada file Euclidean_mod_p_division.adb, including
algorithm 4.1, is available at www.arithmetic-circuits.org.
In order to execute Algorithm 4.1 the following computation
primitives must be implemented: integer division, multiplication and
subtraction, and mod p reduction.

4.1.1 Integer Division
At each step of Algorithm 4.1 the quotient q = a/b and the remainder
r = a mod b must be computed. For using the SRT algorithm ([Par00],
[EL04], [DBS06]) the divisor b should be normalized (most significant
bit equal to 1), a rather complex operation. Instead, the nonrestoring
algorithm will be used.
The range of a and b is deduced from the fact that p = r > r >
0 1
r > . . . > 0, so that 0 < r ≤ p and 1 < r /r ≤ p. Thus, if p is a k-bit
2 i i − 1 i
number, so are a and b, with b ≥ 2. A slightly more general case is
considered: a is assumed to be a (k + 1)-bit 2’s complement integer,
k
k
that is, − 2 ≤ a < 2 . Define
s = a and y = b2 k − 2 (4.10)
0
k
k
k
so that − 2 ≤ s < 2 and y ≥ 2 · 2 k − 2 = 2 k − 1 . Thus 2y ≥ 2 > s , − 2y ≤− 2 ≤ s
k
0 0 0
and − 2y ≤ s < 2y. According to Property 2.1 the equation s = q y + r
0 0 1 1
has at least one solution with q ∈ {− 1, 0, 1} and − y ≤ r < y, so that
1 1
s = 2r belongs to the same interval −2y ≤ s < 2y. By repeatedly
1 1 1
applying Property 2.1 the following set of equations is generated:
a = s = q y + r , − y ≤ r < y
0 1 1 1
2r = s = q y + r , − y ≤ r < y
1 1 2 2 2
2r = s = q y + r , − y ≤ r < y (4.11)
2 2 3 3 3
. . .
2r = s = q y + r , − y ≤ r < y
k − 2 k − 2 k − 1 k − 1 k − 1
According to the Robertson diagram of Fig. 2.1 the value of q can
i
be chosen as follows:
If s < 0 then q =− 1 and r = s + y, and if s ≥ 0 then
i − 1 i i i − 1 i − 1
q = 1 and r = s − y
i i i − 1
Then multiply the first equation by 2 k − 2 , the second one by 2 k − 3 ,
and so on, and sum up the k − 1 equations. The result is
+
a2 k − 2 = (q · 2 k − 2 + q · 2 k − 3 + q · 2 k − 4 . . . + q · 2 )y + r
0
1 2 3 k − 1 k − 1