有限体上の一変数多項式の因数分解法はさまざまな方法が知られているが, こ
こでは, 次数が等しい相異なる既約多項式の積 を因数分解する方法であ
る Cantor-Zassenhaus アルゴリズムを紹介する. 扱う入力が限られているよ
うに見えるが,
これを用いて, 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 に送り, 残りは自分が分解する.
余談(by T): 複数台のマシンを実際に接続して計算しようという場合, 如何に安全に他のマシンでサーバを起動するかという問題がある. 伝統的に組織全体のファイアウオールを嫌い, cracking の嵐が直接研究室に襲ってくる大学環境の場合, これは常に切実になやまされる問題である. 分散計算実験機全体をお手製ファイアウオールにいれてしまったり, PAM を用いるのが正当的だろうが, もっとおてがるな方法に, rsh を ssh に symbolic リンクしてしまうという方法が ある. ssh-agent の利用で, 安全にパスフレーズなしでリモートサーバを 起動できるし, rsh のお手軽さはそのままである. もちろん余計なサービスは全て停止しておくのが常識である.