多項式の選択

ysd@KLab > 因数分解 > GNFS > 多項式

目的

因数分解する数 n を、適当な整数 m と d 次の多項式 f(x) を使って

n = f(m) = cdmd + cd-1md-1 + … + c1m + c0
と表す事が目的です。前提として既知な数は n と d だけとします。m や f(x) も既知なのはこの項目必要無いですし。

ここで選ばれる多項式の性質によって後の計算の効率が変わってきますので、効率の良い（＝後の計算が速い）数式をうまく選び出す事も重要になります。

ちなみにここで使われている変数(n, m, f(x), d, ci)は他の項目でも同じ意味で使います。

とりあえず作る

完全にランダム

mと1次以上の係数を全部乱数で適当に決める。定数項で帳尻を合わせれば完成。 
tmp = n;
m = rand();
for( i = d ; i > 0 ; i-- ) {
  c[i] = rand();
  tmp = tmp - c[i] * (m ** i);
}
c[0] = tmp;

m進展開

mを乱数で決めてnをm進展開すれば係数が全部0≤c<mに入ります。 
tmp = n;
m = rand(n ** (1/(d + 1)), n ** (1/d)); // n**(1/d+1)とn*(1/d)の間の乱数
for( i = 0 ; i ≤ d ; i++ ) {
  c[i] = tmp % m;
  tmp = tmp / m;
  // 後で挿入するところ
}
大雑把に言うと係数の絶対値が小さい方がいい（どこかの係数が特に優先されるということはない）ので、係数の最大を m にします。係数に負の数を許すと、下記のような改造で最大値を m/2 に収めることができます。 
  if(c[i] > m / 2 ) {
    c[i] = c[i] - m;
    tmp = tmp + 1;
  }
改造は簡単。これを先ほどのコードのコメント部分に挿入するだけ…と思ったら乱数の範囲をちょいと変えなきゃいけないかも。

多項式の良さをスコアリング

先に書いた通り、ここの多項式次第で後の計算速度が変わってくるので、その速さを実験しなくても係数から予測できないかなぁということです。

係数の絶対値

大雑把には、係数の絶対値が小さいとありがたいです。理由としては（詳細はアルゴリズムの該当箇所を見てもらうとして）ノルムの値が小さいと計算が速いから、ということです。 
int score( int c[] )
{
  scr = 0;
  for( i = 0 ; i ≤ d ; i++ )
    scr += abs( c[i] );
  return scr;  // 勿論 scr は小さい方が良い
}