Cryptography Reference
In-Depth Information
The previous formula can be used to solve these types of quadratic congruences, but
often it is easier to complete the square yourself and simplify as you proceed.
E
XAMPLE
.
We wish to solve the congruence
2
+ 10
3
x
x
+ 7
1 (mod 19).
Move the 7 to the RHS:
2
+ 10
3
x
x
6
13 (mod 19).
Multiply both sides by 13, an inverse of 3 modulo 19:
2
+ 10
2
+ 13
x
13
x
13
3
x
10
x
13
13
169
17 (mod 19).
)
2
to both sides. 10 is an inverse of 2 modulo 19:
Now, add (10
13
2
2
+ 10
10)
2
10)
2
17 + 8
2
x
13
x
+ (10
13
17 + (16
5 (mod 19).
Write the LHS as a square:
10)
2
+ 8)
2
(
x
+ 10
13
(
x
5 (mod 19).
+ 8)
2
Proposition 30 gives us the solutions to (
x
5 (mod 19); they are
5
(19
1)/4
5
5
x
+ 8
9 (mod 19), or
x
9
8 (mod 19).
This yields the two solutions
x
1 (mod 19), and
x
17
2 (mod 19).
You should verify that each of the solutions is correct. We will solve this congruence
once again however, this time using the quadratic formula:
)
2
))
(
p
1)/4
x
(
a
((2
b
ac
2
ab
(mod
p
).
The congruence to solve is
2
+ 10
3
x
x
+ 7
1 (mod 19),
or in standard form,
2
+ 10
3
x
x
+ 6
0 (mod 19),
so
a
= 10.
Substituting these values into (††) we get
= 3,
b
= 10,
c
= 6,
a
= 13, and 2
10)
2
6))
(19
1)/4
x
=
(13((10
13
10
13
10
6))
5
(13(10000
13
8
(13(15))
5
8
5
5
8
9
8 (mod 19).
Search WWH ::
Custom Search