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