Cryptography Reference
In-Depth Information
CHAPTER
13
Exponential Congruences
This chapter involves solving congruences of the form
a
x
b
(mod
n
)
for
x
. If there is a solution for
x
, we call
x
a discrete logarithm modulo
n
of
a
to the base
b
,
and we write
x
= log
b
,
n
a
.
When the modulus
n
is clear from the context, we often simply write
x
= log
b
a
.
is a large prime, these congruences can be very difficult to solve; this is formally
known as the discrete logarithm problem, or DLP. To help us understand the nature of these
problems, we'll need to do some development. As a review, recall Fermat's Little Theo-
rem:
If
p
If p is prime, and b is an integer such that p
b, then
b
p
1
1 (mod p).
b
z
be congruent to 1 modulo
However, could
p
for some value
z
smaller than
p
1? We
can see this is possible just from the following simple example: let
= 7, and examine the
powers of each integer greater than 0 but less than 7. (See Table 13.1.)
Note that the integers 2, 4, and 6 (and also 1, obviously), yield powers which are con-
gruent to 1 modulo 7 for values smaller than 6.
p
Search WWH ::
Custom Search