Cryptography Reference
In-Depth Information
matrix is sent to the architecture.
a
00
is sent to
I
cell for partial multiplicative
inversion. The first row is sent to
N
l
for normalization. And the other rows
except the first row are sent to
E
lk
for elimination. In this clock cycle, one
iteration of Gauss-Jordan elimination is performed and the matrix has been
updated. In the following clock cycles, the pivot element is sent to
I
cell for
partial multiplicative inversion. The pivot row is sent to
N
l
for normalization.
And the other rows except the pivot row are sent to
E
lk
for elimination. It can
be observed that the system of linear equations with matrix size 12
×
12 can be
solved with 12 clock cycles.
...
N
1
N
2
N
11
N
12
...
E
1,1
E
1,2
E
1,11
E
1,12
I
...
E
2,1
E
2,2
E
2,11
E
2,12
...
E
11,1
E
11,2
E
11,11
E
11,12
...
...
...,...,...,...,...,...
...
aa aa
aa aa
§
·
§
c c c
·
§
cc cc
·
§
ccc
·
1 ...0
0 ...0
0...,...,...,...,...,...
0
a
a
a
10...0
01...0
00...,...,...,...
00...0
aa
aa
10...00
01...00
0..., ..., ..., ...
00...01
a
a
0,0 0,1
0,11 0,12
¨
¸
¨
¸
0,1
0,11
0,12
0,11
0,12
¨
0,12
¸
¨
¸
...
...
¨
¸
¨
¸
¨
¸
c c c
cc cc
ccc
¨
¸
a
a
a
1,0 1,1
1,11 1,12
¨
¸
¨
¸
¨
¸
1,1
1,11
1,12
1,11
1,12
1,12
¨
¸
¨
¸
¨
¸
¨
¸
¨
¸
¨
¸
¨
¸
¨
¸
¨
¸
aa aa
¨
¸
¨
¸
c
c c
cc cc
¨
ccc
¸
a
...0
a
a
aa
©
¹
a
©
¹
©
¹
11,0 11,1
11,11 11,12
©
¹
11,1
11,11
11,12
11,11
11,12
11,12
Fig. 2.
Proposed Architecture for Parallel Solving System of Linear Equations with
Matrix Size 12
×
12
Pivoting Operation.
If the pivot
a
ii
of the
i
i-th iteration is zero, we should
findanonzeroelement
a
ji
in the pivot column, i.e, the
i
i-th column, as the new
pivot element, where
i,j
=0
,
1
, ...,
11. Then the computational results of the
j
i-th row is sent to the
N
l
cells for normalization as the new pivot row. At the
same time, the computational results of the
i
i-th row is sent to the
E
jl
cells for
elimination. In this way, we can ensure that the pivot element is nonzero in a
new iteration. Therefore, the
I
cell, the
N
l
cells and the
E
kl
cells can execute
simultaneously.
An example of pivoting is shown in Fig. 3. Before the second iteration, the
second row is the pivot row but the pivot element is zero. The fourth row can
be chosen as the new pivot row since
a
31
is nonzero. Then
a
31
is sent to
I
