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