有限体上の多項式の因数分解

数学とコンピュータ代数 において、多項式の因数分解は、それを既約因数の積に分解することから成ります。この分解は理論的には可能であり、任意の体の係数を持つ多項式に対して一意ですが、アルゴリズムによる因数分解の計算を可能にするには、係数の体に対する強い制限が必要です。実際には、アルゴリズムは有限体、有理数体、またはそれらのいずれかの 有限生成体拡大の係数を持つ多項式に対してのみ設計されています。

有理数上の多変数多項式の場合も含め、すべての因数分解アルゴリズムは、問題をこの場合に帰着させます。多項式因数分解を参照してください。また、これは、符号理論(巡回冗長符号やBCH符号)、暗号化(楕円曲線による公開鍵暗号化)、計算数論など、有限体のさまざまな応用にも使用されます。

多変数多項式の因数分解を一変数多項式に還元することは有限体の係数の場合には特異性がないため、この記事では 1 つの変数を持つ多項式のみを検討します。

有限体理論は、その起源をガウスとガロアの業績にまで遡ることができ、数学のさまざまな分野で役割を果たしてきました。この概念は、コンピュータサイエンスなどの数学や科学の他の分野にも応用できるため、有限体への関心が再び高まっており、これは部分的には、符号理論と暗号化における重要な応用によるものです。有限体の応用は、暗号化、コンピュータ代数、および符号理論におけるこれらの発展の一部をもたらします。

有限体またはガロア体は、有限の位数（元の数）を持つ体です。有限体の位数は、常に素数または素数のべき乗です。各素数のべき乗 q = p ^rに対して、同型を除いてq個の元を持つ有限体が 1 つだけ存在します。この体はGF ( q ) またはF _qと表記されます。p が素数の場合、GF ( p ) は位数pの素体です。つまり、 pを法とする剰余類の体であり、そのp個の元は 0、1、...、p −1 と表記されます。したがって、GF ( p )のa = b は、a ≡ b (mod p )と同じ意味になります。

F を有限体とする。一般体と同様に、 F [ x ]の非定数多項式fは、2つの正の次数の多項式の積でない場合、 F上で既約であると言われる。 F上で既約でない正の次数の多項式は、F上で既約であると言われる。

既約多項式を使うと、素数でない位数の有限体を構築できます。実際、素数冪qに対して、同型を除いて一意であるq個の元を持つ有限体F _qとします。 F _q上で既約である、1 より大きいn次多項式fは、 q ⁿ個の元を持つ体に同型なn次体の拡大を定義します。この拡大の元はnより低い次数の多項式です。 F _qの元による加算、減算、乗算は、多項式の元と同じです。2 つの元の積は、多項式としての積をfで割った余りです。元の逆は、拡張 GCD アルゴリズムで計算できます (代数拡大の算術を参照)。

したがって、非素数位数の有限体で計算するには、既約多項式を生成する必要がある。このためによく使われる方法は、ランダムに多項式を取り、それが既約かどうかをテストすることである。体での乗算の効率性のために、通常はx ⁿ + ax + bの形をした多項式を探す。^{[要出典] [1]}

有限体上の既約多項式は、フィードバックシフトレジスタとF _{2 ⁿ}上の離散対数を使用する疑似乱数ジェネレータにも役立ちます。

F _q上の n 次の既約な単項多項式の数は、モローのネックレス数え関数M _q ( n ) によって与えられる非周期ネックレスの数です。密接に関連するネックレス関数N _q ( n ) は、基本 (既約のべき乗) であるn次の単項多項式、または n を割り切るすべての次数 d の既約な多項式を数えます。^[2]

多項式P = x ⁴ + 1はQ上では既約ですが、任意の有限体上では既約ではありません。

• F ₂の任意の体拡大において、P = ( x + 1) ⁴である。
• 他の有限体では、−1、2、−2のうち少なくとも1つは平方数である。なぜなら、2つの平方数でないものの積は平方数であり、したがって

1. もしそうなら${\displaystyle -1=a^{2},}$${\displaystyle P=(x^{2}+a)(x^{2}-a).}$
2. もしそうなら${\displaystyle 2=b^{2},}$${\displaystyle P=(x^{2}+bx+1)(x^{2}-bx+1).}$
3. もしそうなら${\displaystyle -2=c^{2},}$${\displaystyle P=(x^{2}+cx-1)(x^{2}-cx-1).}$

多項式因数分解アルゴリズムは、積、除算、最大公約数、ある多項式の別の多項式のべき乗などの基本的な多項式演算を使用します。最大でn次までの 2 つの多項式の乗算は、 F _qでは「従来の」演算を使用してO ( n ² ) 回の演算で実行でき、 F _qでは「高速」演算を使用してO ( n log( n ) log(log( n )) ) 回の演算で実行できます。ユークリッド除算(剰余のある除算) も同じ時間範囲内で実行できます。最大でn次までの 2 つの多項式間の多項式最大公約数のコストは、F _qでは従来の方法を使用してO ( n ² ) 回の演算で実行でき、F _qでは高速な方法を使用してO ( n log ² ( n ) log(log( n )) ) 回の演算で実行できます。最大でn次までの多項式h、gに対して、累乗法によるh ^qの g乗は、 O (log( q ))の多項式積で実行できます。これは、古典的な方法を使用した場合、 F _qでO ( n ² log( q )) の演算、または高速な方法を使用した場合、 F _qでO ( n log( q )log( n ) log(log( n ))) の演算になります。

以下のアルゴリズムでは、多項式の演算のための古典的なアルゴリズムを使用して 、複雑度はF _qの算術演算の数で表現されます。

有限体上の多項式を因数分解するアルゴリズムの多くには、次の 3 つの段階が含まれます。

1. 平方根のない因数分解
2. 異なる次数の因数分解
3. 等次因数分解

重要な例外は、ステージ 2 と 3 を組み合わせたBerlekamp のアルゴリズムです。

ベルレカンプのアルゴリズムは、実際にうまく機能する最初の因数分解アルゴリズムとして歴史的に重要です。ただし、このアルゴリズムには基底体の要素に対するループが含まれているため、小さな有限体でのみ実行可能です。固定された基底体の場合、その時間計算量は多項式ですが、一般的な基底体の場合、計算量は基底体のサイズに対して指数関数的になります。

このアルゴリズムは、 pが素数であるq = p ^m位の有限体F _qから係数が導かれる多項式の平方なし因数分解を決定します。このアルゴリズムは、まず導関数を決定し、次に多項式とその導関数の最大公約数を計算します。それが 1 でない場合、導関数がゼロでない限り (有限体上で定義された非定数多項式の場合に存在します)、最大公約数は元の多項式に再度分割されます。

このアルゴリズムは、多項式の導関数がゼロの場合、それはx ^pの多項式であるという事実、つまり係数がF _pに属する場合、多項式のp乗はx をx ^{1/ p}で置き換えることによって得られるという事実を利用します。係数がF _pに属していない場合、ゼロ導関数を持つ多項式のp乗根は、係数に フロベニウス自己同型の逆を適用することで完了する、xに対する同じ置き換えによって得られます。

このアルゴリズムは、特性0の体上でも機能しますが、唯一の違いは、p乗根を計算する命令ブロックには決して入らないことです。ただし、この場合、Yun のアルゴリズムは、より低い次数の多項式の最大公約数を計算するため、はるかに効率的です。結果として、多項式を整数で因数分解する場合、次のアルゴリズムは使用されません。最初に整数で平方なし因数分解を計算し、結果の多項式を因数分解するために、平方なし法pのままになるp を選択します。

アルゴリズム: SFF (Square-Free Factorization)
    入力: F q [ x ]の単項多項式 f ( q = p m)出力: fのSquare-Free 因数分解R ← 1
    
    
   
    # wをfの因数のうち重複のないすべての因数の積とする。# 重複度はp
    
    で割り切れないc ← gcd ( f , f ′)
     w ← f / c 
   # ステップ 1: w
    
    内のすべての因数を特定します。i ← 1 
     while  w ≠ 1 do 
        y ← gcd ( w , c )
         fac ← w / y 
        R ← R · fac i
         w ← y ; c ← c / y ; i ← i + 1 
     end while 
    # c はfの残りの因数の積 (重複あり) になります。
   
    # ステップ2: 再帰を使用して残りのすべての要素を特定する# これらはpで割り切れる重複度を持つf
    の因数であることに注意c ≠ 1の場合c ← c 1/ p R ← R · SFF ( c ) p終了 if
     
        
        
     
   
    出力（R）

