Page 171 - Hardware Implementation of Finite-Field Arithmetic

154 Cha pte r S i x

if clk’event and clk = ‘1’ then
if first = ‘1’ then a <= f; c <= zero_poly;
elsif ce_ac = ‘1’ then a(m) <=
conv_std_logic_vector(0, k);
for i in 0 to m-1 loop a(i) <= b(i); end loop;
c <= d;
end if;
end if;
end process registers_ac;
registers_bd: process(clk)
begin
if clk’event and clk = ‘1’ then
if first = ‘1’ then b <= h; d <= g;
elsif ce_bd = ‘1’ then b <= next_b; d <= next_d;
end if;
end if;
end process registers_bd;
The complete model additionally includes counters for storing α
and β, combinational circuits that compute the branching conditions
and a control unit.

m
6.3 Reduction to Multiplications over GF(p )
and Inversion over Z
p
m
The set of nonzero elements of GF(p ) is a cyclic group containing q − 1
m
elements (q = p ), so that, given a nonzero polynomial h(x), h(x) q − 1 = 1.
2
r p − 1
m
Let r = 1 + p + p + . . . + p m − 1 = (p − 1)/(p − 1). Thus, (h(x) ) = h(x) q − 1 = 1
r p
and (h(x) ) = h(x) . Taking into account that the fixed elements of the
r
p
Frobenius automorphism ϕ: a → a , ∀a ∈ GF(p ) are the elements of Z
m
p
r
([Kob94]), one deduces that h(x) is a nonzero element of Z :
p
r
r
h(x) ∈ Z h(x) ≠ 0 (6.26)
p
r −1
Thus, g(x)h(x)(h(x) ) h(x) r − 1 ≡ g(x) mod f(x) so that
r −1
z(x) = g(x)(h(x) ) h(x) r − 1 mod f(x) (6.27)
m
The problem has been reduced to multiplications over GF(p ),
r −1
and to an inversion over Z (calculation of (h(x) ) ).
p
Assume that the binary representation r r . . . r of r − 1 = p +
s − 1 s − 2 0
2
p + . . . + p m − 1 has been previously computed. The following algorithm
computes z(x):
m
Algorithm 6.6—mod f(x) division, multiplications over GF(p ), and inversion
over Z
p
E := One;
for I in 0 .. S-1 loop
E := Product_Mod_F(E, E, F);