next up previous contents index
: Asir 用のライブラリの書き方 : OpenXMと分散計算 : Quick Sort   目次   索引

Cantor-Zassenhaus アルゴリズム

有限体上の一変数多項式の因数分解法はさまざまな方法が知られているが, こ こでは, 次数が等しい相異なる既約多項式の積 $f$ を因数分解する方法であ る Cantor-Zassenhaus アルゴリズムを紹介する. 扱う入力が限られているよ うに見えるが,

  1. 一般の多項式は, GCD により, 重複因子を含まない多項式 (無平方多項式) の積に分解できる.
  2. 無平方多項式は, GCD により, 次数が等しい相異なる既約多項式の積 に分解できる. 各因子に含まれる既約多項式の次数も知ることができる.
により, 実用的にも意味がある. ここでは, 係数体を, 標数 $p$ が奇数である $q$ 元体 ($q=p^n$) とする. このとき, 次が成り立つ.

定理 18.1   $f$ が $d$ 次既約多項式 $f_1,f_2$ の積とする. $GF(q)$ 上の高々 $2d-1$ 次式 $g$ をランダムに選ぶとき ${\rm GCD}(g^{(q^d-1)/2}-1,f)$ が $f_1$ または $f_2$ となる確率は $1/2-1/(2q)^d$.

即ち, $f$ に含まれる二つの $d$ 次既約因子が, ランダムに選んだ $2d-1$ 次多項式一つにより, 確率 1/2 弱で分離できることが分かる. $f$ に含まれる因子の数が 2 より大きいでも, ある(小さくない)確率で $f$ が 二つの自明でない因子に分離できる.

これを用いて, quick sort と同様に, 入力多項式を既約多項式に分解する 再帰的なアルゴリズム (Cantor-Zassenhaus アルゴリズム) が得られる. このアルゴリズムも quick sort と同様に並列化できる. 

#define LevelMax 5
         
extern Proc1$
Proc1 = -1$

/* random poynomial generator */

def monic_randpoly_ff(N,V)
{ 
  for ( I = 0, N1 = N-1, S = 0; I < N1; I++ )
    S += random_ff()*V^I;
  return V^N1+S;
}

/* a wrapper of c_z() called on a server */

def ox_c_z(F,E,M,Level)
{
  setmod_ff(M);
  F = simp_ff(F);
  L = c_z(F,E,Level);
  return map(lmptop,L);
}

/*
  Input : a square free polynomial F s.t. 
          all the irreducible factors of F has the degree E.
  Output: a list containing all the irreducible factors of F
*/

def c_z(F,E,Level)
{
  V = var(F);
  N = deg(F,V);
  if ( N == E )
    return [F];
  M = field_order_ff();
  K = idiv(N,E);
  L = [F];
  while ( 1 ) {
    W = monic_randpoly_ff(2*E,V);
    T = generic_pwrmod_ff(W,F,idiv(M^E-1,2));
    W = T-1;
    if ( !W )
      continue;
    G = ugcd(F,W);
    if ( deg(G,V) && deg(G,V) < N ) {
      if ( Level >= LevelMax ) {
        L1 = c_z(G,E,Level+1);
        L2 = c_z(sdiv(F,G),E,Level+1);
      } else {
        if ( Proc1 < 0 )
          Proc1 = ox_launch();
        ox_cmo_rpc(Proc1,"ox_c_z",lmptop(G),E,setmod_ff(),Level+1);
        L2 = c_z(sdiv(F,G),E,Level+1);
        L1 = ox_pop_cmo(Proc1);
        L1 = map(simp_ff,L1);
      }
      return append(L1,L2);
    }
  }
}
end$
このプログラムでは, server の有効活用のため, 二つ生成される因子の 分解のうち, 一方のみを新しい server に送り, 残りは自分が分解する.

問題 18.1   PC-UNIX (FreeBSD, Linux など) では, 複数の CPU を持つマシン上で, 複数のプロセスが実際に異なる CPU 上で動作するように設定する ことができる. このような場合に, 上のプログラムでどの程度 速度が向上するか試してみよ. 入力としては, 異なる一変数多項式 の積を用いればよい.

問題 18.2   上のプログラムは, 元のプロセスが動作しているマシンの上に server を立ち上げてしまう. 複数台のマシンが使える人は, ``野呂, 下山, 竹島 : Asir User's Manual'' (cf. 25.3 節) の 第 7 章をよく読んで, 上のプログラムを 複数のマシン上の server を使えるように改良せよ. さらに, 計算時間と server 数の比 (台数効果) を調べよ.

余談(by T): 複数台のマシンを実際に接続して計算しようという場合, 如何に安全に他のマシンでサーバを起動するかという問題がある. 伝統的に組織全体のファイアウオールを嫌い, cracking の嵐が直接研究室に襲ってくる大学環境の場合, これは常に切実になやまされる問題である. 分散計算実験機全体をお手製ファイアウオールにいれてしまったり, PAM を用いるのが正当的だろうが, もっとおてがるな方法に, rsh を ssh に symbolic リンクしてしまうという方法が ある. ssh-agent の利用で, 安全にパスフレーズなしでリモートサーバを 起動できるし, rsh のお手軽さはそのままである. もちろん余計なサービスは全て停止しておくのが常識である.


Nobuki Takayama 平成15年9月12日