チェビシェフ多項式の
チェビシェフ多項式の
チェビシェフ多項式の
チェビシェフ多項式の 2
2
2
2 変数への拡張と公開鍵暗号
変数への拡張と公開鍵暗号
変数への拡張と公開鍵暗号
変数への拡張と公開鍵暗号（
（
（
（ElGamal
ElGamal
ElGamal
ElGamal 暗号）への応用
暗号）への応用
暗号）への応用
暗号）への応用
Ⅰ
Ⅰ
Ⅰ
Ⅰ....チェビシェフ
チェビシェフ
チェビシェフ
チェビシェフ((((Chebyshev
Chebyshev
Chebyshev
Chebyshev))))の多項式
の多項式
の多項式
の多項式
)
(
2
1
cos
θ
=
e
iθ+
e
−iθ より)
(
2
1
cos
n
θ
=
e
inθ+
e
−inθ であるから)
)(
(
4
1
cos
cos
θ
n
θ
=
e
iθ+
e
−iθe
inθ+
e
−inθ)
(
4
1
( +1)θ+
−( +1)θ+
( −1)θ+
−( −1)θ=
in in in ine
e
e
e
}
)
1
cos(
)
1
{cos(
2
1
θ
θ
+
−
+
=
n
n
よって0
)
1
cos(
cos
cos
2
)
1
cos(
n
+
θ
−
θ
n
θ
+
n
−
θ
=
ここでθ
n
a
n=
cos
，x
=
cos
θ
とおくと0
2
1 1−
⋅
+
−=
+ n n nx
a
a
a
したがって n n nx
a
a
a
+2=
2
⋅
+1−
が成り立つ。 この漸化式とa
0=
1
,
a
1=
x
であることより，a
nは x の多項式となることがわかる。)
(x
T
a
n=
n とおく。これをチェビシェフの多項式という。 ここで))
(
cos(
)
cos(
mn
θ
=
m
n
θ
であるから，y
n
θ
=
cos
とおくと，)
(
)
(
x
T
y
T
mn=
m)
(x
T
y
=
n であるから))
(
(
)
(
x
T
T
x
T
mn=
m n したがって))
(
(
))
(
(
)
(
x
T
T
x
T
T
x
T
mn=
m n=
n m が成り立つ。 上記の議論は，(
)
2
1
cosh
θ
=
e
θ+
e
−θ についても成り立ち， －1≦x≦1 のときT
n(
x
)
=
cos(
n
arccos(
x
))
x≧1 のときT
n(
x
)
=
cosh(
n
arccos
h
(
x
))
x≦－1 のとき
T
n(
x
)
=
(
−
1
)
ncosh(
n
arccos
h
(
−
x
))
である。 上記の事柄は，t の 2 次方程式0
1
2
2− xt
+
=
t
の 2 解をα
,
β
とすると)
(
2
1
β
α
+
=
x
，αβ
=
1
となるから)
(
2
1
n n na
=
α
+
β
とおいても得られる。Ⅱ
Ⅱ
Ⅱ
Ⅱ....チェビシェフの多項式の任意の体への拡張
チェビシェフの多項式の任意の体への拡張
チェビシェフの多項式の任意の体への拡張
チェビシェフの多項式の任意の体への拡張
次に，任意の体 K で考える。GF(2)では 2＝0 であるので，2 次方程式0
1
2
2− xt
+
=
t
では GF(2)の拡大体上で不都合が生じる。2 次方程式を次のように変えて考える。 t の 2 次方程式0
1
2− xt
+
=
t
の 2 解をα，βとすると，解と係数の関係により α+β＝x，αβ＝1 ただし，この方程式が K 上に解を持たない場合は，この 2 次方程式による K の拡大体を考える。 n n na
=
α
+
β
とおく。 na
は，漸化式0
1 2−
⋅
++
=
+ n n nx
a
a
a
を満たす。このとき2
0 0 0=
α
+
β
=
a
，a
1=
α
+
β
=
x
逆にx
a
a
0=
2
,
1=
n n nx
a
a
a
+2=
⋅
+1−
（n は負でない整数） でa
nを定めると，特性方程式方程式t
2− xt
+
1
=
0
の 2 解をα，βとするとき n n na
=
α
+
β
となる。 ちなみに，x
=
2
cos
θ
とすると，a
n=
2
cos
n
θ
となる。 na
は次の性質を満たす。 命題 命題 命題 命題 11112
0=
b
y
a
b
1=
α
n+
β
n=
n=
とし，漸化式b
n+2−
y
⋅
b
n+1+
b
n=
0
（n は負でない整数）でb
nを定めるとき， mn ma
b =
証明 証明 証明 証明 漸化式の特性方程式0
1
2− yt
+
=
t
の 2 解をγ，δとするとb
0,b
1の定め方により m m mb
=
γ
+
δ
また，α
n+
β
n=
y
，α
nβ
n=
(
αβ
)
n=
1
よりα
nβ
n,
はこの特性方程式の解であるから m n m n m m mb
=
γ
+
δ
=
(
α
)
+
(
β
)
=
α
mn+
β
mn=
a
mn 証明終わり 証明終わり 証明終わり 証明終わり}
{
a
n の漸化式とa
0, a
1が x の多項式であることより，a
nは x の多項式となることがわかる。 よって，a
n=
f
n(x
)
とおくと，上記の証明から))
(
(
)
(
y
f
f
x
f
b
m=
m=
m n)
(x
f
a
b
m=
mn=
mn であるから))
(
(
))
(
(
)
(
x
f
f
x
f
f
x
f
mn=
m n=
n m が成り立つことがわかる。 第 第 第 第 nnnn 項の高速計算法項の高速計算法項の高速計算法項の高速計算法 n を任意の自然数とするとき，n を 2 進法で表す。 ps
s
s
s
s
n
=
(
L
(((
0⋅
2
+
1)
⋅
2
+
2)
⋅
2
+
3)
⋅
2
+
L
)
+
ただし，s
iは 0 か 1 の値をとり，s
0≠
0
である。(バイナリー法)x
a
a
0=
2
,
1=
n n nx
a
a
a
+2=
⋅
+1−
（n は負でない整数） とする。 1,
n+ na
a
の組が与えられたとき，a
2n,
a
2n+1の組は次のように求められる。2
)
(
2
)
(
2 2 2 2 2=
+
=
+
−
=
n−
n n n n n na
a
α
β
α
β
αβ
また，)
)(
(
1 1 1 + + +=
n+
n n+
n n na
a
α
β
α
β
)
(
)
(
)
(
α
2 1+
β
2 1+
αβ
α
+
β
=
n+ n+ nx
a
n+
=
2 +1 よってx
a
a
a
2n+1=
n n+1−
これより，
(
a
n,
a
n+1)
の組から)
,
2
(
)
,
(
a
2na
2n+1=
a
n2−
a
na
n+1−
x
)
2
,
(
)
,
(
a
2n+1a
2n+2=
a
na
n+1−
x
a
n+12−
が求まる。この 2 つを繰り返し用いると，a
nを高速に求めることができる。Ⅲ
Ⅲ
Ⅲ
Ⅲ.3
.3
.3
.3 次方程式の解への拡張
次方程式の解への拡張
次方程式の解への拡張
次方程式の解への拡張
体 K での t の 3 次方程式0
1
2 3−
+
−
=
yt
xt
t
…① ただしx ≠
y
の 3 解をα，β，γとする。 ただし，この方程式が K 上に解を持たない場合は，この 3 次方程式による K の拡大体を考える。 解と係数の関係により1
,
,
+
+
=
=
=
+
+
β
γ
αβ
βγ
γα
αβγ
α
x
y
このとき，γ
β
α
1
1
1
+
+
=
y
が成り立つから，①は0
1
1
1
1
)
(
2 3−
=
+
+
+
+
+
−
t
t
t
γ
β
α
γ
β
α
となる。 n n n na
=
α
+
β
+
γ
ただし，n は整数 とおく。n が自然数でなく整数とすることが，ポイントである。3
0=
a
x
a
1=
α
+
β
+
γ
=
y
x
a
2=
α
2+
β
2+
γ
2=
(
α
+
β
+
γ
)
2−
2
(
αβ
+
βγ
+
γα
)
=
2−
2
na
は漸化式0
1 2 3−
⋅
++
⋅
+−
=
+ n n n nx
a
y
a
a
a
（n は整数） を満たす。 逆にy
x
a
x
a
a
0=
3
,
1=
,
3=
2−
2
0
1 2 3−
⋅
++
⋅
+−
=
+ n n n nx
a
y
a
a
a
（n は整数） でa
nを定めると，特性方程式t
3−
xt
2+
yt
−
1
=
0
の 3 解をα，β，γとするとき n n n na
=
α
+
β
+
γ
となる。 na
は次の性質を満たす。 命題 命題 命題 命題 2222n n n n
a
z
=
α
+
β
+
γ
=
n n n n n n na
w
=
+
+
=
+
+
=
−γ
β
α
γα
βγ
αβ
)
(
)
(
)
1
1
1
(
とする。3
0=
b
z
a
b
1=
α
n+
β
n+
γ
n=
n=
w
z
b
2=
α
2n+
β
2n+
γ
2n=
(
α
n+
β
n+
γ
n)
2−
2
{(
αβ
)
n+
(
βγ
)
n+
(
γα
)
n}
=
2−
2
とし，漸化式0
1 2 3−
⋅
++
⋅
+−
=
+ n n n nz
b
w
b
b
b
（n は整数） でb
nを定めるとき， mn ma
b =
証明 証明 証明 証明 漸化式の特性方程式0
1
2 3−
+
−
=
wt
zt
t
の 3 解をλ
,
µ
,
ν
とすると，b
0,
b
1,
b
2の定め方により m m m mb
=
λ
+
µ
+
ν
である。 ま た ，α
n+
β
n+
γ
n=
z
， n n+
n n+
n n=
n+
n+
n=
w
γ
β
α
α
γ
γ
β
β
α
1
1
1
，α
nβ
nγ
n=
(
αβγ
)
n=
1
よ り n n nβ
γ
α
,
,
はこの方程式の解であるから m n m n m n m m m mb
=
λ
+
µ
+
ν
=
(
α
)
+
(
β
)
+
(
γ
)
=
α
mn+
β
mn+
γ
mn=
a
mn 証明終わり 証明終わり 証明終わり 証明終わり}
{
a
n の漸化式とa
0,
a
1,
a
2が x,y の多項式であることより，a
nは x,y の多項式となることがわかる。 よって，a
n=
F
n(
x
,
y
)
とおくと，上記の証明から))
,
(
),
,
(
(
)
,
(
z
w
F
F
x
y
F
x
y
F
b
m=
m=
m n −n)
,
(
x
y
F
a
b
m=
mn=
mn であるから))
,
(
),
,
(
(
))
,
(
),
,
(
(
)
,
(
x
y
F
F
x
y
F
x
y
F
F
x
y
F
x
y
F
mn=
m n −n=
n m −m が成り立つことがわかる。 また，①の両辺をt
3で割ると0
1
1
1
1
3 2+
−
=
−
t
x
t
y
t
となり，これをt
1
の方程式と考えたとき，①と x,y が入れ替わっている。 このことにより，)
,
(
)
,
(
x
y
F
y
x
F
−n=
nが成り立つことがわかる。したがって，
))
,
(
),
,
(
(
))
,
(
),
,
(
(
)
,
(
x
y
F
F
x
y
F
y
x
F
F
x
y
F
y
x
F
mn=
m n n=
n m m が成り立つ。具体的にF
n(
x
,
y
)
を求めてみると，次のようになる。3
)
,
(
0x
y
=
F
x
y
x
F
1(
,
)
=
y
x
y
x
F
2(
,
)
=
2−
2
3
3
)
,
(
3 3x
y
=
x
−
xy
+
F
x
y
y
x
x
y
x
F
4(
,
)
=
4−
4
2+
2
2+
4
y
x
xy
y
x
x
y
x
F
5(
,
)
=
5−
5
3+
5
2+
5
2−
5
3
12
2
6
9
6
)
,
(
6 4 2 2 3 3 6x
y
=
x
−
x
y
+
x
y
+
x
−
y
−
xy
+
F
第 第 第 第 nnnn 項の高速計算法項の高速計算法項の高速計算法項の高速計算法 高速に n n n na
=
α
+
β
+
γ
と n n n na
γ
β
α
1
1
1
+
+
=
− が求められることを示す。}
)
(
)
(
)
{(
2
)
(
2 2 2 2 2 n n n n n n n n n na
=
α
+
β
+
γ
=
α
+
β
+
γ
+
αβ
+
βγ
+
γα
)
1
1
1
(
2
2 2 2 n n n n n nβ
α
γ
γ
β
α
+
+
+
+
+
=
n na
a
+
−=
22
よって n n na
a
a
2=
2−
2
− …② また)
)(
(
1 1 1 1 + + + +=
n+
n+
n n+
n+
n n na
a
α
β
γ
α
β
γ
n n n n n n)
)(
(
)
)(
(
)
)(
(
1 2 1 2 1 2β
γ
α
β
αβ
β
γ
βγ
γ
α
γα
α
+
+
+
+
+
+
+
+
=
+ + + n n n n n nx
x
x
−
+
−
+
−
+
+
+
=
+ + +β
β
α
α
γ
γ
γ
β
α
2 1 2 1 2 1(
)
1
(
)
1
(
)
1
+
+
−
+
+
+
+
+
=
+ + + − − − 1 1 1 1 2 1 2 1 21
1
1
1
1
1
n n n n n n n n nx
γ
β
α
γ
β
α
γ
β
α
)
(
1 1 2 ++
⋅
−−
− +=
a
nx
a
na
n より)
(
1 1 1 2n+=
a
na
n+−
x
⋅
a
−n−
a
−n+a
…③ ここで，0
1 2 3−
⋅
++
⋅
+−
=
+ n n n nx
a
y
a
a
a
であるから
0
2 1 1−
⋅
−+
⋅
−−−
−−=
+ −nx
a
ny
a
na
na
2 1 1 − − −− + − −n−
a
n=
y
⋅
a
n−
a
nxa
よって)
(
1 2 1 1 2n+=
a
na
n+−
y
⋅
a
−n−−
a
−n−a
…④ ②，③，④より次の漸化式が成り立つ。 n n na
a
a
2=
2−
2
− 2 1 1 1 2n+=
a
na
n+−
y
⋅
a
−n−+
a
−n−a
1 2 1 2 2n+=
a
n+−
2
a
−n−a
n n n n na
a
x
a
a
a
2 +3=
+1 +2−
⋅
− −1+
− n n na
a
a
−2=
− 2−
2
2 1 1 1 2 − − − − + + − n=
a
na
n−
x
⋅
a
n+
a
na
1 2 1 2 2 − −−2
+ − n=
a
n−
a
na
n n n n na
a
y
a
a
a
−2 −3=
− −1 − −2−
⋅
+1+
これらを用いると 2 1 2 1,
,
,
,
,
n+ n+ −n −n− −n− na
a
a
a
a
a
の組から 2 2 1 2 2 2 2 1 2 2n,
a
n+,
a
n+,
a
− n,
a
− n−,
a
− n−a
またはa
2n+1,
a
2n+2,
a
2n+3,
a
−2n−1,
a
−2n−2,
a
−2n−3 の組を求めることができ，したがって，a
nを高速に求めることができる。 周期に関する考察 周期に関する考察 周期に関する考察 周期に関する考察 命題 命題 命題 命題 3333 α，β，γは相異なるとき， 異なる(
a
n,
a
n+1,
a
n+2)
の個数と，異なる(
α
n,
β
n,
γ
n)
は個数と等しい。 証明 証明 証明 証明)
,
,
(
)
,
,
(
a
na
n+1a
n+2=
a
ma
m+1a
m+2 と仮定すると)
,
,
(
α
n+
β
n+
γ
nα
n+1+
β
n+1+
γ
n+1α
n+2+
β
n+2+
γ
n+2)
,
,
(
+
+
+1+
+1+
+1 +2+
+2+
+2=
α
mβ
mγ
mα
mβ
mγ
mα
mβ
mγ
m よって m m m n n nβ
γ
α
β
γ
α
+
+
=
+
+
1 1 1 1 1 1 + + + + + ++
n+
n=
m+
m+
m nβ
γ
α
β
γ
α
2 2 2 2 2 2 + + + + + ++
n+
n=
m+
m+
m nβ
γ
α
β
γ
α
したがって
n n nγ
β
α
γ
β
α
γ
β
α
2 2 21
1
1
=
m m mγ
β
α
γ
β
α
γ
β
α
2 2 21
1
1
ここで，α，β，γは相異なるから0
)
)(
)(
(
1
1
1
2 2 2≠
−
−
−
=
α
β
β
γ
γ
α
γ
β
α
γ
β
α
したがって，)
,
,
(
)
,
,
(
α
nβ
nγ
n=
α
mβ
mγ
m 逆も成り立つ。 ゆえに，)
,
,
(
)
,
,
(
a
na
n+1a
n+2=
a
ma
m+1a
m+2 ⇔(
α
n,
β
n,
γ
n)
=
(
α
m,
β
m,
γ
m)
したがって，この 1 対 1 対応により， 異なる(
a
n,
a
n+1,
a
n+2)
の個数と，異なる(
α
n,
β
n,
γ
n)
の個数は等しい。 証明終わり 証明終わり 証明終わり 証明終わり。 補題 補題 補題 補題δµν
αβγ
νδ
µν
δµ
γα
βγ
αβ
ν
µ
δ
γ
β
α
+
+
=
+
+
,
+
+
=
+
+
,
=
⇔集合として，{
α
,
β
,
γ
}
=
{
δ
,
µ
,
ν
}
証明 証明 証明 証明δµν
αβγ
νδ
µν
δµ
γα
βγ
αβ
ν
µ
δ
γ
β
α
+
+
=
+
+
,
+
+
=
+
+
,
=
とするとαβγ
γα
βγ
αβ
γ
β
α
γ
β
α
−
−
=
−
+
+
+
+
+
−
−
x
x
x
x
x
x
)(
)(
)
(
)
(
)
(
3 2δµν
να
µν
δµ
ν
µ
δ
+
+
+
+
+
−
−
=
x
3(
)
x
2(
)
x
)
)(
)(
(
−
δ
−
µ
−
ν
=
x
x
x
よって，3 次方程式(
x
−
α
)(
x
−
β
)(
x
−
γ
)
=
0
の解と，3 次方程式(
x
−
δ
)(
x
−
µ
)(
x
−
ν
)
=
0
解は一致する。 したがって，}
,
,
{
}
,
,
{
α
β
γ
=
δ
µ
ν
逆は明らか。 証明終わり 証明終わり 証明終わり 証明終わり 命題 命題 命題 命題 4444 異なる(
a
n,
a
−n)
の個数と，異なる集合{
α
n,
β
n,
γ
n}
の個数は等しい。 証明 証明 証明 証明)
,
(
)
,
(
a
ma
−m=
a
na
−n とする。 n ma
a
=
より n n n m m mβ
γ
α
β
γ
α
+
+
=
+
+
…① n ma
a
−=
− より n n n m m mβ
γ
α
β
γ
α
1
1
1
1
1
1
+
+
=
+
+
ここで，αβγ
=
1
を用いると n n n n n n m m m m m mβ
β
γ
γ
δ
α
β
β
γ
γ
α
α
+
+
=
+
+
…②また，
αβγ
=
1
より n n n m m mβ
γ
α
β
γ
α
=
…③ よって，①，②，③と補題により}
,
,
{
}
,
,
{
α
mβ
mγ
m=
α
nβ
nγ
n 逆は明らか。よって，)
,
(
)
,
(
a
ma
−m=
a
na
−n ⇔{
α
m,
β
m,
γ
m}
=
{
α
n,
β
n,
γ
n}
したがって，この 1 対 1 対応により， 異なる(
a
n,
a
−n)
の個数と，異なる{
α
n,
β
n,
γ
n}
の個数は等しい。 証明終わり 証明終わり 証明終わり 証明終わり ここで， 異なる{
α
n,
β
n,
γ
n}
の個数×3!≧異なる(
α
n,
β
n,
γ
n)
の個数 であるから，α，β，γが相異なるとき 異なる(
a
n,
a
−n)
の個数×6≧異なる(
α
n,
β
n,
γ
n)
の個数=異なる(
a
n,
a
n+1,
a
n+2)
の個数 さらに， 異なる(
α
n,
β
n,
γ
n)
の個数＝α
nβ
nγ
n,
,
それぞれの異なる個数の最小公倍数 異なる(
a
n,
a
−n)
の個数≦(体 K の位数)2 であるから，α
,
β
,
γ
を体 K とその拡大体にうまく配置できれば，異なる(
a
n,
a
n+1,
a
n+2)
の個数を，(体 K の位 数)2 程度まで延長できる可能性がある。0
≠
p
として，任意の整数 n についてa
n+p=
a
nを満たすとき，p を周期という。 ここでは，正の周期だけを考える。 周期のうち最小なものを，基本周期という。このとき，次の定理が成り立つ。 定理 定理 定理 定理 すべての周期は基本周期の倍数である。 証明 証明 証明 証明 基本周期を T とし，T でないある周期を p とすると，p>T より，整数 m を用いて p=Tm+r (0≦r<T) と表されるから r=p－Tm となる。T,p は共に周期であるから n p n Tm p n r na
a
a
a
+=
+ −=
+=
よって，r>0 とすると r は周期となり，0≦r<T より T が最小の周期であることに反する。 したがって，r=0 となるから， p=Tm ゆえに，p は T の倍数である。 証明終わり 証明終わり 証明終わり 証明終わりこれより，基本周期は任意の周期の約数であるといえる。したがって，1 つの周期が求められれば，その周期 を素因数分解することにより，基本周期の候補が見つかる。 異なる
(
a
n,
a
n+1,
a
n+2)
の個数は，基本周期である。 体から零元 0 を除けば群をなすから，異なる(
α
n,
β
n,
γ
n)
の個数は（拡大体の位数－1）の約数である。 さらに，異なる(
a
n,
a
n+1,
a
n+2)
の個数は，異なる(
α
n,
β
n,
γ
n)
の個数と等しいから， 基本周期は 基本周期は 基本周期は 基本周期は（拡大体の位数－（拡大体の位数－（拡大体の位数－（拡大体の位数－1111）の約数）の約数）の約数）の約数 である。 実装例 実装例 実装例 実装例GF
(
2
)
の既約多項式x
127+ x
63+
1
を用いて体を構成する。2
127−
1
はメルセンヌ素数である。この体 上で公開鍵暗号を作成するとき，この体の位数は 1272
であるから， （ⅰ）体が拡大されず，位数が 1272
のとき （体の位数－1）＝2
127−
1
（ⅱ）拡大体の位数が 127 2)
2
(
のとき （拡大体の位数－1）＝(
2
127)
2−
1
=
(
2
127−
1
)(
2
127+
1
)
1
2
127+
=3×56713727820156410577229101238628035243 （ⅲ）拡大体の位数が 127 3)
2
(
のとき （拡大体の位数－1）＝(
2
127)
3−
1
=
(
2
127−
1
){(
2
127)
2+
2
127+
1
}
1
2
)
2
(
127 2+
127+
＝7×2287×15241×349759 ×339212878596211796110770323541353281494127285320354524672773903 t の 3 次方程式t
3−
xt
2+
yt
−
1
=
0
で，100000 個の x,y の乱数の組で実験したところ， 周期が(
2
127)
2−
1
の約数であるものは 66647 個 あり，その内 周期が2
127−
1
であるものは 16765 個 周期が2
127+
1
の約数であるものは 0 個 周期が(
2
127)
2+
2
127+
1
の約数であるものは 33353 個 あり，その内 周期が(
2
127)
2+
2
127+
1
であるものは 28486 個 あった。 周期が(
2
127)
2+
2
127+
1
である x，y を用いるのが良いと思われる。 チェビシェフ多項式との関係 チェビシェフ多項式との関係 チェビシェフ多項式との関係 チェビシェフ多項式との関係 t の 3 次方程式0
1
2 3−
+
−
=
yt
xt
t
において，y=x とおくと0
1
2 3−
xt
+
xt
−
=
t
この方程式はt
=
1
を解に持ち，因数分解すると0
}
1
)
1
(
){
1
(
t
−
t
2−
x
−
t
+
=
となるから， 2 次方程式t
2− xt
+
1
=
0
から作られる多項式をf
n(x
)
とし，この 3 次方程式から作られる多項式をg
n(x
)
とす ると1
)
1
(
)
(
x
=
f
x
−
+
g
n nとなる。この式と
