Cryptography Reference
In-Depth Information
Note that 21 = 3
7. The congruence is already in standard form, so we have
a
= 2,
b
=
)
2
))
(3
1)/4
(mod
3,
c
= 16,
a
= 11, and 2
= 11. We first calculate the quantities
(
a
((2
b
ac
)
2
))
(7
1)/4
(mod 7), and 2
3),
(
a
((2
b
ac
ab
(mod 3 and mod 7):
)
2
))
(3
1)/4
(
a
((2
b
ac
3)
2
11
16))
(3
1)/4
(11((11
0)
2
2
1))
(3
1)/4
(2((2
2 (mod 3).
)
2
))
(7
1)/4
(
a
((2
b
ac
3)
2
11
16))
(7
1)/4
(11((11
3)
2
4
2))
(7
1)/4
(4((4
0 (mod 7).
2
ab
11
11
3
2
2
0
0 (mod 3)
2
ab
11
11
3
4
4
3
6 (mod 7)
The four solutions we seek (actually two, because of
0 below) are then
x
(
1
0)
7
1 + (
0
6)
3
5 (mod 21).
Here, 1 is an inverse of 7 mod 3, and 5 is an inverse of 3 mod 7. If we provide the answers
in terms of least nonnegative residues, we get
x
7
6
1 (mod 21),
x
7
6
13
8 (mod 21).
The methods we have discussed here can be easily extended to solve quadratic congru-
ences modulo
p
n
where the factors are all distinct primes congruent to 3 mod-
ulo 4. You may wish to attempt this.
n
=
p
1
p
2
...
Java Algorithm.
We should write a solveQuadratic() method (in the BigIntegerMath
class, of course) to solve quadratic congruences of the forms described above. That is, the
Search WWH ::
Custom Search