Cryptography Reference
In-Depth Information
Algorithm 1 for 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
u ← a
1
,
x ← u
,and
i ←
2
.
2.
Set
C
i
←
1
,
j ←
1
.
3.
Set
u ← m
−
j
mod
m
i
(computed by means of the extended Euclidean
algorithm; see page 181) and
C
i
← uC
i
mod
m
i
.
4.
Set
j ← j
+1
;if
j ≤ i −
1
, go to step 3.
5.
Set
u ←
(
a
i
− x
)
C
i
mod
m
i
,
and
x ← x
+
u
i
−
1
j
=1
m
j
.
6.
Set
i ← i
+1
;if
i ≤ r
, go to step 2. Otherwise, output
x
.
It is not obvious that the algorithm does what it is supposed to, but this can
be shown by an inductive argument. To this end let
r
=2
. In step 5 we then have
x
=
a
1
+((
a
2
− a
1
)
u
mod
m
2
)
m
1
.
It is seen at once that
x ≡ a
1
mod
m
1
.However,wealsohave
x ≡ a
1
+(
a
2
− a
1
)
m
1
m
−
1
mod
m
2
≡ a
2
mod
m
2
.
1
To finish the induction by passing from
r
to
r
+1
we assume that the algorithm
returns the desired result
x
r
for some
r ≥
2
, and we append a further congruence
x
≡
a
r
+1
mod
m
r
+1
. Then by step 5 we have
x
r
+
(
a
r
+1
mod
m
r
+1
r
r
m
−
1
x
≡
−
x
)
·
m
j
.
j
j
=1
j
=1
Here we have
x ≡ x
r
≡ a
i
mod
m
i
for
i
=1
,...,r
according to our assumption.
But we also have
x ≡ x
r
+
(
a
r
+1
− x
)
r
r
m
−
1
m
j
·
≡ a
r
+1
mod
m
r
+1
,
j
j
=1
j
=1
which completes the proof.
For the application of the Chinese remainder theorem in programs
one function would be particularly useful, one that is not dependent on a
predetermined number of congruences, but rather allows the number of
congruences to be specified at run time. This method is supported by an
adaptation of the above construction procedure, which does not, alas, have the
advantage that reduction need take place only modulo
m
i
, but it does make it
possible to process the parameters
a
i
and
m
i
of a system of congruences with
i
=1
,...,r
with variable
r
with a constant memory expenditure. Such a solution
is contained in the following algorithm from [Cohe], Section 1.3.3.
