一种在模意义下的特殊高次方程的解法

也许会被一些奇怪的数据卡掉。

考虑解方程：

$$H_n(x_1, \dots, x_k) - H_{n-1}(x_1, \dots, x_k) = C \pmod p$$

其中 $H_n$ 是 $n$ 次齐次多项式，$H_{n-1}$ 是 $n-1$ 次齐次多项式，$p$ 是质数模数。

一个显然的性质是：对于任意标量 $t$，有 $H_d(t \cdot \mathbf{v}) = t^d H_d(\mathbf{v})$。

我们考虑随机选择一个方向向量 $\mathbf{v} = (v_1, v_2, \dots, v_k) \in \mathbb{F}_p^k \setminus \{\mathbf{0}\}$，然后令：

$$x_1 = t \cdot v_1, \quad x_2 = t \cdot v_2, \quad \dots, \quad x_k = t \cdot v_k$$

其中 $t \in \mathbb{F}_p$ 是未知的标量。

将 $\mathbf{x} = t\mathbf{v}$ 代入原方程，方程变为：

$$t^n H_n(\mathbf{v}) - t^{n-1} H_{n-1}(\mathbf{v}) = C \pmod p$$

因为向量 $\mathbf{v}$ 是我们随机选定的，所以现在 $H_n(\mathbf{v})$ 和 $H_{n-1}(\mathbf{v})$ 是两个常数。

令 $A = H_n(\mathbf{v}) \pmod p$，$B = H_{n-1}(\mathbf{v}) \pmod p$。

原问题转化为求解：

$$A t^n - B t^{n-1} - C = 0 \pmod p$$

两边同除以 $A$，得到标准的三项式方程：

$$t^n - u t^{n-1} - v = 0 \pmod p$$

其中 $u = B \cdot A^{-1}$， $v = C \cdot A^{-1}$。

根据费马小定理，令 $m = n \bmod (p-1)$，方程等价于求解（$m>0$）：

$$f(t) = t^m - u t^{m-1} - v = 0 \pmod p$$

此时我们只需找出一个满足 $f(t) \equiv 0 \pmod p$ 的根 $t$。对于一个随机生成的 $(u, v)$ 组合，该方程存在根的概率约为 $1 - e^{-1} \approx 63.2\%$。如果无根就重新随机一组 $\mathbf{v}$。

求根可以使用 Cantor-Zassenhaus 快速求解。

时间复杂度我不太清楚，但应该挺快的。