Cryptography Reference
In-Depth Information
Proof.
a) From FLT, we have
g
p
1
1 (mod
p
). Since
g
is a generator modulo
p
, no smaller power
of
g
is congruent to 1 modulo
p
, and thus log1 =
p
1
0 (mod
p
1).
b) Note that from the definition of discrete logarithms,
log(
ab
)
ab
(mod
p
),
g
and
log
a
log
b
log
a
log
b
g
ab
(mod
p
).
g
g
Thus,
log
a
log
b
(mod
p
),
and by using proposition 38, we conclude that
log(
ab
)
g
g
log(
ab
)
log
a
+ log
b
(mod
p
- 1)
c) Exercise.
E
XAMPLES
.
Take the prime
p
= 13, and note that 2 is a generator modulo 13 (this is easily
checked). Note that since 2
0
2
12
1 (mod 13) by FLT, we have
log
2,13
1 =12
0 (mod 12).
Also, note that
log
2,13
12 = 6,
log
2,13
9 = 8, and
log
2,13
(9
12) = log
2,13
(108) = log
2,13
(4) = 2.
(Since 108
4 modulo 13.)
This gives us
log
2,13
(9
12) = 2
6 + 8 = log
2,13
12 + log
2,13
9 (mod 12).
Also, note that
10
log
2,13
12 = 10
6 = 60,
and
log
2,13
12
10
= log
2,13
61917364224 = log
2,13
1 = 12.
(Since 61917364224
1 modulo 13.)
This yields
log
2,13
12
10
= 12
60 = log
2,13
12
10
(mod 12).
0
Search WWH ::
Custom Search