二次剩余

Summary

若存在 x 使 x 的平方模 p 等于 n，则称 n 是模 p 的二次剩余。欧拉判别法给出：对奇质数 p，n 是二次剩余当且仅当 n 的 (p−1)/2 次方模 p 等于 1。Cipolla 算法用于求出一个解，先随机找 a 使 a 的平方减 n 是非二次剩余，再在扩域中计算 a 加上根号下 (a 的平方减 n) 的 (p+1)/2 次方，其结果即为原方程的一个解，时间复杂度为 O(log p)。

参考资料

• 二次剩余 - OI Wiki

简介

若存在 $x$ 使 $x^2\equiv n\pmod p$，则称 $n$ 是模 $p$ 的 二次剩余。由 欧拉判别法，对奇质数 $p$，$n$ 是二次剩余当且仅当 $n^{(p-1)/2}\equiv 1\pmod p$。

Cipolla 算法 用于求出一个解：先随机找 $a$ 使 $a^2-n$ 是非二次剩余，在扩域 $\mathbb F_p(\sqrt{a^2-n})$ 中计算 $(a+\sqrt{a^2-n})^{(p+1)/2}$ 即为一个解，时间复杂度 $O(\log p)$。

例题

洛谷 P5491 【模板】二次剩余

$T$ 组询问，每组给定整数 $n$ 与奇质数 $p$，求同余方程 $x^2\equiv n\pmod p$ 的所有解。