Cryptography Reference
In-Depth Information
which yields the four solutions
x
122
45 (mod 77),
or
10 (mod 77).
(Here 2 is an inverse of 11 mod 7, and 8 is an inverse of 7 mod 11.) If you prefer to have
the solutions in terms of least nonnegative residues modulo
x
n
, they are
x
45 (mod 77),
x
32 (mod 77),
x
10 (mod 77),
x
67 (mod 77).
2
You should verify that each solution satisfies the congruence
x
23 (mod 77).
We see from the previous development that solving quadratic congruences when the
modulus is not prime involves obtaining the prime factorization of
, solving the congru-
ences for the prime moduli, and then recombining the solutions using CRT. This will work
even when the solutions we seek are for quadratic congruences more complicated than the
simple congruence
n
2
).
To continue with this, we will now consider quadratic congruences of the form
x
a
(mod
p
2
+
ax
bx
+
c
0 (mod
p
)
where
. Solving such a congru-
ence can go quickly by completing the square, almost the same way we do in algebra. First,
multiply both sides by an inverse of
p
is a prime of the form 4
k
+ 3, and
a
is not divisible by
p
a
modulo
p
. This inverse exists because (
a
,
p
) = 1:
2
+
x
abx
+
ac
0 (mod
p
).
Now move
ac
to the RHS:
2
+
x
abx
ac
(mod
p
).
Next, add the exact quantity to both sides to make the LHS a perfect square:
2
+
)
2
)
2
(mod
x
abx
+ (2
ab
ac
+ (2
ab
p
).
The value desired is 2
ab
, where 2
is an inverse of 2 modulo
p
, which exists since
p
is
an odd prime. Now, rewrite the LHS as a square, and factor the RHS:
)
2
)
2
(
x
+ 2
ab
a
((2
b
ac
) (mod
p
).
Proposition 30 now tells us the solutions to the previous congruence:
)
2
))
(
p
1)/4
(mod
x
+ 2
ab
(
a
((2
b
ac
p
).
Thus, we finally arrive at our solutions for
x
:
)
2
))
(
p
1)/4
x
(
a
((2
b
ac
2
ab
(mod
p
).
Search WWH ::
Custom Search