Page 175 - Hardware Implementation of Finite-Field Arithmetic

158 Cha pte r S i x

The most complex operation of Algorithms 6.6 and 6.7 is the mod
f(x) product. In Algorithm 6.6, it is executed approximately 2s ≈
2mlog p times, while in Algorithm 6.7 it is executed approximately m
2
times. Furthermore, it is worthwhile to look for optimized computa-
2
tion schemes. For instance, if m is odd, then r − 1 = p + p + . . . + p m − 1
2
2
u
can be decomposed under the form (p + p + . . . + p ) + (p + p + . . . +
u
u
p )p , where u = (m − 1)/2, and the computation of (h(x)) r − 1 can be
performed as follows:
e x () = hx hx () p ( 2 ) ... hx () p ( u )
p
()
x
hx () r–1 = e x e(x) p ( u )
()
In this way the number of mod f(x) products is approximately
equal to m/2. By recursively using this type of decomposition, the
number of mod f(x) products can be reduced to about log m.
2
As an example consider the case where m = 17. Then h(x) r − 1 can be
computed according to the following scheme ([WBP00][DCW00]):
dx () = h x ()
0
dx () = h x () p
1
dx () = d x d x () = h x () 1+ p
+
()
2 0 1
dx() = d x() p ( 2 ) = h x() p 2 + p 3
3 2
dx() = dx d x) = hx 1 ++pp 2 + p 3
()
( )
)
(
4 2 3
6 6
x
dx () p ( 4 ) = h () p 4 + p 5 + p + p 7
() = dx
5 4
6 6
pp
d x() = dx dx() = h x() 1+ + 2 + p 3 + p 4 + p 5 +p + p 7
()
6 4 5
13
14
p
dx() = d x() p ( 8 ) = h x() p 8 + p 9 + p 10 + p 11 + p 12 + p + p + p 15
7 6
5
3
pp +
4
9
7
11
dx = d x d x = h x() 1++ 2 p + p + p + p + p + p + p + p 10 + p + p 12 + p 13 + p 14 + p 15
8
6
p
()
()
()
8 6 7
8
9
10
13
12
11
15
d () = d () = h () p p + p + p + p + p + p + p + p + p + p + p + p + p + p + p 16
14
+
5
6
7
2
3
4
p
p
x
x
x
9 9 8
= hx() r 1–
It includes 4 mod f(x) products.
Algorithm 6.8—mod f(x) division, optimal extension field, m = 17, version 2
a := h;
for j in 0 .. m-1 loop e(J) := (a(J)*Frobenius(j,1))
mod P; end loop;