Page 208 - Hardware Implementation of Finite-Field Arithmetic

188 Cha pte r Se v e n

where a new additional variable aux should be included in order to
hold the input operand a(x) modified by the Product_alpha_A function.
An executable Ada file LSBfirst_squarer.adb, including Algorithm
7.10, is available at www.arithmetic-circuits.org.
Bit-level Montgomery squaring could also be computed slightly
modifying Algorithm 7.8 for multiplication.

Algorithm 7.11 —Bit-level montgomery squaring
for i in 0 .. m-1 loop c(i) := 0; end loop;
for i in 0 .. m-1 loop
c := m2xvv(c,m2abv(a(i),a));
if c(0) = 1 then
c := m2xvv(c,m2abv(c(0),f));
c := lshift(c);
c(m-1) := 1;
else
c := lshift(c);
end if;
end loop;
An executable Ada file bsquarer_montgomery.adb, including
Algorithm 7.11, is also available at www.arithmetic-circuits.org.
However, the above multiplication-based algorithms can be
further optimized because squaring operation is a linear operation in
m
GF(2 ), that is,
2
c(x) = a(x) mod f(x) = (a x 2(m − 1) + a x 2(m − 2)
m − 1 m − 2
2
+ . . . + a x + a ) mod f(x) (7.33)
1 0
Therefore, in classic squaring given in Algorithm 7.9, polynomial
multiplication d(x) = a(x)a(x) computed by d := poly_multiplication(a,a)
can be substituted for the 2m – 2 polynomial d(x) = a x 2(m − 1) + a x 2(m − 2)
m − 1 m − 2
2
+ . . . + a x + a = (a , 0, a , 0, . . . , 0, a , 0, a ). The new algorithm is
1 0 m − 1 m − 2 1 0
given as following.
Algorithm 7.12—Classic squaring, version 2
for i in 0 .. 2*m-2 loop d(i) := 0; end loop;
for i in 0 .. m-1 loop d(2*i) := a(i); end loop;
R := reduction_matrix_R(f);
for j in 0 .. m-1 loop c(j) := d(j); end loop;
for j in 0 .. m-1 loop
for i in 0 .. m-2 loop
c(j) := m2xor(c(j),m2and(R(j,i),d(m+i)));
end loop;
end loop;
An executable Ada file classic_squaring_v2.adb, including
Algorithm 7.12, is available at www.arithmetic-circuits.org.