Page 230 - Hardware Implementation of Finite-Field Arithmetic

210 Cha pte r Se v e n

registers: process(clk, reset)
begin
if reset = ‘1’ or first_step = ‘1’ then
r <= (‘0’ & A); s <= (‘1’ & F);
u <= (0 => ‘1’, others => ‘0’); v <= (others => ‘0’);
d <= (others => ‘0’);
elsif clk’event and clk = ‘1’ then
if capture = ‘1’ then
r <= new_r; s <= new_s; u <= new_u; v <= new_v;
d <= new_d;
end if;
end if;
end process;
A VHDL process models the combinational part. Additionally, a
simple state machine, a counter, and registers are necessary to store
intermediate data.
The Almost Inverse Algorithm [SOOS95] is a modification of the binary
k
− 1
Euclidean algorithm and computes a (x)x mod f(x) as an intermediate
k
result. The inverse a − 1 (x) is finally obtained by the reduction of x .
Algorithm 7.22 is a modified version of the Almost Inverse Algorithm
given in [HLM00], where the inverse is produced directly. The algorithm
performs a division of b(x) whenever u(x) is divided by x. If b(x) is not
divisible by x, then b(x) is replaced by b(x) + f(x) before the division.
− 1
Finally, b(x) = a (x) mod f(x). The algorithm in [HLM00] follows:
m
Algorithm 7.22—Almost Inverse Algorithm (modified) for inversion in GF(2 )
Input: a(x), f(x)
Output: b(x) = a (x)
-1
1. v(x) := f(x); c(x) := 0; u(x) := a(x); b(x) := 1;
2. while x divides u(x) do
3. u(x) := u(x)/x
4. if x divides b(x) then
5. b(x) := b(x)/x
6. else
7. b(x) := (b(x) + f(x))/x
8. if u(x) = 1 then return(b(x))
9. if deg(u(x)) < deg(v(x)) then
10. {u(x) := v(x), v(x) := u(x)};
11. {b(x) := c(x), c(x) := b(x)};
12. u(x) := u(x) + v(x);
13. b(x) := b(x) + c(x);
14. Go to step 2.
If the functions degreem and unitym are available that compute
the maximum degree of an (m + 1)-bit polynomial and determine
if an (m + 1)-bit polynomial is the unity, and therefore represent
the polynomials b(x), c(x), f(x), u(x), v(x), and a(x) with bit vectors
with m + 1 bits (type poly_vectorm), then the above algorithm can
be implemented as follows: