结式的计算方法

结式计算

结式，是用来判断两个多项式之间是否互素的一种方式。

对于给定的多项式 $f(x,y),g(x,y)$ ，如果 $gcd(f,g)!=1$，那么 $f,g$ 的结式为0。

有如下三种方式计算 $res_x(f,g) $。

1.sylvester_matrix

h = f.sylvester_matrix(g, x).det().univariate_polynomial().monic()

2.resultant

P.<x, y> = PolynomialRing(ZZ)
f.resultant(g, x).univariate_polynomial().change_ring(Zmod(n)).monic()

3.groebner basis

P = Zmod(n)["x, y"]
I = ideal([g, f])
I.groebner_basis()[0].univariate_polynomial().monic()