二次剩余学习笔记

精通多项式的大家一定见过以下一个问题(如果你实在要说不精通的话就去看 Imakf 的博客，看完就精通了)。

1.多项式开根(加强版)

给定一个 $n-1$ 次多项式 $A(x)$ ，求一个在  $\bmod {x^n}$ 意义下的多项式 $B(x)$ ，使得 $B^2(x)\equiv A(x)\pmod {x^n}$ ，答案取常数项更小的的 $\sqrt{A(x)}$。

多项式的系数在 $\bmod 998244353$ 的意义下进行运算。

不保证 $a_0=1$。

先来一波多项式部分的推导：

不妨假设我们求出了 $H^2(x)\equiv A(x)$，现在要求 $G^2(x)\equiv A(x)$。

$$G(x)-H(x)\equiv 0(\bmod x^(\frac{n}{2})\\ G^2(x)+H^2(x)-2G(x)H(x)\equiv 0(\bmod x^n)\\ 2G(x)H(x)\equiv G^2(x)+H^2(x)(\bmod x^n)\\ G(x)\equiv \frac{F(x)+H^2(x)}{2H(x)}(\bmod x^n)$$

然后就可以递归求解了。

那么现在递归到常数项的时候有一个问题：如何求 $x_0^2\equiv y(\bmod 998244353)$。

那么就要用到一个新知识：二次剩余。

这个玩意使用来求解方程：

$$x^2\equiv n(\bmod p)$$

这里要求 $p$ 是奇质数，我们不妨在这里设 $p$ 的原根为 $g$。

• 判定

判断一个数 $x$ 是不是二次剩余。

这个东西叫欧拉准则。

结论：

$x^{\frac{p-1}{2}}\equiv 1(\bmod p)$ 与 $x$ 是二次剩余等价。

推论：

$x^{\frac{p-1}{2}}\equiv -1(\bmod p)$ 与 $x$ 是非二次剩余等价。

根据费马小定理有 $x^{\frac{p-1}{2}}\equiv 1(\bmod p)\Leftrightarrow x^{2\cdot\frac{p-1}{2}}\equiv 1(\bmod p)\Leftrightarrow g^{k\cdot\frac{p-1}{2}}\equiv1(\bmod p)$ 。

可得 $k$ 一定为偶数，那么 $g^{\frac{k}{2}}$ 是 $x$ 开根的结果，所以 $x$ 是二次剩余，

由于$x^{\frac{p-1}{2}}\equiv 1 or-1(\bmod p)$ 。

• 求解

判定完了以后可以开始求解了。

我们可以先找到一个 $a$ 使得 $a^2-n\equiv 0$ 且 $a^2-n$ 是非二次剩余。

至于怎么找，因为非二次剩余数量是 $n/2$ 级别的，所以可以随机。

现在找到一个 $b$ 使得 $b^2 \equiv a^2-n$。

因为实际上实数域上涨不到这样的 $b$ 所以可以到复数域上找，只不过为了计算方便我们定义 $i^2=a^2-n$。

那么可以通过计算得出 $(a+i)^{p+1}\equiv n$。

所以得到 $(a+1)^{\frac{p+1}{2}}$ 是一个解， $-(a+1)^{\frac{p+1}{2}}$ 是另一个解。