浅谈二次剩余

概述

这篇博客讨论一下我对二次剩余肤浅的理解
二次剩余主要用于解决在模意义下开根的问题
如果存在一个x使得$x^2\equiv n(\mod P)$则称n在模P意义下是二次剩余的,否则称n在模P意义下是非二次剩余的。
在IO中的大多数情况下,P是一个奇质数,在这样的条件下有一个快速的算法来求出一个符合条件的非负整数x。

二次剩余判别式

[引理1]$n^{\frac{P-1}{2}}\equiv -1(\mod P) \Rightarrow $n在模P意义下是非二次剩余
证明:
当n=0时,显然成立
当n>0时,
假定n是二次剩余
那么存在$x^2\equiv n(\mod P)$
根据费马小定理,$x^{P-1}\equiv 1(\mod P)$
所以$n^{\frac{P-1}{2}}\equiv 1(\mod P)$
不符合条件,所以n在模P意义下是非二次剩余。
证毕
[引理2]n在模P意义下是非二次剩余 $\Rightarrow n^{\frac{P-1}{2}}\equiv -1(\mod P) $
证明:
当n=0时显然成立
当n>0时,
根据扩展欧几里德可知,对于任意$x\in [1,P-1]$,存在唯一一个$y\in [1,P-1]$,且$xy\equiv n(\mod P)$
由于n是非二次剩余,所以$x\not =y$
也就是说我们可以将这P-1个数两两配对乘起来,每一对的积都是n
所以有$(P-1)!\equiv n^{\frac{P-1}{2}}$
根据威尔逊定理,上式在模P意义下等于-1
证毕
总上所述,n是模P意义下的二次剩余等价于$n^{\frac{P-1}{2}}\equiv -1$
我们可以用这个式子判断n是否是二次剩余

一种神奇的求法

[引理3] 对于任意模P意义下的非二次剩余w和任意非负整数a,有$(a+\sqrt{w})^P \equiv a-\sqrt{w}(\mod P)$
证明:
对左边展开可得:
$\displaystyle\sum_{i=0}^P a^i \sqrt{w}^{P-i} C_P^i$
由于大多数项的$C_P^i$在模P意义下都是0,所以上式等于
$\sqrt{w}^P+a^P$
$\equiv w^{\frac{P-1}{2}}\sqrt{w}+a^{P-1}a$
$\equiv a-\sqrt{w}$
证毕
那么
$(a+\sqrt{w})^{\frac{P+1}{2}} \equiv \sqrt{a^2-w}$
也就是说,我们只需要找出一组a和w,使得$n=a^2-w$
就可以通过这个式子得到$\sqrt{a^2-w}$
根据元根的性质可以发现非二次剩余的密度是很大的,所以我们随机a就可以在期望$O(1)$次的判断后得到一组合法的a和w
时间复杂度期望$O(\log P)$
代码:

发表评论