Cryptography Reference
In-Depth Information
In this example,
n
1
=7,
n
2
=11,
n
3
=13(note that these integers are
pairwise co-prime), and
n
=7
13 = 1001.Furthermore,
a
1
=5,
a
2
=3,and
a
3
=10. To determine the solution
x
in
·
11
·
Z
1001
, one must compute
m
1
=
1001
/
7 = 143
m
2
=
1001
/
11 = 91
m
3
=
1001
/
13 = 77
and
143
−
1
(mod 1001) = 5
y
1
≡
91
−
1
(mod 1001) = 4
y
2
≡
77
−
1
(mod 1001) = 12
y
3
≡
After this preparation, the solution
x
can be computed as follows:
k
x
≡
a
i
m
i
y
i
(mod
n
)
i
=1
≡
a
1
m
1
y
1
+
a
2
m
2
y
2
+
a
3
m
3
y
3
(mod
n
)
≡
5
·
143
·
5+3
·
91
·
4+10
·
77
·
12 (mod 1001)
≡
3575 + 1092 + 9240 (mod 1001)
≡
13907 (mod 1001)
=
894
Consequently,
x
= 894 is the solution in
Z
1001
,and
{
i
∈
Z
|
894 +
i
·
1001
}
is the set of all solutions in
.
The case
k
=2is so important in practice that we have a closer look at the
corresponding CRA. The system of congruences looks as follows:
Z
x
≡
a
1
(mod
n
1
)
x
≡
a
2
(mod
n
2
)
Again, the moduli
n
1
and
n
2
must be co-prime (i.e.,
gcd
(
n
1
,n
2
)=1). We
compute
