二次剩余

Published: June 15, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 二次剩余
• 欧拉准则
• Toneli-Shanks算法

二次剩余

在数论中，一个整数$x$对于$p$的二次剩余是指$x^2\pmod p$，如果一个数$y$可以表示$x^2\pmod p$，那么称$y$是模$p$的二次剩余，否则称$y$是模$p$的二次非剩余。

如果$p$是素数，考虑到$a^2=b^2\Rightarrow (a-b)(a+b)=0$，因此可以认为在模$p$的剩余类环中有$\frac{p-1}{2}$个二次剩余（不考虑$0$），同时也有$\frac{p-1}{2}$个二次非剩余。

欧拉准则

当$p$是素数时，要判断一个数$y$是否是模$p$的二次剩余，可以借助欧拉准则。

一个数y是模p的二次剩余，当且仅当$y^{\frac{p-1}{2}}=1\pmod p$。

Toneli-Shanks算法

Toneli-Shanks算法可以用于求解$x^2=y\pmod p$，这里$p$是素数，$y$已知，求$x$。算法流程如下：

如果$p=2$，则一定有$y=x$。

否则我们需要先通过欧拉准则确定有解。假如有解，我们随机一个$a$，满足$w=a^2-y$是二次非剩余。之后我们证明$x=(a+\sqrt{w})^{\frac{p+1}{2}}$。

证明：

由于费马小定理知道对于任意数$t\neq 0\pmod p$都有$t^{p-1}=1$。因此可以继而推出$t^{\frac{p-1}{2}}=\pm 1$。

$$(a+\sqrt{w})^{p+1}=(a+\sqrt{w})^p(a+\sqrt{w})$$

其中

$$(a+\sqrt{w})^p=\sum_{i=0}^p{p\choose i}a^i\sqrt{w}^{p-i}$$

由于${p \choose i}\pmod p$非0仅在$i=0$和$i=p$的情况下会发生，因此$(a+\sqrt{w})^p=a^p+\sqrt{w}^p$，其中$a^p=a^{p-1}a=a$，而$\sqrt{w}^p=\sqrt{w}^{p-1}\sqrt{w}=w^{\frac{p-1}{2}}\sqrt{w}=-\sqrt{w}$（注意$w$不是二次剩余）。

$$(a+\sqrt{w})^p=(a+\sqrt{w})(a-\sqrt{w})=a^2-w=y$$

因此$x=(a+\sqrt{w})^\frac{p+1}{2}$。

注意上面的$\sqrt{w}$不存在，但是满足$\sqrt{w}^2=w$。我们可以用类似复数虚部的方式来表示它。可以证明当$x$存在的时候，这时候一定有$(a+\sqrt{w})^\frac{p+1}{2}$只包含实部。

这个算法的时间复杂度取决于$a$选择的次数，考虑到我们在二次剩余那节说过$[1,p-1]$之间的二次剩余和二次非剩余是相同数量的，这里可以简单认为取到w为非二次剩余的概率为$\frac{1}{2}$，因此期望次数为$2$，故时间复杂度应该为$O(\log_2p)$。