Cryptography Reference
In-Depth Information
Algorithm 2 for calculating a simultaneous solution of a system of linear
congruences
x ≡ a
i
mod
m
i
,
1
≤ i ≤ r
, with
gcd (
m
i
,m
j
)=1
for
i
=
j
1.
Set
i ←
1
,
m ← m
1
,and
x ← a
1
.
2.
If
i
=
r
, output
x
and terminate the algorithm. Otherwise, increase
i ← i
+1
and calculate
u
and
v
with
1=
um
+
vm
i
using the extended Euclidean
algorithm (cf. page 179).
3.
Set
x ← uma
i
+
vm
i
x
,
m ← mm
i
,
x ← x
mod
m
andgotostep2.
The algorithm immediately becomes understandable if we carry out the
computational steps for three equations
x
=
a
i
mod
m
i
,
i
=1
,
2
,
3
:For
i
=2
we have in step 2
1=
u
1
m
1
+
v
1
m
2
and in step 3
x
1
=
u
1
m
1
a
2
+
v
1
m
2
a
1
mod
m
1
m
2
.
Inthenextpassthroughtheloopwith
i
=3
the parameters
a
3
and
m
3
are
processed. In step 2 we then have
1=
u
2
m
+
v
2
m
3
=
u
2
m
1
m
2
+
v
2
m
3
and in step 3
x
2
=
u
2
ma
3
+
v
2
m
3
x
1
mod
mm
1
=
u
2
m
1
m
2
a
3
+
v
2
m
3
u
1
m
1
a
2
+
v
2
m
3
v
1
m
2
a
1
mod
m
1
m
2
m
3
.
The summands
u
2
m
1
m
2
a
3
and
v
2
m
3
u
1
m
1
a
2
disappear in forming
the residue
x
2
modulo
m
1
; furthermore,
v
2
m
3
≡ v
1
m
2
≡
1mod
m
1
by
construction, and thus
x
2
a
1
mod
m
1
solves the first congruence. Analogous
considerations lead us to see that
x
2
also solves the remaining congruences.
We shall implement this inductive variant of the construction principle ac-
cording to the Chinese remainder theorem in the following function
chinrem_l()
,
whose interface enables the passing of coefficients of a variable number of
congruences. For this a vector with an even number of pointers to
CLINT
objects
is passed, which in the order
a
1
,m
1
,a
2
,m
2
,a
3
,m
3
,...
are processed as
coefficients of congruences
x
≡
a
i
mod
m
i
. Since the number of digits of the
solution of a congruence system
x ≡ a
i
mod
m
i
is of order
i
log (
m
i
)
, the
procedure is subject to overflow in its dependence on the number of congruences
and the size of the parameters. Therefore, such errors will be noted and indicated
in the return value of the function.
≡
