Cryptography Reference
In-Depth Information
This yields
x
1 (mod 19), and
x
17
2 (mod 19), the same solutions obtained by
completing the square.
We are finally ready to solve the type of congruence which we will find most useful;
those of the type
2 +
ax
bx
+
c
0 (mod
n
)
where (
a
,
n
) = 1,
n
=
pq
, and where
p
and
q
are both primes congruent to 3 modulo 4.
PROPOSITION 32.
Let
n
=
pq
, where
p
and
q
are primes congruent to 3 modulo
n
.
Suppose
a
is an integer relatively prime to
n
, and that the congruence
2 +
ax
bx
+
c
0 (mod
n
)
has a solution. Then all the solutions are given by
) 2
)) ( p 1)/4 )
) 2
)) ( q 1)/4 )
x
(
(
a
((2
b
ac
qq p
+ (
(
a
((2
b
ac
pp q
2
ab
(mod
n
).
(Again,
q p
means an inverse of
q
modulo
p
, and
p q
is an inverse of
p
modulo
q
.)
Proof.
Most of the work involved in finding the solutions has already been done. As
before, use some algebra to rewrite the congruence as
) 2
) 2
(
x
+ 2
ab
a
((2
b
ac
) (mod
n
).
As before, this splits up into two congruences
) 2
) 2
(
x
+ 2
ab
a
((2
b
ac
) (mod
p
), and
) 2
) 2
(
x
+ 2
ab
a
((2
b
ac
) (mod
q
),
and proposition 30 tells us the solutions:
) 2
)) ( p 1)/4 (mod
x
+ 2
ab
(
a
((2
b
ac
p
), and
) 2
)) ( q 1)/4 (mod
x
+ 2
ab
(
a
((2
b
ac
q
)
2 +
We then use CRT to recombine these solutions and obtain solutions to
ax
bx
+
c
0
(mod
n
):
) 2
)) ( p 1)/4 )
) 2
)) ( q 1)/4 )
x
+ 2
ab
(
(
a
((2
b
ac
qq p
+ (
(
a
((2
b
ac
pp q
(mod
n
),
or
) 2
)) ( p 1)/4 )
) 2
)) ( q 1)/4 )
x
(
(
a
((2
b
ac
qq p
+ (
(
a
((2
b
ac
pp q
2
ab
(mod
n
).
Here
q p
is an inverse of
q
modulo
p
, and
p q
is an inverse of
p
modulo
q
. These are the
values claimed in the proposition.
The formula may appear quite horrifying at first, but it provides the solutions we seek
very nicely. We demonstrate this now:
E XAMPLE .
We solve the congruence
2 + 3
2
x
x
+ 16
0 (mod 21).
 
Search WWH ::




Custom Search