二次剩余与二次剩余核

二次剩余与二次剩余核

二次剩余概念

例如

1的平方为1， 除以10后的余数为1 2的平方为4， 除以10后的余数为4 3的平方为9， 除以10后的余数为9 4的平方为16，除以10后的余数为6 5的平方为25，除以10后的余数为5 6的平方为36，除以10后的余数为6 7的平方为49，除以10后的余数为9 8的平方为64，除以10后的余数为4 9的平方为81，除以10后的余数为1 10的平方为100，除以10后的余数为0

故0， 1，4，5，6，9中 与10互质的整数1，9为10的二次剩余

主要给出一些性质：

• 总存在一个整数 对 整数p取余之后的结果一定都可以取到(0, 1, 2, … p-1)中的任意一个数。
• 任意一个整数的平方后，对整数p取余之后的结果确无法取到(0, 1, 2, … p-1)中的任意一个整数。

关于上诉性质的说明详见：
平方剩余

二次剩余核

二次剩余核也称平方剩余核

对一个整数n进行质因子分解，可得到如下表达式

其中pj均为质数，对pj上面指数i进行除2求余之后得到的结果即为n的二次剩余核，例如18的二次剩余核为2
计算过程如下：

性质:
两个二次剩余核相等的整数n1，n2 的乘积一定可以表示为某个整数n的平方
即： n1 * n2 = n * n

那么如何求一个整数n的二次剩余核呢？其实可以反过来求，求[1, n] 中所有整数的二次剩余核，

• 首先[1, n] 中所有整数的二次剩余核的范围一定也是[1, n]\
• 其次可以先依次求二次剩余核的i的所有整数是哪些？那么如何求呢？
• 假设求 二次剩余核为i的整数有哪些？根据定义一定可以表示为
  i * k^2 = n，通过不断的调整i，k就可以求出[1, n] 中所有整数的二次剩余核了