Page 278 - Hardware Implementation of Finite-Field Arithmetic

258 Cha pte r Ei g h t

Algorithm 8.10—Itoh-Tsujii inversion algorithm in normal basis
Input: A
Output: L = A -1
1. S :=⎣log (m - 1) ⎦ - 1.
2
2. P := A
3. for i = S downto 0 do
4. R := Shift (m – 1) to right by S bits
5. Q := P
6. Rotate Q to left by ⎣R/2⎦ bits
7. T := PQ
8. If last bit of R = 1 then
9. Rotate T to left by 1 bit
10. P := TA
11. else
12. P := T
13. end if
14. S := S – 1
15. end for
16. Rotate P to left by 1 bit
17. L := P
18. return L
The Itoh-Tsujii algorithm achieves inversion by computing the expo-
nentiation A −1 = A 2 m − 2 , using a clever recursive decomposition tech-
nique applied on the exponent. The efficiency of the algorithm is
based on the efficient squaring property of the normal basis and on
the reduction of the number of required multiplications to O(log m).
It must be noted that the shift (left, right) and rotate operations in
Algorithm 8.10 refer to a bit ordering from (m – 1) downto 0.
Assume that the functions
function log(x: integer) return integer
function vectoint(x: poly_vector) return integer
computing ⎣log x⎦, and converting a bit vector to its integer value are
2
available. Then the following algorithm implements the Itoh-Tsujii
inversion scheme given in Algorithm 8.10.

Algorithm 8.11—Itoh-Tsujii inversion algorithm in normal basis for GF(2 )
m
r := inttovect(m-1);
rint := vectoint(r);
s := log(m-1) - 1;
p := a;
for i in reverse 0 .. s loop
for i in 1 .. s loop
r := lshift(r);
end loop;
q := p;
for i in 1 .. rint/2 loop
q := NB_sq(q);
end loop;