考え方は、同じ重複度を持つfのすべての既約因数の積を特定することです。これは 2 つのステップで行われます。最初のステップでは、 fの形式導関数を使用して、重複度がpで割り切れないすべての因数を見つけます。2 番目のステップでは、残りの因数を特定します。残りの因数はすべて重複度がpで割り切れる、つまりpの累乗であるため、 p番目の平方根 を取って再帰を適用するだけで済みます。

させて

${\displaystyle f=x^{11}+2x^{9}+2x^{8}+x^{6}+x^{5}+2x^{3}+2x^{2}+1\in \mathbf {F} _{3}[x],}$

3 つの要素を持つ体上で因数分解されます。

アルゴリズムはまず計算する

${\displaystyle c=\gcd(f,f')=x^{9}+2x^{6}+x^{3}+2.}$

導関数はゼロでないので、w = f / c = x ² + 2となり、 while ループに入ります。 1 回のループ後、y = x + 2、z = x + 1、R = x + 1となり、 i = 2、w = x + 2、c = x ⁸ + x ⁷ + x ⁶ + x ² + x +1が更新されます。 2 回目のループでは、y = x + 2、z = 1、R = x + 1となり、i = 3、w = x + 2、c = x ⁷ + 2 x ⁶ + x + 2が更新されます。 3 回目のループでもR は変化しません。 4 回目のループでは、 y = 1、z = x + 2、R = ( x + 1)( x + 2) ⁴となり、i = 5、w = 1、c = x ⁶ + 1が更新されます。w = 1なので、while ループを抜けます。c ≠ 1なので、完全な立方体でなければなりません。 x ^{3 を}xに置き換えて得られるcの立方根はx ² + 1であり、平方根のない手順を再帰的に呼び出すと、平方根がないことがわかります。したがって、それを立方体にして、その時点までのRの値と組み合わせると、平方根のない分解が得られます。

${\displaystyle f=(x+1)(x^{2}+1)^{3}(x+2)^{4}.}$

このアルゴリズムは、平方自由多項式を、すべての既約因数が同じ次数である多項式の積に分割します。因数分解する多項式を 次数nのf ∈ F _q [ x ]とします。

アルゴリズム異なる次数による因数分解(DDF)
    入力: モニックな平方自由多項式  f ∈ F q [ x ]
    出力: f が次数dの既約因数を持ち、
              gがfの次数dのすべてのモニックな既約因数の積であるような 
             すべてのペア( g、d )の集合。Begin
     while do if g ≠ 1、then ;
                 end if i  := i + 1; end while ;
         if、then ;
         if、then return {( f、 1)}、
             else return S End
        ${\displaystyle i:=1;\qquad S:=\emptyset ,\qquad f^{*}:=f;}$
         ${\displaystyle \deg f^{*}\geq 2i}$  
            ${\displaystyle g=\gcd(f^{*},x^{q^{i}}-x)}$
              
                ${\displaystyle S:=S\cup \{(g,i)\}}$${\displaystyle f^{*}:=f^{*}/g}$
            
            
         ${\displaystyle f^{*}\neq 1}$ ${\displaystyle S:=S\cup \{(f^{*},\deg f^{*})\}}$ ${\displaystyle S=\emptyset }$  
    

アルゴリズムの正確さは以下に基づいています。

補題i ≥ 1に対して多項式

${\displaystyle x^{q^{i}}-x\in \mathbf {F} _{q}[x]}$

は、 F _q [ x ] 内の、次数がi を割り切る すべての単項既約多項式の積です。

一見すると、これは入力多項式の次数に対して指数関数的な次数の多項式のGCDを計算するため効率的ではない。しかし、

${\displaystyle g=\gcd \left(f^{*},x^{q^{i}}-x\right)}$

置き換えられる可能性がある

${\displaystyle g=\gcd \left(f^{*},\left(x^{q^{i}}-x\mod f^{*}\right)\right).}$

したがって、次の式を計算する必要があります。

${\displaystyle x^{q^{i}}-x\mod f^{*},}$

方法は2つあります。

方法I.の値から始める

${\displaystyle x^{q^{i-1}}\mod f^{*}}$

前のステップで計算された値と、そのq乗を新しいf*を法として2乗法で累乗する。これには

${\displaystyle O\left(\log(q)\deg(f)^{2}\right)}$

各ステップでF _qの算術演算を実行し、

${\displaystyle O\left(\log(q)\deg(f)^{3}\right)}$

アルゴリズム全体の算術演算。

方法II. q乗がF _q上の線型写像であるという事実を利用して、その行列を次のように計算することができる。

${\displaystyle O\left(\deg(f)^{2}(\log(q)+\deg(f))\right)}$

ループの各反復で、行列とベクトルの積を計算します（O（deg（f）^{2 ）回の演算）。これにより}_、 Fqの演算の総数は

${\displaystyle O\left(\deg(f)^{2}(\log(q)+\deg(f))\right).}$

したがって、この 2 番目の方法の方が効率的であり、通常はこの方法が好まれます。さらに、この方法で計算される行列は、ほとんどのアルゴリズムで等次数因数分解 (以下を参照) に使用されます。したがって、この行列を異なる次数因数分解に使用すると、さらに計算時間が節約されます。

このセクションでは、有限体F _q上のn次、単項平方自由一変数多項式fの因数分解について考察します。この多項式は、 r ≥ 2個の、それぞれ次数dの異なる既約因数をペアで持っています。 ${\displaystyle f_{1},\ldots ,f_{r}}$

まず、Cantor と Zassenhaus (1981) によるアルゴリズムについて説明し、次に、少しだけ計算量が少ない変種について説明します。どちらも、実行時間がランダムな選択 (ラスベガス アルゴリズム) に依存する確率的アルゴリズムであり、平均実行時間は良好です。次のセクションでは、Shoup (1990) によるアルゴリズムについて説明します。これも等次因数分解アルゴリズムですが、決定論的です。これらのアルゴリズムはすべて、係数体に奇数次数q を必要とします。その他の因数分解アルゴリズムについては、たとえば Knuth の著書The Art of Computer Programming第 2 巻を参照してください。

アルゴリズムCantor–Zassenhaus アルゴリズム。
    入力:奇数次qの有限体F q。F q [ x ]のn = rd次単項
           平方自由多項式f、r ≥ 2 個の既約因子
                を持ち、それぞれ次数dである。
    出力: fの単数既約因子の集合。

    因子:= { f };
     Size(因子) < rの場合、 F q [ x ]内のdeg( h ) < nとなるh をランダムに
        
        選択します。Factors内のdeg( u ) > dとなる各uに対して、 gcd( g , u ) ≠ 1 かつ gcd( g , u ) ≠ uであれば、
                Factors:= Factorsとなります。endif
             endwhile${\displaystyle g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}}$
           
            ${\displaystyle \,\setminus \,\{u\}\cup \{(\gcd(g,u),u/\gcd(g,u))\}}$
    

    リターン要因

このアルゴリズムの正しさは、環F _q [ x ]/ f が、f _{i が}fの既約因子上で実行される体F _q [ x ]/ f _iの直積であるという事実に依存しています。これらすべての体はq ^d個の元を持つので、これらの体のいずれにおいてもgの成分は確率でゼロになります 。

${\displaystyle {\frac {q^{d}-1}{2q^{d}}}\sim {\tfrac {1}{2}}.}$

これは、多項式gcd( g , u )がgの成分がゼロであるgの因数の積であることを意味します。

アルゴリズムのwhileループの平均反復回数は 未満であることが示されており、 Fqにおける算術演算の平均回数はとなる。^[3 _]${\displaystyle 2.5\log _{2}r}$${\displaystyle O(dn^{2}\log(r)\log(q))}$

d log( q ) > nの典型的なケースでは、この複雑さは次のように軽減される。

${\displaystyle O(n^{2}(\log(r)\log(q)+n))}$

線形写像の核で hを選択することによって

${\displaystyle v\to v^{q}-v{\pmod {f}}}$

命令を置き換える

${\displaystyle g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}}$

