二次剩余

定义

一个数 ，如果不是 的倍数且模 同余于某个数的平方，则称 为模 的 二次剩余。而一个不是 的倍数的数 ，不同余于任何数的平方，则称 为模 的 二次非剩余。

对二次剩余求解，也就是对常数 解下面的这个方程：

通俗一些，可以认为是求模意义下的 开平方 运算。对于更高次方的开方的简单讨论，可以参见离散对数一文。

这里只讨论 为奇素数 的求解方法。后文可能在模 显然的情况下简写成二次（非）剩余。

Legendre 符号

且是模的二次剩余且不是模的二次剩余

通过 Legendre 符号可以判断一个数 是否为二次剩余，具体判断 是否为模 的二次剩余，需要通过 Euler 判别准则来实现。

下表为部分 Legendre 符号的值

Euler 判别准则

定义

对于奇素数 和 有

若有解若无解

证明

引理：令 为素数和模 意义下原根 并令 。那么 有解当且仅当 为偶数。

引理的证明：（充分性）假设 有解为 对于某个 成立。那么 。因此 （Fermat 小定理），而 为偶数，所以 为偶数。

（必要性）假设 为偶数，那么

而因为 为偶数，所以 为整数，因此 有解为 。

因为 为模 的原根，那么 的阶为 所以 且根据阶的定义，对于所有 满足 都有 ，所以

考虑同余方程 。因为 且 对于某个 满足 成立。若同余方程存在解，则 为偶数，通过上述引理和 Fermat 小定理有

所以当 时解存在。

又因上述引理， 无解时 为奇数。假设 为奇数，那么

即得 Euler 判别准则，也可以推断出 Legendre 符号为完全积性函数。

二次剩余和二次非剩余的数量

定义

对于奇素数 和集合 ，在模 意义下二次剩余的数量等于二次非剩余的数量。

证明

引理：对于 和奇素数 ， 恰有 个解。

引理的证明：根据 Fermat 小定理，当 时有 。因此对于每个 ， 是 的解。通过因式分解 有

其中 。根据 Lagrange 定理 我们知道 最多有 个解。因为 有 个解，所以显然 至少有 个解。如果只考虑 ，我们知道最多有 个解。所以 恰有 个解。

根据 Euler 判别准则，对于 显然 ，又因上述引理所以 有 个解，而集合中有 个元素，所以也有 个二次非剩余。

特殊情况时的算法

对于同余方程 ，其中 为奇素数且 为二次剩余在 时有更简单的解法，考虑

小定理

那么 为一个解。

Atkin 算法

过程

仍然考虑上述同余方程，此时 ，那么令 和 那么此时 且 为一个解。

证明

其中 在模形如 或 的素数时为二次非剩余，这由二次互反律给出，由于证明较复杂，读者可参考 Wikipedia。

那么

得证。

Cipolla 算法

定义

Cipolla 算法用于求解同余方程 ，其中 为奇素数且 为二次剩余。

过程

算法可描述为找到 满足 为二次非剩余， 为一个解。

在复数域 中，记 后 。考虑令 和实系数多项式的集合 对 取模后的集合记作 ，那么集合中的元素都可以表示为 的形式，其中 ，又因为 ，考虑多项式的运算可以发现 中元素的运算与 中一致。

后文考虑对于系数属于有限域 的多项式 和对 取模后的集合 中的运算。

选择 ：

若 那么 为二次剩余，此时解显然为 。所以假设 。使得 为非零二次剩余的选择有 个，而使得 的选择恰有两个，那么有 种选择可以使得 为二次非剩余，使用随机方法平均约两次可得 。

证明

令 和 那么有 且 。

为二次非剩余

又因为二项式定理

可以发现只有当 和 时由于没有因子 不会因为模 被消去，其他的项都因为有 因子被消去了。所以

所以

若 且

所以 的系数必须为零即 此时考虑 Legendre 符号为完全积性函数可知 显然为二次剩余，不符合定义。因此 且 。

Legendre 算法

定义

对于同余方程 ，其中 为奇素数且 为二次剩余。Legendre 算法可描述为找到 满足 为二次非剩余，令 ，那么 且 。

证明

考虑选择一个 满足 ，那么 为二次非剩余，所以

存在环态射

那么

所以 而 。

Tonelli-Shanks 算法

定义

Tonelli-Shanks 算法是基于离散对数求解同余方程 的算法，其中 为奇素数且 为模 的二次剩余。

令 其中 为奇数。仍然使用随机方法寻找 满足 为二次非剩余。令 且 ，那么存在整数 满足 。若 为二次剩余，那么 为偶数且 。

证明

而

所以 的阶为 ，又因为 是 的解，所以 是 的幂次，记 。

若 是二次剩余，那么

所以 为偶数，而

剩下的问题是如何计算 ，Tonelli 和 Shanks 提出一次确定 的一个比特。令 在二进制下表示为 其中 。

因为 是二次剩余，所以开始时 ，然后计算 然后 等等，由以下公式给出

正确性显然。

习题

【模板】二次剩余

「Timus 1132」Square Root

参考文献

build本页面最近更新：2022/9/18 20:58:01，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：hly1204, ShaoChenHeng, Chrogeek, Enter-tainer, Great-designer, iamtwz, nanmenyangde, sshwy, StudyingFather, TachikakaMin, Xeonacid, xyf007
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论