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