による

${\displaystyle g:=h^{\frac {q-1}{2}}-1{\pmod {f}}.}$

有効性の証明は上記と同じで、体F _q [ x ]/ f _iの直積を、 q個の要素を持つそれらの部分体の直積に置き換えます。計算量は、アルゴリズム自体、線形マップの行列の計算（これは平方自由因数分解で既に計算されている可能性があります）とカーネルの計算O ( n ³ ) に分解されます。このアルゴリズムは、因子の次数が同じでなくても機能することに注意してください（この場合、while ループを停止するために必要な因子の数rは、カーネルの次元として見つかります）。ただし、このアルゴリズムを使用する前に平方自由因数分解を行うと、計算量はわずかに改善されます（平方自由因数分解でnが減少する可能性があるため、重要なステップの計算量が削減されます）。 ${\displaystyle O(n^{2}\log(r)\log(q))}$${\displaystyle O(n^{2}(\log(q)+n))}$

前のセクションのアルゴリズムと同様に、Victor Shoupのアルゴリズムは等次因数分解アルゴリズムです。^[4]これらのアルゴリズムとは異なり、これは決定論的なアルゴリズムです。ただし、実際には、前のセクションのアルゴリズムほど効率的ではありません。Shoup のアルゴリズムでは、入力は素体F _p上の多項式に制限されます。

