二次剩余

今天要讨论的问题是解方程，其中是奇质数。

引理：

证明：由费马小定理，

引理：方程有解当且仅当

定理：设满足不是模的二次剩余，即无解，那么是二次

     剩余方程的解。

证明：由，前面的等号用二项式定理和，后面的等

     号用了费马小定理和是模的二次非剩余。然后

在算法实现的时候，对的选择可以随机，因为大约有一半数是模的二次非剩余，然后快速幂即可。

接下来我们来解另一个二次同余方程的解，其中，并且是奇质数。方法如下

先求出方程的一个解，那么进一步有

我们知道

那么也就是说

可以证明和，那么最终得到

这里由于不是素数，所以求逆元用扩展欧几里得算法即可。

例如：求方程的解

分析：利用上述方法求得，最终解得。

二次剩余

原文：http://www.cnblogs.com/zarth/p/7373750.html