Cryptography Reference
In-Depth Information
for any
is also a solution to the individual congruences of the system. To show this
solution is unique (in the sense that all other solutions are congruent to it modulo
k
. That is,
x
M
), let
x
and
y
both be simultaneous solutions to the previous system. Note now that we have
x
y
a
k
(mod
m
k
)
∀
k
, and proposition 26 tells us then that
x
y
(mod
M
), as desired.
E
XAMPLE
.
We'll use the Chinese Remainder Theorem (CRT) to solve the same system (*);
that is, the system
x
3 (mod 4)
x
0 (mod 5)
x
0 (mod 7)
x
8 (mod 9).
(Note that the moduli are pairwise relatively prime.) The proof of CRT shows us how to get
our solutions very quickly by computing
M
= 4
5
7
9 = 1260, and
M
1
= 1260/4 = 315,
M
2
= 1260/5 = 252,
M
3
= 1260/7 = 180,
M
4
= 1260/9 = 140.
We then compute inverses
y
i
of each
M
i
modulo
m
i
:
M
1
= 3 (an inverse of 315 modulo 4)
M
2
= 3 (an inverse of 252 modulo 5)
M
3
= 3 (an inverse of 180 modulo 7)
M
4
= 2 (an inverse of 140 modulo 9)
To get our solution, we now simply form the sum
x
=
a
1
M
1
M
1
+
a
2
M
2
M
2
+
a
3
M
3
M
3
+
a
4
M
4
M
4
= 3
315
3 + 0
252
3 + 0
180
7 + 8
140
2
= 5075
35 (mod 1260).
This is exactly the same solution we obtained earlier, only perhaps less directly but cer-
tainly more quickly. (Note that computing
M
2
,
M
3
,
y
2
and
y
3
isn't even necessary in this
example, because they vanish in the final computation.)
Java Algorithm.
Suppose we write a static method in the BigIntegerMath class to
solve such sets of congruences; we can call it solveCRT(). We can make it solve systems of
the form
Search WWH ::
Custom Search