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

· · 算法·理论

省流：对于一个多元的 n 次齐次多项式减去一个 n - 1 次的多元齐次多项式等于常数，有一种简单的 O(\sqrt {Pm}\times Q) ，复杂度的做法（m 为多项式中每项的元数和，Q 是快速幂复杂度）。

例如本算法可以解决如下问题：

x^{1000000} + y^{1000000} + z^{1000000} + x^{999999}y+x^{999999}z-y^{999999}z = C + x^{999999} + y^{999999} + z^{999999}

首先考虑如何求出若干的 C = 0 的解：

随机 r_1, r_2，我们另 y = r_1x, z = r_2x，那么我们可以发现等式可以形如 Ax^{1000000} = Bx^{999999}，取 x = \dfrac B A 即可。

假设我们现在得到了 C = 0 的解，其中左式和右式均等于 k。

那么假设 xyz 同时乘上 R，则此时两式差为 k(R^{1000000}-R^{999999})。

假设我们现在有若干个 C = 0 的解和若干个 (R^{1000000}-R^{999999})，那么我们只要找到两个乘起来 =C 的一组解即可。

所以我们将随机若干 C = 0 的解存入哈希表，然后随机 R 寻找 \dfrac C {(R^{1000000}-R^{999999})} 是否在哈希表中即可。

推广上述做法：

然后求 C = 0 的解，我们就先随机若干个 r_2,r_3...r_t，表示 x_a = r_ax_1，那么此时解 C = 0 等价于原式形如 Ax^{1000000} = Bx^{999999}，取 x=\dfrac B A，并将解存入哈希表中。

然后我们随机若干 R，并检验哈希表中是否存储了 \dfrac C {R^n - R^{n-1}}，如果有则将每个数乘上 R 作为结果返回。

假设第一步去了 s 个解，那么第二步期望要 O(\dfrac P S) 步。

即快速幂次数为为 O(sm+\dfrac P s)，取 s = \sqrt {\dfrac P m} 得到复杂度 O(\sqrt{Pm}\times Q)，Q 为快速幂复杂度（说不定可以省去）。