Cryptography Reference
In-Depth Information
Algorithm and Architecture.
We give a straightforward description of the
proposed algorithm of the parallel variant of Gauss-Jordan elimination in Algo-
rithm 1, where
operation
(
i
) stands for operation performed in the
i
i-th iteration,
and
i
=0
,
1
, ...,
11. The optimized Gauss-Jordan elimination with 12 iterations
consists of pivoting, partial multiplicative inversion, normalization and elimina-
tion in each iteration.
We enhance the algorithm in four directions. First, multiplication of three
elements is computed by invoking three-input multipliers designed in Section 3.3.
Second, we adopt a partial multiplicative inverter described in Section 3.4 in our
design. Third, the partial multiplicative inversion, normalization and elimination
are designed to perform simultaneously. Fourth, during the elimination in the
i
i-th iteration, we simultaneously choose the right pivot for the next iteration,
namely if element
a
i
+1
,i
+1
of the next iteration is zero, we swap the (
i
+1)-th row
with another
j
-th row with the nonzero element
a
ji
,where
i,j
=0
,
1
, ...,
11. The
difference from usual Gauss-Jordan elimination is that the usual Gauss-Jordan
elimination choose the pivot after the elimination, while we perform the pivoting
during the elimination. In other words, at the end of each iteration, by judging
the computational results in this iteration, we can decide the right pivoting for
the next iteration. By integrating these optimizations, it takes only one clock
cycle to perform one iteration.
Algorithm 1.
Solving a system of linear equations
Ax
=
b
with 12 iterations,
where
A
is a 12
×
12 matrix
1: var
2: i: Integer;
3: begin
4: i := 0;
5: Pivoting(i = 0);
6: repeat
7: Partial inversion(i), Normalization(i), Elimination(i);
8: Pivoting(i+1);
9: i:= i+1;
10: until i = 12
11: end.
12, where
a
ij
is the element located at the
i
-th row and
j
i-th column of the matrix.
There exist three kinds of cells in the architecture, namely
I
,
N
l
,and
E
kl
,
where
k
=1
,
2
, ...,
11 and
l
=1
,
2
, ...,
12. The
I
cell is for partial multiplicative
inversion. As described in 3.4, two three-input multipliers are included in the
I
cell for computed partial multiplicative inversion. The
N
l
cells are for normal-
ization. And the
E
kl
cells are for elimination. The architecture consists of one
I
cell, 12
N
l
cells and 132
E
lk
cells.
The matrixes depicted in Fig. 2 are used only to illustrate how the matrix
changes. The left-most matrix is the one in the first clock cycle while the
i
-th
matrix is the one in the
i
i-th clock cycle. In the first clock cycle, the left-most
The proposed architecture is depicted in Fig. 2 with matrix size 12
×
