gcd, gcdz

gcd(poly1,poly2[,mod])

gcdz(poly1,poly2)

:: poly1 と poly2 の gcd.

return

多項式

poly1,poly2

多項式

mod

素数

• 二つの多項式の最大公約式 (GCD) を求める.
• gcd() は有理数体上の多項式としての GCD を返す. すなわち, 結果は整数係数で, かつ係数の GCD が 1 になるような多項式, または, 互いに素の場合は 1 を返す.
• gcdz() は poly1, poly2 ともに整数係数の場合に, 整数環上の多項式としての GCD を返す. すなわち, gcd() の値に, 係数全体の整数 GCDの値を掛けたものを返す.
• 引数 mod がある時, gcd() は GF(mod) 上での GCD を返す.
• gcd(), gcdz() Extended Zassenhaus アルゴリズムによる. 有限体上の GCD は PRS アルゴリズムによっているため, 大きな問題, GCD が 1 の場合などにおいて効率が悪い.

[0] gcd(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
x^3+3*x^2+3*x+1
[1] gcdz(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
6*x^3+18*x^2+18*x+6
[2] gcd((x+y)*(x-y)^2,(x+y)^2*(x-y));
x^2-y^2
[3] gcd((x+y)*(x-y)^2,(x+y)^2*(x-y),2);
x^3+y*x^2+y^2*x+y^3

参照

section igcd,igcdcntl.

Go to the first, previous, next, last section, table of contents.