Projective DeBruijn 系列を係数に持つ多項式の原始既約性の判定佐藤 春菜

1(指導教員：萩田真理子)
a0 a1 a2 a3 · · · , ai = aN +i , aj ∈ X
であり，どの連続する k 個も異なり，最小距離k−1∑
d :=minδ(ai+s , ai+t ) ただし
0≤s<t≤N −1
i=0{
1 (x 6= y)δ(x, y) =0 (x = y)の error-correcting code をなすものをいう.

はじめにストリーム暗号の多くは，鍵から生成した擬似乱数列と平文の排他的論理和 (XOR) を取ることで暗号化され，復号時には再び暗号文と擬似乱数列を XOR する．このとき，暗号化した時と同じ位置で XOR しなければならないため，送信者と受信者の間で同期を取る必要がある．そのため，送信者が周期的な数列を単位時間に１ビットずつ送り続けたとき，受信者の側で受け取った数列の一部分を見れば，たとえそれが誤りを含む列でも，それを訂正して相手の送った数列を知り，同期を取ることができる誤り訂正符号系列が必要とされている．このような誤り訂正符号系列は，ProjectiveDeBruijn 系列を係数に持つ原始多項式が存在すれば，これを用いて m 系列を作ると性質の良いものが得られる．本研究では「Projective DeBruijn 系列を係数に持つ原始多項式が存在する」ことを確かめるため，小さなパラメータでの原始多項式の割合を調べた．

2

Fq 上 n 次の m 系列は，周期 q n −1 で，Definition4,5より (q n − 1, n, 1)ECS である.

3

Projective DeBruijn 系列

２章より，e 個の誤り訂正をするための最小距離 dは d ≥ 2e + 1 であることから，誤りを訂正するにはd は３以上でなくてはならないことが分かる. しかし
ｍ系列は (q n − 1, n, 1)ECS，すなわち d = 1 であるため，誤りを訂正することができない.
そこで，d ≥ 3 とするため，(q n − 1, n + s, d)ECS とし，d を大きくするために，見る範囲を +s だけ拡張し，ｍ系列に現れる連続する n + s 個を見る. これは
a0 a1 · · · an−110···0
···
an−1 1···0  0 a0 a1
A=
..
..
..

.
.
.


誤り訂正符号とｍ系列Definition 1 (ハミング距離) F n の任意の２つの元
x = (x1 , · · · , xn ) と y = (y1 , · · · , yn ) に対して，xi 6=yi である座標 i の数を x と y のハミング距離といい，d(x,y) と書く.
Definition 2 (最小距離)
C(⊂ F n ) を符号とする.C の任意の 2 つの符号語のハミング距離の最小値0···0a0a1···

an−11とすると，Ax = 0 を満たす，全て０以外のベクトルxの全体である.d ≥ 3 にするためには，行列 A のどの２つの列も線型独立でなくてはならない. 線型独
qn − 1
立な列の個数は高々個であるから，s をなるべ
q−1く小さくするには，この最大値を考えればよいので，qn − 1n+s =とする. このとき，行列 A の一行目をq−1１つの周期とする数列を考えると，行列 A のどの列も周期の中でちょうど 1 回ずつ，連続する s 文字として現れていることがわかる.

d = min{d(x, y) : x, y ∈ C, x 6= y}を符号 C の最小距離という.

Definition 3 (e-誤り訂正符号) e ビット以内の誤りを復号することが出来る符号を e-誤り訂正符号 (e-errorcorrecting code) と呼ぶ．
符号 C の最小距離 d が d ≥ 2e + 1 を満たすとき，Cは e-誤り訂正符号となる.

Definition 4 (m 系列) Fq 上の n 次のｍ系列とは，原始多項式

Definition 6 (Projective Debruijn 系列) s 次 のqs − 1
Projective DeBruijn 系列とは，Fq 上の周期q−1の数列であり，連続する s 個を見ると，周期の中で全て 0 の列以外のどのパターンもちょうど 1 回ずつ出ている数列である. ただし，k ∈ Fq \{0} について
(x1 x2 · · · xs ) = k(x1 x2 · · · xs ) とする．

f (t) = tn + an−1 tn−1 + · · · + a1 t + a0の係数から作られる漸化式

xn+i + an−1 xn+i−1 + · · · + a0 xi = 0

Theorem 1 f (x) = xn + an−1 xn−1 + · · · + a1 x + a0
を Fq 上 s 次の Projective DeBruijn 系列を係数に持つ
s−1− s である．この f (x)多項式とする. ただし n = qq−1からｍ系列を作ると，(q n − 1, n + s, 3)ECS となる.

で生成される，周期 q n − 1 の数列 x0 x1 x2 · · · である．

C := {xi xi+1 · · · xi+n−1 | i = 0, 1, · · · , q n − 1}とおくと，C = Fqn \{0} となる．

「Projective DeBruijn 系列を係数に持つ多項式」とは，s − 1 個の 0 が連続する部分を除き，その次の数
s−1−s 次から順に係数とした多項式である．これは qq−1式になる．

Definition 5 (error-correcting sequence) X 上の (N, k, d)error-correcting sequcnce(ECS) とは，周期 N の数列
1

Theorem 2 (Projective DeBruijn 系列の個数)
Fq 上の s 次の Projective DeBruijn 系列の個数はq s−1 −1(q!) q−1
q s−1個である.

Conjecture 2 Conjecture1が 正 し け れ ば ，()
q s −1−sq s −1q−1q− 1, q−1 , 3 ECS が存在する．
F = F2 の場合については，この予想は成り立たず，n代わりに (22 −n−1 − 1, 2n − 2, 3)ECS が存在すると予想されている．この予想については，DeBruijn 系列と呼ばれる列を係数とする原始多項式の存在を仮定すれば正しいことが示されていて，その存在性については先行研究があるので，本研究では q が奇数の場合を考察した．

Fq 上の n 次式を考え，k を xk = 1 となる最初の kとすると，x, x2 , x3 , · · · は周期 k の周期列となる．既n約な多項式は xq −1 = 1 であるので，k | q n − 1 が成り立つ．
定義より，k = q n − 1 なら原始既約である．
nq − 1 と k がそれぞれ次のように分解できたとする．

原始多項式の数

028の多項式の総数

39366

約 1.00 × 1017

原始多項式の総数

2640

約 1.19 × 1015=(q!) q−1
q s−1·φ(q n − 1)/n(q − 1)q n−1個以上となり，q = 3 の 3 次 (s = 3, n = 10) 以外では存在すると期待できる．

k < q − 1 とすると，di < ei となる i が存在し，nk | q q−1が成り立つ．
i564

q s−1 −1nx = 1 ならば x12(F3 上4 次の Projective DeBruijn 系列の個数)
F3 上 36 次の原始多項式の個数
×F3 上 36 次の多項式の個数− 1 = q1e1 q2e2 · · · qlel
k = q1d1 q2d2 · · · qldl

因数 qi について x qiいえる．

既約多項式の数

このように，Projective DeBruijn 系列から作った多項式の方が原始多項式の割合が高いと期待できる結果となった．Projective DeBruijn 系列から作った多項式の方がランダムに係数を選んだ多項式よりも原始多項式になりやすいと仮定すると，Projective DeBruijn 系
列を係数とする原始多項式の個数の期待値は，本研究では，すでに既約多項式であると判定された多項式を以下のような方法で原始多項式かどうかを調べた．

q n −1qi
q n −16510819(2000)

Projective DeBruijn 原始多項式の個数
Projective DeBruijn 多項式の個数
28== 0.014
2000

Definition 7 (原始多項式) f (x) を Fq 上の n 次式とnする．x, x2 , x3 , · · · , xq −1 を f (x) で割ったときの余りが全て異なるとき，f (x) を原始多項式という．

k144(144)

F3 上の 36 次の原始多項式の個数
F3 上の 36 次式の個数
φ(336 − 1)/36== 0.00399 · · ·2 · 335

既約多項式の原始性の判定

qProjectiveDeBruijnの数 (調べた数)

3 次の Projective DeBruijn 系列では原始多項式は存在しなかった．これは Conjecture1 の反例となる結果である．
また，4 次の結果から，「一般の多項式の中の原始多項式の割合」と「Projective DeBruijn 系列から作った多項式の中の原始多項式の割合」を比較してみると，以下のようになる．

この予想が成り立てば，次の予想も成り立つ．

n4次(n = 36)

an = 1, a0 6= 0

Conjecture 1 Fq (q ≥ 3) 上の Projective DeBruijn
系列を係数に持つ多項式の中には，原始既約であるものが存在する．

43次(n = 10)

6= 1 なので，q − 1 の全ての素nまとめと今後の課題

F3 上の 3 次と 4 次の Projective DeBruijn 系列の係数から作った多項式について，それぞれの原始多項式の割合を調べた．
今後は，F3 上の 4 次の多項式について，より統計的な精度を出すようにプログラムを改良すること，また，
F5 上の Projective DeBruijn 系列についても同様に調べていきたい．

6= 1 ならば原始既約であるとProjective DeBruijn 原始多項式の存在性

F3 上の 3 次と 4 次の Projective DeBruijn 系列に関しての結果は以下のようになった．

参考文献[1] Mariko Hagita, Makoto Matsumoto, Fumio
Natsu, Yuki Ohtsuka: ”Error Correcting Sequenceand Projective De Bruijn Graph”
Graphs and Combinatorics(2008)24:185-194

2