Page 145 - Hardware Implementation of Finite-Field Arithmetic

128 Cha pte r F i v e

if load = ‘1’ then
c <= ZERO_POLY; int_b <= b; int_a <= a;
elsif update = ‘1’ then
c <= next_c; int_b <= zero_coef & int_b(M-1 downto 1);
int_a <= next_a;
end if;
end if;
end process registers_abc;
z <= c;
counter: process(clk)
begin
if clk’event and clk = ‘1’ then
if load = ‘1’ then count <=
conv_std_logic_vector(M-1, LOGM);
elsif update = ‘1’ then count <= count - 1;
end if;
end if;
end process counter;
count_equal_zero <= ‘1’ when count = 0 else ‘0’;
control_unit: process(clk, reset, count_equal_zero,
current_state)
begin
case current_state is
when 0 to 1 => load <= ‘0’; update <= ‘0’; done <= ‘1’;
when 2 => load <= ‘1’; update <= ‘0’; done <= ‘0’;
when 3 => load <= ‘0’; update <= ‘1’; done <= ‘0’;
end case;
if reset = ‘1’ then current_state <= 0;
elsif clk’event and clk = ‘1’ then
case current_state is
when 0 => if start = ‘0’ then current_state <= 1;
end if;
when 1 => if start = ‘1’ then current_state <= 2;
end if;
when 2 => current_state <= 3;
when 3 =>if count_equal_zero=’1’
then current_state <= 0; end if;
end case;
end if;
end process control_unit;

5.3 Exponentiation mod f(x)
In general, an arbitrary integer power k of an element a(x) ∈ Z [x]/f(x)
p
can be computed using the repeated “square and multiply” method
[MOV96], also known as binary method ([Knu81]), which breaks the
exponentiation operation into a series of squaring and multiplication
operations in Z [x]/f(x). This method is based on the observation that
p
m
the binary representation of any integer k, with 0 ≤ k ≤ p − 1, is given
by k =∑ t k 2 , with k ∈ {0,1}.
i
i=0 i i