Cryptography Reference
In-Depth Information
represents column
j
in the state matrix, then
c
(
x
)
⊗
a
(
x
) can be represented by
the matrix product:
2311
1231
1123
3112
a
0
,j
a
1
,j
a
2
,j
a
3
,j
b
0
b
1
b
2
b
3
CA
j
=
=
=
B,
where the matrix
A
j
is column
j
of the state matrix and
C
is the
circulant
matrix
representing
c
(
x
). Hence, each column
A
j
of the state matrix is multiplied in
this fashion by
C
. For instance, if
a
(
x
)=
x
3
+1
,
then
a
(
x
)=5
x
3
+4
x
2
+2
x
+3
,
which is given by the matrix product:
⊗
c
(
x
)
2311
1231
1123
3112
1
0
0
1
3
2
4
5
=
=
B,
D.2 Silver-Pohlig-Hellman
The next algorithm is the Silver-Pohlig-Hellman algorithm for finding dis-
crete logs, which first appeared in 1978 (see [187]).
We discussed issues sur-
rounding this algorithm on page 165.
Silver-Pohlig-Hellman Algorithm for Computing Discrete Logs
Let
α
be a generator of
F
p
and let
β
∈
F
p
, and assume that we have a
factorization
r
p
a
j
j
p
−
1=
a
j
∈
N
,
j
=1
where the
p
j
are distinct primes. The technique for computing
e
= log
α
β
is
to compute
e
modulo
p
a
j
j
for
j
=1
,
2
,...,r
, then apply the Chinese remainder
theorem (see Theorem A.12 on page 478 in Appendix A). Since we operate on
each prime power
p
a
j
, we replace
p
j
with
q
for simplicity in what follows, and
simply refer to
q
a
with the understanding that we are operating on each of the
r
prime powers in this fashion. To compute
e
modulo
q
a
we need to determine
e
in its base
q
representation:
a
−
1
b
i
q
i
e
=
where 0
≤
b
i
≤
q
−
1 for 0
≤
i
≤
a
−
1
.
i
=0
Search WWH ::
Custom Search