二次剩余

Published: by Creative Commons Licence

  • Tags:

二次剩余

在数论中,一个整数$x$对于$p$的二次剩余是指$x^2\mod p$,如果一个数$y$可以表示$x^2\mod 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\mod p$。

Toneli-Shanks算法

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

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

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

证明:

由于费马小定理知道对于任意数$t\neq 0\mod 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}\mod 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)$。