二次剩余与 Cipolla 算法

本文主要是介绍二次剩余与 Cipolla 算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

对于 $P,n$，若存在 $x$，满足：

\[x^2≡n\pmod p \]

则称 $n$ 为模 $P$ 意义下的二次剩余。

定义如下：

\[\left(\frac{n}{p}\right)= \begin{cases} 1,&n\text{ 在模 $p$ 意义下是二次剩余}\\ -1,&n\text{ 在模 $p$ 意义下是非二次剩余}\\ 0,&n\equiv0\pmod p \end{cases} \]

对于勒让德符号，有：

\[\left({n\over p}\right)\equiv n^{p-1\over 2}\pmod{p} \]

证明：

若 $n≡0\pmod p$，显然该式子成立。

若 $n$ 在模 $p$ 意义下是二次剩余，即存在 $x^2≡n\pmod p$，那么就有 $x^{p−1}≡1\pmod p$，根据费马小定理显然 $x$ 存在。

若 $n$ 在模 $p$ 意义下是二次非剩余，我们仍假设存在 $x^2≡n\pmod p$，从而有 $x^{p−1}≡−1\pmod p$，由费马小定理，显然 $x$ 不存在。

这篇关于二次剩余与 Cipolla 算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程