Sylvester结式法求解多项式方程

文中提到的论文是指 这个，论文中对Sylvester结式法做了简要的介绍

Sylvester结式法，结式，消元法，ctfshow 七夕杯 LUCK7，crypto，WriteUp

• 吴方法

• Grobner 基方法

• 迪克逊（Dixon）结式法

• 希儿维斯特（Sylvester）结式法

• …

  其中 Sylvester 结式法是一种经典的基本消元方法。

结式(Eliminant)

定义来自百度百科

指由两个多项式的系数所构成的一种行列式，或称Sylvester行列式，结式可判断两个多项式是否有公根、是否互素，以及判断多项式是否有重根。

设
$$\begin{gathered} f(x)=a_0{x}^n+a_1{x}^{n-1}+...+a_n \\ g(x)=b_0{x}^m+b_1{x}^{m-1}+...+b_m \end{gathered}$$
将 $f(x)$ 分别乘以 $x$ ~ $x^m$，得到 $m$ 个等式

同理，将 $g(x)$ 分别乘以 $x$ ~ $x^n$，得到 $n$ 个等式

由此定义行列式 $R(f,g)$
$$R(f,g)=\left|\begin{array}{ccccccccc}{a}_0& a_1& a_2& ...& ...& a_n& 0& ...& 0\\ 0& a_0& a_1& ...& ...& a_{n-1}& a_n& ...& 0\\ 0& 0& a_0& ...& ...& a_{n-2}& a_{n-1}& ...& 0\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\\ 0& 0& ...& 0& a_0& ...& ...& ...& a_n\\ b_0& b_1& b_2& ...& ...& ...& b_m& ...& 0\\ 0& b_0& b_1& ...& ...& ...& b_{m-1}& b_m& ...\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\\ 0& ...& 0& b_0& b_1& ...& ...& ...& b_m\end{array}\right|$$
$R(f,g)$ 为 $f$ 和 $g$ 的结式

相关定理

• （在复数域中）多项式 $f$ 和 $g$ 有公共根的充要条件是它们的结式 $R(f,g)=0$
• 多项式 $f$ 和 $g$ 互素的充要条件是它们的结式 $R(f,g)\ne 0$

Sylvester 结式法消元

设二元方程
$$\begin{gathered} f(x,y)=a_n(y)x^n+a_{n-1}(y)x^{n-2}+a_{n-2}{x}^{n-2}+...+a_0(y) \\ g(x,y)=b_n(y)x^m+b_{m-1}(y)x^{m-2}+b_{m-2}{x}^{m-2}+...+b_0(y) \end{gathered}$$
其中， $a_i(y),b_j(y)$ 可以看作是 $f(x,y),g(x,y)$ 中 $x^i,x^j$ 的系数

利用上诉方法求出 Sylvester 结式，这样将求解方程组公共零点解，转化为对其求解 Sylvester 结式，并使结式 $R(f,g)=0$

于是通过利用求解结式的方法，消去了变量 $x$（或者变元 $y$），将复杂多项式方程简化为求解单一变元多项式的根。

这就是 Sylvester 结式法消元的原理

实现

论文中对实现流程的描述

此处我使用 sageMath 集成的函数来实现

尝试求解以下方程组的零解
$$\begin{array}{l}f(x,y)=x^3-2x^{2}y+4xy-y^2-2\\ g(x,y)=2x{y}^2+xy-y^3-2\end{array}$$
对这个方程组

from sage.matrix.matrix2 import Matrix

P.<x,y> = PolynomialRing(ZZ)
f = x^3 - 2*x^2*y + 4*x*y - y^2 - 2
g = 2*x*y^2 + x*y - y^3 - 2
syl_x = f.sylvester_matrix(g,x)
syl_y = f.sylvester_matrix(g,y)
# 分别是通过代入，消去 x 和 y
print(syl_x)
print(syl_y)

det = Matrix.determinant(syl_x)
# 化为单变元，直接求解
# 如果最开始是二元函数的话，消掉一个元就已经是单变元函数了，但还是需要执行这一步
r = det.univariate_polynomial()
rr = r.roots()
print(rr)
# [(1,1)]

代表 $y$ 有两个相同的解，即 1

将 $y=1$ 代回等式 $f$ ，再求解，得到 $x$ 的值

ctfshow 2022 七夕杯 Luck7

题目

from Crypto.Util.number import bytes_to_long, getPrime
from secret import flag

l = len(flag)
assert l == 56
x = bytes_to_long(flag[:l//2])
y = bytes_to_long(flag[l//2:])

p = getPrime(1024)
e = 65537 #e = '0x10001'  print(int(e,16))

x = pow(x, e, p)
y = pow(y, e, p)

a = (7 * x + x * y + 77 * y ** 7) % p
b = (x ** 7 + 777 * y) % p
'''
print(f'p = {p}')
print(f'a = {a}')
print(f'b = {b}')
''''''
p = 160676801612994301361202519503059426958636739446670462398261976532859847492256822690640058297338763725128097587993428329580105931247817467950370089691908132361316857330836120708767594061772979871315614755470773991633234068651435625372887767258609941208307491359777513843529144444836847722372845148836203335627
a = 30318995909014771647618268716833486449002423009996671727903532973647046764624121316716790986592523978549131384964872198795285872746623966910764159262479160147876027157581577141632378119375701270068263640642243000011932466519579133761464923463402462812787531220639360431295348786697861069940729757964584951972
b = 51036630170491152581994259808984114372634216659979376101433163181132141957563047348137651942358538069256102718534893846618166559129391336639526588292370462975735415885732360576961407017238385374280336346614960555565504032093702784952402038043052556719843691506943605133036720410419999467125928578673380637828

脚本

有官方WP，此方法也是通过官方WP才知道的。

使用 Sylvester 结式法直接解即可

# Sage
from sage.matrix.matrix2 import Matrix
from Crypto.Util.number import long_to_bytes

def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))

p = 160676801612994301361202519503059426958636739446670462398261976532859847492256822690640058297338763725128097587993428329580105931247817467950370089691908132361316857330836120708767594061772979871315614755470773991633234068651435625372887767258609941208307491359777513843529144444836847722372845148836203335627
a = 30318995909014771647618268716833486449002423009996671727903532973647046764624121316716790986592523978549131384964872198795285872746623966910764159262479160147876027157581577141632378119375701270068263640642243000011932466519579133761464923463402462812787531220639360431295348786697861069940729757964584951972
b = 51036630170491152581994259808984114372634216659979376101433163181132141957563047348137651942358538069256102718534893846618166559129391336639526588292370462975735415885732360576961407017238385374280336346614960555565504032093702784952402038043052556719843691506943605133036720410419999467125928578673380637828
e = 0x10001

P.<x, y> = PolynomialRing(Zmod(p))
f1 = 7 * x + x * y + 77 * y ** 7 - a
f2 = x ** 7 + 777 * y - b

hx = resultant(f1, f2, y)
rx = hx.univariate_polynomial().roots()
x, _ = zip(*rx)
y = [((b - i^7) * inverse_mod(777, p)) % p for i in x]

d = inverse_mod(e, p-1)

for i in range(len(x)):
    m1 = pow(x[i], d, p)a
    m2 = pow(y[i], d, p)
    try:
        print(bytes.fromhex(hex(m1)[2:]).decode(),end='')
        print(bytes.fromhex(hex(m2)[2:]).decode())
    except:
        pass