Cryptography Reference
In-Depth Information
where congruence for matrices and matrix multiplication are defined as follows:
Definition
We say two
k
x
p
matrices
A
and
B
are congruent to each other modulo
n
if each entry
a
i
,
j
b
i
,
j
(mod
n
) for
i
= 1, . . . ,
k
,
j
= 1, . . . ,
p
.
E
XAMPLES
.
Here are some examples of congruent matrices.
≡
34
1
13
−
6
(mod 10)
−
8
21
2
≡
012
111
200
678
−
2
−
51
(mod 3)
11
9
15
6543
0064
1233
0017
0
−
1
−
2
−
3
0
−
60
−
2
72
−
3
−
9
60
−
51
(mod 6)
≡
Definition
If
A
is an
m
n
matrix, and
B
is an
n
p
matrix, the matrix product
C
=
AB
is the
m
p
matrix
c
1
,
1
c
1
,
2
··· c
1
,
p
c
2
,
1
c
2
,
2
··· c
2
,
p
···
···
···
c
m
,
1
c
m
,
2
··· c
m
,
p
where the
i
,
j
th entry of
C
is
a
i
,
k
b
k
,
j
k
= 1, 2, . . . ,
n
.
This simply means we multiply the entries of the
i
th row of
A
by the entries of the
j
th col-
umn of
B
, then sum them up to get the
i
,
j
th entry of
C
=
AB
. This also means, of course,
that the number of columns of the first matrix must be the same as the number of rows in
the second matrix. An example illustrating this process is shown in Table 6.1.
To use matrices to solve linear systems of congruences, we must determine whether or
not the operations we use for ordinary matrices representing systems of equations still hold
TABLE 6.1
3
1
3
1 2 5 1
5
1•1+2•7+5•1+1•2=22
9
•
=
1
7
0
2 4 0 0
10
30
6
0
1
1
0
2
1
Search WWH ::
Custom Search