Cryptography Reference
In-Depth Information
9.2
FERMAT'S LITTLE THEOREM
How do we find solutions to quadratic congruences? When the modulus is a prime of the
form 4
k
+ 3, that is, congruent to 3 modulo 4, these solutions are easily obtained. But before
we do this, we must first prove Fermat's Little Theorem, an extremely useful result.
PROPOSITION 29. (FERMAT'S LITTLE THEOREM.)
p
b
Let
be prime and
an inte-
p
b
b
p
1
p
ger such that
. Then
1 (mod
).
Proof.
p
b
b
p
b
p
kb
Note first that
divides none of the integers
, 2
, . . . , (
1)
, for if
|
for
k
p
p
k
p
b
some
between 1 and
1 (inclusive), then by proposition 13,
|
since
, and this is
b
b
p
b
impossible. Now we want to show that no two of the integers
, 2
, . . . , (
1)
are con-
p
gruent modulo
. Assume two of them are; that is,
jb
kb
p
≤
j
k
≤
p
(mod
) where 1
<
1.
j
k
p
b
p
Then proposition 21 says
(mod
) since
and
are relatively prime. But this can-
j
k
p
not be since
and
are positive integers both less than
1.
p
Thus, the sequence of integers 1, 2, . . . ,
1 has the same number of members as the
b
b
p
b
p
sequence
, 2
, . . . , (
1)
, and the least nonnegative residues of the latter (modulo
)
p
must therefore be a permutation of 1, 2, . . . ,
1. Thus we must have
p
b
b
p
b
p
1
2 . . . (
1)
2
. . . (
1)
(mod
), or
p
b
p
1
(
p
p
(
1)!
1)! (mod
).
p
p
, we can divide it out and preserve the congruence
by proposition 21. This yields the desired result; namely,
Since (
1)! is relatively prime to
b
p
1
p
1 (mod
).
x
2
a
p
p
is a prime congruent to 3 mod-
ulo 4. These solutions are in the next proposition, which you can prove quickly with the aid
of Fermat's Little Theorem. Solutions to quadratic congruences when the modulus is a prime
of the form 4
Now we can find the solutions to
(mod
) when
k
+ 1 are more difficult to obtain, and we will not cover such congruences
here.
PROPOSITION 30.
p
a
Let
be a prime congruent to 3 modulo 4, and
an integer such that
p
a
x
2
a
p
x
a
(
p
1)/4
(mod
p
. Then if the congruence
(mod
) has solutions, they are
),
x
a
(
p
1)/4
(mod
p
and
).
(Hint: First show that
a
(
p
1)/2
p
); this is called Euler's criterion. It may not
be clear to you when proving proposition 30 why
1 (mod
p
must be congruent to 3 modulo 4; it is
p
simply the only way (
+ 1)/4 can be an integer.)
Search WWH ::
Custom Search