结式

结式（Resultant）

结式（Resultant）通常用于处理多变量的多项式方程，下面给出一个具体实例进行参考

实例

from Crypto.Util.number import *

p0 = 7
q0 = 13
N = p0 * q0
p_plus_q = p0 + q0

x, y = ZZ['x, y'].gens()
f = N - p*q
g = p+q - p_plus_q
h = f.resultant(g, q)
print([f, g])
# [-p*q + 91, p + q - 20]
print([h, factor(h)])
# [-p^2 + 20*p - 91, (-1) * (p - 13) * (p - 7)]
roots = h.univariate_polynomial().roots()
print(roots)
# [(13, 1), (7, 1)]

在这里，我们通过g = f1.resultant(f2, q)消去了单变量q，最后得到了一个单变量的多项式进行求解

定义

在一般条件下，我们定义如下的多项式 f(x) = a(x − α₁)(x − α₂)⋯(x − α_m)

g(x) = b(x − β₁)(x − β₂)⋯(x − β_n)

则我们记它们的结式为 Res(f, g) = aⁿb^m∏_i, j(α_i − β_j)

 = aⁿ∏_ig(α_i)

 = (−1)^mnb^m∏_if(β_i)

所以我们可以通过结式快速判断两个式子有无公共根，从而将两个式子化简成一个单变量的式子

Sylvester 结式

两个一元多项式在一个域或者环下的结式是由它们所对应的Sylvester matrix行列式构成的

记两个一元多项式为 f(x) = a₀xⁿ + a₁x^n − 1 + … + a_n

g(x) = b₀x^m + b₁x^m − 1 + … + b_n

此时我们就可以构造他们的Sylvester matrix行列式

• 取f(x)的系数, 依次在左上角起向下构造m行，每行右移一格补零
• 取g(x)的系数, 依次在左下角起向下构造n行，每行右移一格补零

构造行列式 结式 res(f, g) = det (R(f, g))

然后我们就可以通过求解这个结式即可消去其中一个变量得到一个单变量的多项式

from sage.matrix.matrix2 import Matrix 
#构建矩阵，然后再计算其行列式
def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))

h = f1.sylvester_matrix(f2, y).det()         #利用结式消掉y
roots = h.univariate_polynomial().roots()

参考:

Resultant | languag3

入门向]结式在CTF Crypto中的应用 - 知乎