Algebra`PolynomialPowerMod`

このパッケージでは，素数および多項式を法とする多項式のベキ乗を効率的に計算する関数PolynomialPowerModを紹介する．PolynomialQuotientとPolynomialRemainderにはModulusオプションのサポートが加えられる．また，大規模な素数の法が扱えるようにFactor，FactorList，PolynomialGCDのModulusオプションも拡張する．

このパッケージの関数で使われる因数分解アルゴリズムは，D.E. Knuth著「Seminumerical Algorithms」（Addison-Wesley，1981出版）のセクション4.6.2で説明されている．まず，導関数を使って についての多項式 を無平方因子に分解する． を法とする の 次因数分解は，のときの と の最大公約数を求めることによって得られる．これは積算を繰返し使用して迅速に計算される．最後に，確率の因数分解アルゴリズムであるCantor-Zassenhausアルゴリズムを使って，結果を 次既約因子に分解する．

PolynomialPowerModの使用

パッケージをロードする．

In[1]:= <<Algebra`PolynomialPowerMod`

パッケージ関数のPolynomialPowerModは，組込み関数PolynomialModを使って多項式をベキ乗するよりも効率的である．

In[2]:= {Timing[PolynomialPowerMod[1 + x + x^2, 400,
{x^3 + x^2 + 1, Prime[4750]}]][[1]],
Timing[PolynomialMod[(1 + x + x^2)^400,
{x^3 + x^2 + 1, Prime[4750]}]][[1]]}

Out[2]=

PolynomialQuotientとPolynomialRemainderのModulusオプション

以下は についての2つの多項式である．

In[3]:= {f, g} = {(1 + x)^3 (1 + x^3), x^2 + 2};

PolynomialQuotientでModulusオプションを使うことは，PolynomialModをPolynomialQuotientの結果に適用することと同じである．

In[4]:= {PolynomialQuotient[f, g, x, Modulus -> 11],
PolynomialMod[PolynomialQuotient[f,g,x], 11]}

Out[4]=

PolynomialRemainderでModulusオプションを使うことは，PolynomialModをPolynomialRemainderの結果に適用することと同じである．

In[5]:= {PolynomialRemainder[f, g, x, Modulus -> 11],
PolynomialMod[PolynomialRemainder[f,g,x],11]}

Out[5]=

大規模な素数の法を扱うためのPolynomialGCD，Factor，FactorListの拡張

PolynomialGCDでModulusオプションを使うことは，PolynomialGCDの結果にPolynomialModを適用することと同じである．

In[6]:= {PolynomialGCD[x^2-1,x-1, Modulus -> Prime[10^8]],
PolynomialMod[PolynomialGCD[x^2-1,x-1], Prime[10^8]]}

Out[6]=

このパッケージをロードすると，多項式は大きい素数を法として因数分解される．

In[7]:= Factor[1 + 2 x^3, Modulus -> Prime[10^7]]

Out[7]=