Shoup アルゴリズムの最悪の場合の時間計算量は係数 p になります。この計算量は指数関数的ではありますが、係数pを持つ以前の決定論的アルゴリズム (Berlekamp アルゴリズム) よりはるかに優れています。ただし、計算時間が指数関数的になる多項式は非常に少なく、アルゴリズムの平均時間計算量は の多項式になります。ここで、 dは多項式の次数、p は基底体の要素数です。 ${\displaystyle {\sqrt {p}}.}$${\displaystyle d\log(p),}$

g = g ₁ ... g _kを目的の因数分解とする。ここでg i_は次数dの異なる単数既約多項式である。n = deg( g ) = kd とする。環 R = F _q [ x ]/ gを考え、 xのRへの像もxで表す。環Rは体R _i = F _q [ x ]/ g _iの直積であり、p _iでRからR _iへの自然準同型を表す。R _iのF _q上のガロア群は次数dの巡回群であり、体自己同型u → u ^pによって生成される 。したがって、g _iのR _iへの根は

${\displaystyle p_{i}(x),p_{i}(x^{q}),p_{i}\left(x^{q^{2}}\right),\ldots ,p_{i}\left(x^{q^{d-1}}\right).}$

前のアルゴリズムと同様に、このアルゴリズムは、ベルレカンプのアルゴリズムと同じRの部分代数 Bを使用します。これは「ベルレカンプ部分代数」と呼ばれることもあり、次のように定義されます。

${\displaystyle {\begin{aligned}B&=\left\{\alpha \in R\ :\ p_{1}(\alpha ),\cdots ,p_{k}(\alpha )\in \mathbf {F} _{q}\right\}\\&=\{u\in R\ :\ u^{q}=u\}\end{aligned}}}$

Bの部分集合Sは、任意の 1 ≤  i  <  j  ≤  kに対してs  ∈  Sが存在し、となるとき分離集合と呼ばれます。前述のアルゴリズムでは、分離集合はSの要素をランダムに選択することによって構築されます。ショウプのアルゴリズムでは、分離集合は次のように構築されます。R [ Y ]のs がとなるものと します。${\displaystyle p_{i}(s)\neq p_{j}(s)}$

${\displaystyle {\begin{aligned}s&=(Y-x)\left(Y-x^{q}\right)\cdots \left(Y-x^{q^{d-1}}\right)\\&=s_{0}+\cdots +s_{d-1}Y^{d-1}+Y^{d}\end{aligned}}}$

すると、i =1, ..., kに対して は分離集合となる（2つの単項多項式は同じ根を持つ）。g i は対ごとに異なるため、_異なるインデックスの対（ i、j ）ごとに、係数s _hの少なくとも1つは次式を満たす。${\displaystyle \{s_{0},\dots ,s_{d-1}\}}$${\displaystyle p_{i}(s)=g_{i}}$${\displaystyle p_{i}(s_{h})\neq p_{j}(s_{h}).}$

分離集合を持つショウプのアルゴリズムは、単に「線形写像の核内のh をランダムに選択する」という命令を「 h がS内にあり、iが{1, ..., k −1} 内にある状態でh + i を選択する」に置き換えることで、前のセクションの最後のアルゴリズムと同じように進行します。 ${\displaystyle v\to v^{q}-v{\pmod {f}}}$

