Cryptography Reference
In-Depth Information
a.
a
+
c
b
+
c
(mod
m
)
b.
a
c
b
c
(mod
m
)
c.
ac
bc
(mod
m
).
Proposition 20.
Let
a
,
b
, and
c
be integers, and let
m
be a positive integer. Suppose
a
b
(mod
m
), and
c
d
(mod
m
). Then
a.
a
+
c
b
+
d
(mod
m
)
b.
a
c
b
d
(mod
m
)
c.
ac
bd
(mod
m
).
Proposition 21.
Let
a
,
b
, and
c
be integers, and
m
a positive integer. Let
d
= (
c
,
m
),
and suppose
ac
bc
(mod
m
). Then
a
b
(mod
m
/
d
).
Proposition 22.
Suppose
ax
b
(mod
m
), where
a
,
b
, and
m
are all positive integers.
Let
d
= (
a
,
m
). If
d
b
, the congruence has no solution for
x
. If
d
|
b
, then there are exactly
d
incongruent solutions modulo
m
, given by
x
=
x
0
+
tm
/
d
, where
x
0
is a particular solution
to the linear diophantine equation
ax
+
my
=
b
, and
t
= 0, 1, . . . ,
d
1.
Proposition 23.
When matrices are used to represent a system of linear congruences,
the three elementary row operations for matrices do not affect the solution(s) of the corre-
sponding system of congruences modulo
n
.
Proposition 24.
Suppose two
n
k
matrices
A
and
B
are such that
A
B
(mod
m
).
Then
AC
BC
(mod
m
) for any
k
p
matrix
C
, and
DA
DB
(mod
m
) for any
q
n
matrix
D
.
Proposition 25.
Suppose integers
a
1
,
a
2
, ...,
a
n
are pairwise relatively prime. Then
(
a
1
a
2
...
a
n
)|
c
if and only if
a
1
|
c
,
a
2
|
c
, ...,
a
n
|
c
.
Proposition 26.
Let
a
b
(mod
m
1
),
a
b
(mod
m
2
), . . . ,
a
b
(mod
m
n
) where
a
1
,
a
2
, ...,
a
n
are pairwise relatively prime. Then we have
a
b
(mod
m
1
m
2
...
m
n
).
Proposition 27. (The Chinese Remainder Theorem.)
Suppose
m
1
,
m
2
, . . . ,
m
n
are pairwise relatively prime. Then the system of congruences
x
a
1
(mod
m
1
)
x
a
3
(mod
m
3
)
...
x
a
n
(mod
m
n
)
has a unique solution modulo
M
=
m
1
m
2
...
m
n
, namely,
x
a
1
M
1
y
1
+
a
2
M
2
y
2
+ . . . +
a
n
M
n
y
n
(mod
M
)
Search WWH ::
Custom Search