Cryptography Reference
In-Depth Information
and since
m
j
u
j
≡
0mod
m
i
for
i
=
j
, we obtain
r
m
j
u
j
a
j
≡ m
i
u
i
a
i
≡ a
i
mod
m
i
,
x
0
≡
(10.19)
j
=1
and in this way have constructed a solution to the problem. For two solutions
x
0
x
1
mod
m
i
.Thisis
equivalent to the difference
x
0
− x
1
being simultaneously divisible by all
m
i
,that
is, by the least common multiple of the
m
i
. Due to the pairwise relative primality
of the
m
i
we have that the least common multiple is, in fact, the product of the
m
i
,sothatfinally,wehavethat
x
0
≡
a
i
mod
m
i
and
x
1
≡
a
i
mod
m
i
we have
x
0
≡
x
1
mod
m
holds.
We now apply the Chinese remainder theorem to obtain a solution of
≡
x
2
≡ a
mod
rs
with
gcd(
r, s
)=1
,where
r
and
s
are distinct odd primes and
neither
r
nor
s
is a divisor of
a
, on the assumption that we have already obtained
roots of
y
2
≡ a
mod
r
and
z
2
≡ a
mod
s
. We now construct as above a common
solution to the congruences
x ≡ y
mod
r,
x ≡ z
mod
s,
by
x
0
:= (
zur
+
yvs
)mod
rs,
where
1=
ur
+
vs
is the representation of the greatest common divisor of
r
and
s
. We thus have
x
0
≡ a
mod
r
and
x
0
≡ a
mod
s
, and since
gcd(
r, s
)=1
,we
also have
x
0
≡
a
mod
rs
, and so we have found a solution of the above quadratic
congruence. Since as shown above every quadratic congruence modulo
r
and
modulo
s
possesses two solutions, namely
±
y
and
±
z
, the congruence modulo
rs
has four solutions, obtained by substituting in
±y
and
±z
above:
x
0
:=
zur
+
yvs
mod
rs,
(10.20)
x
1
:=
−
zur
−
yvs
mod
rs
=
−
x
0
mod
rs,
(10.21)
x
2
:=
−zur
+
yvs
mod
rs,
(10.22)
x
3
:=
zur − yvs
mod
rs
=
−x
2
mod
rs.
(10.23)
We have thus found in principle a way to reduce the solution of quadratic
congruences
x
2
a
mod
n
with
n
odd to the case
x
2
≡
≡
a
mod
p
for primes
p
.
For this we determine the prime factorization
n
=
p
k
1
···p
k
t
and then calculate
the roots modulo the
p
i
, which by the recursion in Section 10.4.2 can be used to
obtain solutions of the congruences
x
2
≡ a
mod
p
k
i
. As the crowning glory of
all this we then assemble these solutions with the help of the Chinese remainder
theorem into a solution of
x
2
1
≡ a
mod
n
. The function that we give takes this
path to solving a congruence
x
2
≡ a
mod
n
. However, it assumes the restricted
hypothesis that
n
=
p · q
is the product of two odd primes
p
and
q
, and first
