2.8　二次剩余

设，如果不是的倍数且模同余于某个数的平方，则称为的二次剩余。而一个不是的倍数的数，不同余于任何数的平方，则称为的二次非剩余。也就是说，二次剩余[9] 是指的平方除以得到的余数，记作。

定义2.8.1　二次剩余(Quadratic Residue)

给定的一个整数是二次剩余的话，那么它必须满足：

是有解的。其中为素数且。如果不满足，则称为的二次非剩余。

例2.8.1　列举5、7、11的二次剩余。

整理5的二次剩余时，可以发现因为任意与5互素的数，也就必然与1、2、3、4中某个数关于模5同余。因此模5的二次剩余为1、4 ，二次非剩余为2、3 。模7的二次剩余为1、2、4 ，二次非剩余为3、5、6 。模11的二次剩余为1、3、4、5、9 ，二次非剩余为2、6、7、8、10 。

如果是不被素数整除的整数，那么方程则可能无解，也有可能有两个不同余的解。

定理2.8.1　素数的二次剩余

设为素数，那么一个数的二次剩余的数目正好是的一半，即有个。且

是模的全部二次剩余。

证明

假设，其中。根据公式可以得到所有的二次剩余，代人可得：

此时意味着和实际上指的是同一个二次剩余，因此只需要计算即可找到所有的二次剩余。

接着计算得出的二次剩余是否两两不等。另设整数，使得

因此等式成立。

勒让德符号也称二次特征，是由法国数学家阿德里安-马里・勒让德（Adrien-Marie Legendre）发明的。它在数论中有广泛的应用，可以用来判断二次剩余方程是否有解，并提供了一种方法来确定解的性质。在代数数论和密码学等领域，勒让德符号是研究整数的重要工具。例如在后续章节介绍椭圆曲线密码系统时，它被用来判断点的阶是否为素数。

定义2.8.2　勒让德符号(Legendre Symbol)

其中是奇素数，是整数。

那么如何知道一个数是不是素数的二次剩余呢？这时候就可以使用欧拉判别法，它是一个最基本的二次剩余判别的方法。

定理2.8.2　欧拉判别法(Euler’s Criterion)

设为奇素数，并且，则：

根据上述的欧拉判别法可知：

所以

这也是勒让德符号的性质之一。除此之外，它还有以下几个性质。

1）如果，则。

2)。

3)。

定理2.8.3　二次互反律(Law of Quadratic Reciprocity)

如果都是奇素数且不同，那么:

例2.8.2　使用二次互反律，计算和的值。

解：

因此如果都是素数，那么是偶数，于是就可以知道：

例2.8.3　判断3和4是不是5的二次剩余。

解：因为，所以3是5的二次非剩余；因为，所以4是5的二次剩余。

欧拉判别法的Python代码如下:

 1  def EulerCriterion(n, p):
 2      n = n % p
 3
 4      for x in range(2, p, 1):
 5          if ((x * x) % p == n):
 6              return True
 7      return False

雅可比符号是勒让德符号的推广，它由德国数学家卡尔・雅可比（Carl Jacobi）发明。雅可比符号在勒让德符号的计算中非常有用。

定义2.8.3　雅可比符号(Jacobi Symbol)

设，为正奇数且，并与互素，雅可比符号可以表示为：

其中不一定相同。它是勒让德符号的延伸，不过当很大且质因数未知时，根据这个定义计算并不容易。但是仍然可以通过下面的递归来计算：

例2.8.4　计算。

解：

计算雅可比符号的Python代码如下:

 1  #计算雅可比符号Jacobi Symbol
 2  def jacobi(a, n):
 3      assert(n > a > 0 and n%2 == 1)
 4      t = 1
 5      while a != 0:
 6          while a % 2 == 0:
 7              a /= 2
 8              r = n % 8
 9              if r == 3 or r == 5:
10                  t = -t
11          a, n = n, a
12          if a % 4 == n % 4 == 3:
13              t = -t
14          a %= n
15      if n == 1:
16          return t
17      else:
18          return 0
19
20  j = jacobi(24, 601)