Cryptography Reference
In-Depth Information
where
ζ
=
e
2
πi/d
. Fix
a
and
d
with
ad
=
N
.
CLAIM 10.13
d−
1
d
P
(
ζ
b
e
2
πiaτ/d
)) =
p
k
(
e
2
πiaτ/d
)
X
k
(
X
−
b
=0
k
=0
isapolynom ialin
X
w hose coe cients
p
k
are Laurent series in
e
2
πiaτ/d
with
integer coe cients.
In the statement of the claim and in the following, a Laurent series will
always be one with only finitely many negative terms (in other words, a power
series plus finitely many terms with negative exponents). Everything in the
claim is obvious except the fact that the coe
cients of the Laurent series
p
k
are integers. One proof of this is as follows. The coe
cients of each
p
k
lie in
Z
[
ζ
]. The Galois group of
Q
(
ζ
)
/
Q
permutes the factors of the product, hence
leaves the coecients of
p
k
unchanged. Therefore, they are in
Q
. But the
elements of
Z
[
ζ
]
∩
Q
are algebraic integers in
Q
, hence are in
Z
.Thisproves
the claim.
For a proof of the claim that does not use Galois theory, consider the matrix
⎛
⎞
010
···
0
001
···
0
.
⎝
⎠
Z
=
.
.
.
.
.
.
.
100
···
0
Let 0
≤
b<d
and let
⎛
⎞
1
ζ
b
ζ
2
b
.
ζ
b
(
d−
1)
⎝
⎠
v
b
=
.
Then
Zv
b
=
ζ
b
v
b
. It follows that
P
(
e
2
πiaτ/d
Z
)
v
b
=
P
(
ζ
b
e
2
πiaτ/d
)
v
b
.
Therefore, the numbers
P
(
ζ
b
e
2
πiaτ/d
), for 0
≤ b<d
, are a complete set of
eigenvalues for the
d×d
matrix
P
(
e
2
πiaτ/d
Z
), so the characteristic polynomial
is
d
−
1
P
(
ζ
b
e
2
πiaτ/d
))
.
(
X
−
b
=0
But the entries of the matrix
P
(
e
2
πiaτ/d
Z
) are Laurent series in
e
2
πiaτ/d
with
integer coecients. Therefore, the coecients of the characteristic polynomial
are power series in
e
2
πiaτ/d
with integer coe
cients. This proves the claim.
Search WWH ::
Custom Search