Cryptography Reference
In-Depth Information
CHAPTER
9
Quadratic Congruences
9.1
QUADRATIC CONGRUENCES MODULO A PRIME
The type of congruences we will first investigate here are those of the form
x
2
a
(mod
p
)
p
where
is prime. (Later on, we will allow the modulus to be composite.) Not all such con-
gruences have solutions; for example,
x
2
5 (mod 11)
x
x
has two solutions,
4 (mod 11), and
4
7 (mod 11). (Verify.) But the congruence
2
2 (mod 5)
has no solutions. (Verify by trying all values from 0 through 4.) It turns out that such con-
gruences either have no solutions, or exactly two, as the next theorem shows.
x
2
PROPOSITION 28.
If
p
is an odd prime and
p
a
, then the congruence
x
a
(mod
p
)
has either no solutions or exactly two incongruent solutions modulo
p
.
2
Proof.
Suppose the congruence has a solution, say
x
=
z
; that is,
z
a
(mod
p
). Then
)
2
2
clearly,
x
=
z
is also a solution, since (
z
=
z
a
(mod
p
). Also,
z
z
(mod
p
),
because if
z
z
(mod
p
), this would imply that 2
z
0 (mod
p
), which cannot be because
2
p
is odd and does not divide
).
Now we must show these two solutions (when they exist) are the only solutions. Suppose
z
(since
z
a
(mod
p
) and
p
a
2
2
x
=
z
,
x
=
y
are two solutions to this quadratic congruence, hence
z
y
a
(mod
p
) and
2
2
= (
so
z
y
z
+
y
)(
z
y
)
a
a
0 (mod
p
). This says that
p
|(
z
+
y
) or
p
|(
z
y
), which
further implies then that
z
y
(mod
p
) or
z
y
(mod
p
). Either way, we are left with only
two distinct solutions,
x
z
(mod
p
) and
x
z
(mod
p
).
Note that the previous only applies to odd primes, so quadratic congruences modulo 2
(the only even prime) are handled somewhat differently. We will not have occasion to do
this.
Search WWH ::
Custom Search