设整数,如果存在,满足,那么称是模的二次剩余,否则就称为模的二次非剩余,用表示模的二次剩余集合,用表示模的二次非剩余集合
针对质数的二次剩余判定,对于质数,任意,的充分必要条件为
的充分必要条件为
针对合数的二次剩余判定,,那么的充分必要条件为:
对于质数,中有个元素是模的二次剩余,另外个元素是模的二次非剩余
对于两个质数的乘积,那么里恰好有1/4的数,也就是个是二次剩余,一般来说,如果合数n有k个质数因子,那么中的元素中有是二次剩余
对于任意质数,和任意,定义勒让德符号(Legendre_symbol)为
勒让德符号计算方法
对于合数, 其素因子(可重复),任意整数,定义雅可比符号(Jacobi symbol)
注意:雅可比符号不能确定一个数是否是对模的二次剩余(除非是质数),比如
但7并不是143的二次剩余
勒让德符号和雅可比符号也可统一简写为 ,或者
对于质数,如果,那么方程
在有两个解,也就是说a有两个平方根,其中一个在区间,另一个在区间,而且,其中一个平方根也属于模的二次剩余,称为主平方根(pricipal square root)
对于方程
有两个解, 其中
对于方程 如果, 如果, 如果,
对于一般情况的质数,使用Tonelli–Shanks算法求解
参考: https://www.johndcook.com/blog/quadratic_congruences/
对于方程,有解 方程,当时有2个解, 方程, 当时有4个解,
求解方程, 方程有解的充分必要条件是, 也就是a是模p的二次剩余 方程有两个解,使用Hensel's lemma算法 设是的解,有存在使得等式成立,那么是方程的解
求解方程
其中,首先解方程
以为例,使用扩展欧几里得算法求解
同理,求方程
所以,最终方程的两个解是
对于合数, 整数, 求解方程 首先求解模质数方程
然后根据中国剩余定理,解方程组
得到,由于每个有两个解,所以最终有个解
按照模为质数的方法解方程
按照中国剩余定理,解以下四个方程组
得到四个解
如果不知道的素因子,那么就模的平方根是非常困难的问题