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