前のセクションで説明したように、有限体上の因数分解には、多項式時間計算量のランダム化アルゴリズム(たとえば、カントール-ザッセンハウス アルゴリズム) があります。また、多項式平均計算量を持つ決定論的アルゴリズム (たとえば、ショウプのアルゴリズム) もあります。

多項式最悪の複雑度を持つ決定論的アルゴリズムの存在は、まだ未解決の問題です。

個別次数分解アルゴリズムと同様に、ラビンのアルゴリズム^[5]は上記の補題に基づいています。個別次数分解アルゴリズムは、入力多項式の次数の半分以下のすべてのdをテストします。ラビンのアルゴリズムは、より少ないdを考慮するために因子が必要ないことを利用しています。それ以外は、個別次数分解アルゴリズムに似ています。これは次の事実に基づいています。

p ₁ , ..., p _{k を}nのすべての素因数とし、（1 ≤ i ≤ k）と表す。n次F _q [ x ] の多項式fがF _q [ x ]で既約となるのは、 （1 ≤  i  ≤  k）かつf がを割り切れるときのみである。実際、f がn を割り切れない 次数の因数を持つ場合、f はを割り切れない。fがn を割り切れる 次数の因数を持つ場合、この因数は少なくとも次の 1 つを割り切れる。${\displaystyle n/p_{i}=n_{i}}$${\displaystyle \gcd \left(f,x^{q^{n_{i}}}-x\right)=1}$${\displaystyle x^{q^{n}}-x}$${\displaystyle x^{q^{n}}-x}$${\displaystyle x^{q^{n_{i}}}-x.}$

アルゴリズムラビン既約性テスト
    入力: n次F q [ x ]の単項多項式f、 
         p 1、...、p k はすべてnの異なる素因数。
    出力: 「 f は既約ではない」または「f は既約である」のいずれか。

     j = 1 to k の場合、実行します 
        。i
     = 1 to kの場合、実行します。g
          := gcd( f , h );
         g ≠ 1の場合、 「f は既約です」を返して STOP します。
    終了
    。g =
     0の場合、 「f は既約ではありません」を返し、 
        それ以外の場合は「fは既約です」
を返します。${\displaystyle n_{j}=n/p_{j}}$   
        ${\displaystyle h:=x^{q^{n_{i}}}-x{\bmod {f}}}$ ${\displaystyle g:=x^{q^{n}}-x{\bmod {f}}}$ 

このアルゴリズムの基本的な考え方は、最小のものから繰り返し二乗するかフロベニウス自己同型を使って計算し、対応する最大公約数を取るというものである。初等多項式演算を使用すると、フロベニウス自己同型行列の計算にはF _qの演算が必要であり、 ${\displaystyle x^{q^{n_{i}}}{\bmod {f}}}$${\displaystyle n_{1},\ldots ,n_{k}}$${\displaystyle O(n^{2}(n+\log q))}$

${\displaystyle x^{q^{n_{i}}}-x{\pmod {f}}}$

にはさらにO ( n ³ ) 回の演算が必要であり、アルゴリズム自体にはO ( kn ² ) 回の演算が必要で、F _qには演算の合計が発生します。高速演算（乗算と除算、およびGCD 計算の計算量）を使用すると、繰り返し二乗することによるの計算はとなり、アルゴリズム自体は となり、 F _qには演算の合計が発生します。 ${\displaystyle O(n^{2}(n+\log q))}$${\displaystyle O(n\log n)}$${\displaystyle O(n(\log n)^{2})}$${\displaystyle x^{q^{n_{i}}}-x{\bmod {f}}}$${\displaystyle O(n^{2}\log n\log q)}$${\displaystyle O(kn(\log n)^{2})}$${\displaystyle O(n^{2}\log n\log q)}$

• ベルレカンプのアルゴリズム
• カンター・ザッセンハウスアルゴリズム
• 多項式因数分解

• いくつかの既約多項式 http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf
• 体とガロア理論:http://www.jmilne.org/math/CourseNotes/FT.pdf
• ガロア体:http://designtheory.org/library/encyc/topics/gf.pdf
• 有限体上の多項式の因数分解: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf