有限体上の多項式の既約性判定アルゴリズム
(この記事はQiitaからの転載です)
暗号や符号などで既約多項式がよく使われることは誰しも知っていると思う。
でも、じゃあその既約多項式ってどうやって見つけてくるの?ということはよくわからない。
そこで私が調べた結果わかったことを記事にしてみようと思った。
今回紹介するのは、Ben-Orの(多項式の)既約性判定テストの方法だ。
私が知っていたのは手元に以下の本を持っていたからだ。
計算機代数の辞書的な本に相当するが、数学系のプログラミングをしている人にはぜひともおすすめしたい。ネットで調べて出てくるのはアイゼンシュタインの判定法とかだが、計算機で使う判定法とはあまり関係ない。
(値段がすごいことになってますが、自分が買ったときは1万円行かなかったと思います。ノイキルヒの代数的整数論より高い?)
この本には以下のような疑似コードが書かれている。
1.ランダムに有限体上の多項式を取り、それを
2.for i in 1 to floor(n/2) do
3.else retturn f.
たったこれだけで既約性を判定できるのだ。
コードで示そう。
//GF(2^m) then set m in this function.
int ben_or(OP f)
{
int i, n, flg = 0;
OP s = {0}, u = {0}, r = {0};
vec x = {0};
//if GF(8192) is 2^m and m==13 or if GF(4096) and m==12 if GF(16384) is testing
int m = 13;
x.x[1] = 1;
s = v2o(x); //s(x)=x
r = s;
n = deg(o2v(f));
if (n == 0)
return -1;
i = 0;
//r(x)=x^{q^i} square pow mod
while (i < n / 2 + 1)
{
flg = 1;
//over GH(8192) 2^13
r = opowmod(r, f, m); //r(x)=r(x)^m % f
//over GF2
//r=omod(opow(r,2),f);
u = oadd(r, s);
if (LT(u).n == 0 && LT(u).a == 0)
return -1;
if (LT(u).n == 0 && LT(u).a == 1)
{
i++;
flg = 0;
}
if (LT(u).n > 0)
u = gcd(f, u);
if (LT(u).n > 0)
return -1;
if (flg == 1)
i++;
}
return 0;
}
ここでちょっと問題なのは、
仮に巨大整数型を使うにしても、xを
しかし安心してほしい。この計算には秘訣があるのだ。
まずコードで見てみよう。
//多項式のべき乗余
OP opowmod(OP f, OP mod, int n)
{
int i, j = 0;
//繰り返し2乗法
for (i = 1; i < n + 1; i++)
{
f = omul(f, f);
if (odeg(f) > odeg(mod))
f = omod(f, mod);
}
return f;
}
ここで出てくる繰り返し2乗法は楕円曲線やRSAの実装をしたことがあれば知っていると思うので割愛する。q=2ならば、f同士を掛け算することを繰り返していけば、
更に多項式の次数nが128次のとき、
このように、このアルゴリズムの計算量は多項式の次数nと体の拡大次数mに関係している。
計算の途中でgcdが出てくるが、これは
(蛇足だが、q=3の場合は
今回の実装ではランダムな多項式を生成して、その中から
以上簡単ではあるが、有限体上定義された既約多項式の判定法の紹介である。
プログラムを動かしてみたい方はコメントください。
詳しい理屈が知りたい方は、以下の参考文献をお読みいただきたい。
20210324(追記)
なんで探している間は出てこないんだろう・・・
本に乗ってることがネットで見つからないなんてありえないと思っていたけど、検索内容が変わるというのはよくあるらしい。
Discussion