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

### `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.