二次剩余多项式高斯引理理相关问题

来源：蜘蛛抓取(WebSpider) 时间：2019-05-19 04:09 标签： 高斯引理

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

引理：方程有解当且仅当

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

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

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

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

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

可以证明和那么最终得到

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

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

0,p\)得到后面的等号用费马小定理囷\(\omega\)是模\(p\)的二次非剩余。然后

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

p=2时特判輸出1不然会WA。龟速乘会TLE

我要回帖

更多关于 高斯引理 的文章

 

随机推荐