Crypto中的结式

前几天做题遇见了，记录一下。

结式（resultant）

  • 概念： 在域中，多项式的结式是Sylvester Matrix的行列式。

  • 定义： 有两个多项式

$$
f(x)=\sum_{i=0}^ma_ix^i \
g(x)=\sum_{j=0}^nb_jx^j
$$

构造如下矩阵：

$$
S_{f,g}:=
\begin{bmatrix}
a_m & a_{m-1} & \cdots & a_1 & a_0 & & \ \
& \ddots & \ddots & & \ddots & \ddots\
& & a_m & a_{m-1} & \dots & a_1 & a_0 & \
b_n & b_{n-1} & \cdots & b_1 & b_0 & & \ \
& \ddots & \ddots & & \ddots & \ddots\
& & b_n & b_{n-1} & \dots & b_1 & b_0 & \
\end{bmatrix}
$$

其中前$n$行是$f(x)$,后$m$行是$g(x)$

该矩阵称为Sylvester矩阵，它的行列式为 $res(f,g)$,称为$f,g$的结式。

  • 应用：

    • 判断互素： 当且仅当$res(f,g)=0$时，两多项式存在公共根。

    • 消元： 假设有

$$
\begin{cases}
F(x,y)=0 \
G(x,y)=0
\end{cases}
$$

将$y$视为常数，此时$f(x),g(x)$有公因子，因此令$res(f,g)=0$可以解出$y$，再代入原方程便可以解出$x$。代码示例：

1
2
3
4
5
6
7
#sage
R = PolynomialRing(ZZ, 'x, y')
f1 =#x,y的表达式1
f2 =#x,y的表达式2
h = f1.sylvester_matrix(f2, y).det()         #利用结式消掉y
roots = h.univariate_polynomial().roots()    #求出x
print(roots)

结合coppersmith方法

1
2
3
4
5
6
7
8
9
10
11
12
13
#sage
n = 

R.<x,y> = PolynomialRing(Zmod(n))
f1 =#x,y的表达式1
f2 =#x,y的表达式2

h1 = f1.sylvester_matrix(f2, y).det()     #利用结式消掉y
h2 = f2.sylvester_matrix(f1, x).det() 
x_roots = h1.univariate_polynomial().monic().small_roots(X=2**128,beta=0.4,epsilon=0.01)#求出x
y_roots = h2.univariate_polynomial().monic().small_roots(X=2**128,beta=0.4,epsilon=0.01)
print(x_roots)
print(y_roots)

参考：结式、伴随矩阵、特征多项式和2023江苏省数据安全竞赛的hardrsa | Tover’s Blog