Cryptography Reference
In-Depth Information
E
XAMPLES
.
We will solve all of the following congruences. Note that the modulus is prime
and congruent to 3 modulo 4.
2
•
x
2 (mod 23)
Solutions:
x
2
(23
1)/4
=
2
6
=
64
5 (mod 23)
If you prefer to always use least nonnegative residues, the solutions are:
x
5 (mod 23), and
x
5
18 (mod 23)
2
•
x
17 (mod 19)
Solutions:
x
17
(19
1)/4
=
17
5
6 (mod 19)
2
•
x
2 (mod 7)
Solutions:
x
2
(7
1)/4
=
2
2
4 (mod 7)
9.3
QUADRATIC CONGRUENCES MODULO A COMPOSITE
We are now ready to attempt solving congruences when the modulus is not prime. Let
n
=
pq
, where
p
and
q
are distinct primes of the form 4
k
+ 3, and consider the congruence
2
x
a
(mod
n
)
(*)
where 0 <
a
<
n
. Suppose (*) has a solution, say
x
=
y
. Then it has four solutions, accord-
ing to the following proposition.
PROPOSITION 31.
Let
n
=
pq
where
p
and
q
are primes congruent to 3 modulo 4, and
let
a
be an integer such that 0 <
a
<
n
. Suppose the equation
x
2
a
(mod
n
) has a solution.
Then all the solutions are given by
x
(
zqq
p
wpp
q
) (mod
n
)
(
p
1)/4
,
w
=
a
(
q
1)/4
,
q
p
is an inverse of
q
modulo
p
, and
p
q
is an inverse of
p
mod-
where
z
=
a
ulo
q
.
Proof.
We will show it has exactly four solutions as follows. Note that
x
=
y
are solu-
2
2
2
tions to
x
a
(mod
n
) iff they are solutions to both
x
a
(mod
p
) and
x
a
(mod
q
).
This is easy enough to see if you use the definition of congruence:
2
y
is a solution to
x
a
(mod
n
)
2
iff
y
a
(mod
n
)
2
iff
n
|(
y
a
)
2
2
iff
p
|(
y
a
) and
q
|(
y
a)
(since
n
=
pq
and clearly
p
|
n
and
q
|
n
)
2
2
iff
y
a
(mod
p
) and
y
a
(mod
q
)
2
2
iff
y
is a solution to both
x
a
(mod
p
) and
x
a
(mod
q
)
Search WWH ::
Custom Search