结式与RSA

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$。代码示例：

#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方法

#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