Page 122 - Hardware Implementation of Finite-Field Arithmetic

Operations over GF ( p ) 105

− 1
If b mod 4 = 0: c = c , d = d 4 mod p
i i + 1 i i + 1 i
If b mod 4 ≠ 0 and b is even: c = c , d = d 2 − 1 mod p
i i i + 1 i i + 1 i
− 1
If b is odd, b + a mod 4 = 0 and β ≥α: c = c, d = (d + c)4 mod p
i i i i i i + 1 i i + 1 i i
If b is odd, b + a mod 4 = 0 and β < α: c = d, d = (d + c)4 mod p
− 1
i i i i i i + 1 i i + 1 i i
− 1
If b is odd, b − a mod 4 = 0 and β ≥α: c = c, d = (d − c)4 mod p
i i i i i i + 1 i i + 1 i i
− 1
If b is odd, b − a mod 4 = 0 and β < α: c = d, c = (d − c)4 mod p
i i i i i i + 1 i i + 1 i i
In conclusion, after a finite number of steps ⏐a ⏐= 1 (Lemma 4.4)
i
and c y ≡ x mod p (same proof as Lemma 4.3), that is,
i
xy mod p = c if a = 1 xy mod p = p − c if a =− 1 (4.28)
− 1
− 1
i i i i
Given an integer w, the value of an integer equivalent to w2 −1
mod p can be computed as follows:
− 1
if w mod 2 = 0 then w/2 ≡ w2 mod p
(4.29)
if w mod 2 = 1 then (w + p)/2 ≡ w2 − 1 mod p
and the value of an integer equivalent to w4 mod p as follows: if p
− 1
mod 4 = 1 then
if w mod 4 = 0 then w/4 ≡ w4 − 1 mod p
− 1
if w mod 4 = 1 then (w − p)/4 ≡ w4 mod p
(4.30)
− 1
if w mod 4 = 2 then (w + 2p)/4 ≡ w4 mod p
if w mod 4 = 3 then (w + p)/4 ≡ w4 mod p
− 1
and if p mod 4 = 3 then
if w mod 4 = 0 then w/4 ≡ w4 − 1 mod p
− 1
if w mod 4 = 1 then (w + p)/4 ≡ w4 mod p
(4.31)
− 1
if w mod 4 = 2 then (w + 2p)/4 ≡ w4 mod p
if w mod 4 = 3 then (w − p)/4 ≡ w4 mod p
− 1
If w belongs to the interval − p < w < p then − p < w/2 < p and − p <
(w + p)/2 < p, and if w belongs to the interval − 2p < w < 2p then − p <
w/4 < p, − p < (w + p)/4 < p, − p < (w + 2p)/4 < p, and − p < (w − p)/4 < p.

Assume that the functions
function divide_by_2(w, p: in integer) return integer
function divide_by_4(w, p: in integer) return integer
−1
−1
returning integers equivalent to w2 mod p and w4 mod p,
respectively, according to the sets of Eqs. (4.29) to (4.31), have been
defined. During the execution of the following algorithm, a, b, c, and d