Cryptography Reference
In-Depth Information
The matrices
A
and
B
are both known; we simply take the product
AB
modulo
n
to get
our solutions for
X
. (Note: Linear algebra says that when
I
is the identity matrix,
IX
=
X
, so
certainly
IX X
(mod
n
).)
E XAMPLE .
Find the solutions to
AX B
(mod 5) by finding
A
where
A
is the matrix
14
22
X
is the vector
x
y
and B is the vector
3
2
We already found the inverse A of A modulo 5 earlier; it is the matrix
34
24
and to use it to find
X
, we simply take the product
AB
:
34
24
3
2
17
14
2
4
(mod 5)
We now verify that x 2 (mod 5) and y 4 (mod 5) is actually a solution to the system
of congruences
x + 4 y 3 (mod 5)
2
x
y
+ 2
2 (mod 5).
Substitution reveals
2 + 4 4 = 18 3 (mod 5)
2
2 + 2
4 = 12
2 (mod 5)
and the solution checks.
You may have noticed something amiss in multiplying both sides of the congruence
AX B
. Namely, how do we know that
multiplying both sides of a matrix congruence by a matrix preserves the congruence? That
is, if two
(mod
n
) by some matrix
A
in order to solve for
X
nk
matrices
A
and
B
are such that
A B
(mod
m
), is it true that
AC BC
(mod
m
? The next
proposition shows that this is the case, and thus vindicates our seeming recklessness.
) for any
kp
matrix
C
, and that
DA DB
(mod
m
) for any
qn
matrix
D
PROPOSITION 24.
Suppose two
nk
matrices
A
and
B
are such that
A B
(mod
m
). Then
AC BC
(mod
m
) for any
kp
matrix
C
, and
DA DB
(mod
m
) for any
qn
matrix
D
.
Search WWH ::




Custom Search