二次剩余（Cipolla's algorithm）学习笔记

Oct 10, 2016 · 2 min read · number theory 二次剩余剩余系

先放资料。

前置技能点：

剩余系**:设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]****，**

这m个数**{0,1,2,****…****m-1}**称为一个完全剩余系，

每个数称为相应类的代表元。

当m=10（偶数）时候，则{0,1,2,3,4,5,6,7,8,9}是最小非负完全剩余系

{-5,-4,-3,-2,-1,0,1,2,3,4,5} 是绝对值最小完全剩余系

{-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小

{1,2,3,4,5,6,7,8,9,10}是最小正完全剩余系

简化剩余系:在每个剩余类选取至1个与m互素代表元构成简化剩余系。

当m=10则,{0,1,2,3,4,5,6,7,8,9} 完全剩余系

{1,3,7,9}是简化剩余系(x,10)=1

当m=5则，{0,1,2,3,4}为完全剩余系,

{1,2,3,4}是简化剩余系，因为除去余0(正好是倍数)外，其它都互素。

f(m)=欧拉函数=|{t|0<t<m, (t, m)=1}|

=简化剩余系的元素个数

维基百科_高斯引理

设_p_为奇[质数](https://zh.wikipedia.org/wiki/)，_a_是一个与_p_[互质](https://zh.wikipedia.org/wiki/)的整数。考虑以下数组：![{\displaystyle a,2a,3a,\dots ,{\frac {p-1}{2}}a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82941c63fd5e49cf0b57612ee5e895d1e1c9096c) 以及它们对_p_的[最小非负剩余](https://zh.wikipedia.org/w/index.php?title=&action=edit&redlink=1)。这些剩余两两不等（**kk:这些剩余两两不等的证明：可以考虑反证，假设两个不同的数x,y对于p同余，那么x-y和0关于p同余，而x-y同时关于a同余，a与p互质，矛盾。因此这些剩余两两不等**），因此我们共有![\frac{p-1}{2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a733b8495b0d55ed5bc9d795b7b6821efb1d858b) 个两两不等的介于1和_p（_**kk:这里似乎有问题，如果剩余是在1..p之间，那么前面应该是说最小正剩余而不是最小非负剩余，最小非负剩余应该是在0..p-1之间**_）_之间的整数：![{\displaystyle t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7992b0d1c192f11821dce891b5f16dffdb35c536) 。设其中有_n_个数比_p_/2大，那么高斯引理声称：![{\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b89fef980b3b0a785356b6960fd49e257aa2b16)
上式左边是勒让德符号，当其值为+1时，表示_a_是模_p_的二次剩余；其值为-1时，表示_a_是模_p_的二次非剩余。

用通俗的语言来说，就是： $t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}}$ 里面比_p_/2大的有偶数个，那么_a_是模_p_的二次剩余，如果有奇数个，那么_a_是模_p_的二次非剩余。

正片：

维基百科_勒让德符号

定义：

勒让德符号![({\tfrac {a}{p}})](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ebb252decd96b7adf4d3fffdda2c15b718c7420) （有时为了印刷上的方便，写成(_a_|_p_))有下列定义：

![\left({\frac {a}{p}}\right)={\begin{cases}\quad 0\\+1\\-1\end{cases}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddbfff4690a7d39fe7c2fcd69885dc8f36f2ed7c)

如果![a\equiv 0{\pmod {p}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30d65a6f62fe8c414ef6c4b123da631d1125594f)

如果![a\not \equiv 0{\pmod {p}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/520a34d8efca5436576b29f6765af091ad07b271)
，且对于某个整数 $x,x^{2}\equiv ;a{\pmod {p}}$

如果不存在整数![x](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
，使得 $x^{2}\equiv ;a{\pmod {p}}$ 。

如果(a|p) = 1，a 便称为二次剩余(mod p)；如果(a|p) = −1，则 a 称为二次非剩余(mod p)。通常把零视为一种特殊的情况。

性质：

勒让德符号有许多有用的性质，可以用来加速计算。它们包括：

  * ![\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c8876ab646dd7c9976bc54dd7487527f77bd202)

（它是一个**完全积性函数**(kk:g(a)g(b)=g(ab)对于任意正整数a,b都成立，不需要gcd(a,b)=1，完全积性真是爽哭了。。。。)。这个性质可以进一步理解为：两个剩余或非剩余的乘积是剩余，一个剩余与一个非剩余的乘积是非剩余。（kk:因为负负得正，正正得正...））

  * 如果_a_ ≡ _b_ (mod _p_)，则![\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)](https://wikimedia.org/api/rest_v1/media/math/render/svg/22c53d660aed6373e99b8e0feb7d9801186b2d41)



  * ![\left({\frac {a^{2}}{p}}\right)=1](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5b6f43df4f40202dbf365146ae39d7037387df5)



  * ![{\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}+1{\mbox{ if }}p\equiv 1{\pmod {4}}\\-1{\mbox{ if }}p\equiv 3{\pmod {4}}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd3bcfb31b3ac3ef72a6838ba0d0c58a2f236f74)

这个性质称为二次互反律的第一补充。

  * ![{\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}7{\pmod {8}}\\-1{\mbox{ if }}p\equiv 3{\mbox{ or }}5{\pmod {8}}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d90e3a78bfe75d1c4f4bfdd49690bd3af4673562)

这个性质称为二次互反律的第二补充。一般的二次互反律为：

  * 如果_p_和_q_是奇素数，则![\left({\frac {q}{p}}\right)=\left({\frac {p}{q}}\right)(-1)^{{{\frac {p-1}{2}}{\frac {q-1}{2}}}}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/966e6a0e5a66971e0c4d850b4a1627a598863d46)

参见二次互反律和二次互反律的证明。

以下是一些较小的_p_的值的公式：

  * 对于奇素数_p_，![\left({\frac {3}{p}}\right)=(-1)^{\left\lceil {\frac {p+1}{6}}\right\rceil }={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}11{\pmod {12}}\\-1{\mbox{ if }}p\equiv 5{\mbox{ or }}7{\pmod {12}}\end{cases}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d1c563452f82cfaf77baaecb82ed16888381a6b)



  * 对于奇素数_p_，![\left({\frac {5}{p}}\right)=(-1)^{\left\lfloor {\frac {p-2}{5}}\right\rfloor }={\begin{cases}+1{\mbox{ if }}p\equiv 1{\mbox{ or }}4{\pmod 5}\\-1{\mbox{ if }}p\equiv 2{\mbox{ or }}3{\pmod 5}\end{cases}},](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e1ed5877d9a39798e4afdb699e61d13b8071e59)

但一般直接把剩余和非剩余列出更简便：

  * 对于奇素数_p_，![\left({\frac {7}{p}}\right)={\begin{cases}+1{\mbox{ if }}p\equiv 1,3,9,19,25,{\mbox{ or }}27{\pmod {28}}\\-1{\mbox{ if }}p\equiv 5,11,13,15,17,{\mbox{ or }}23{\pmod {28}}\end{cases}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a70b4a7cc4d99b0842fa9b6bc71209398f6f8eeb)

勒让德符号(a|p)是一个狄利克雷特征(mod p)。

计算勒让德符号的一个例子：

$\left({\frac {12345}{331}}\right)$

$=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right)$ （完全积性）

$=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right)$ （161和823关于331同余）

$=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right)$ （完全积性）

$=(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right)$ （二次互反律）

$=-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right)$ （同余数）

$=-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3}{23}}\right)^{2}$ （完全积性，平方的形式值一定为1）

$=-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1.$ （分别计算，可以参考小素数时的分段函数，具体的计算方法见下文）

维基百科_欧拉准则（用来计算勒让德符号）

若![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36) 是奇[质数](https://zh.wikipedia.org/wiki/)且![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36) 不能整除![d](https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab) ，则：
![d](https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab)
是模 $p$ 的二次剩余当且仅当： $d^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$
![d](https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab)
是模 $p$ 的非二次剩余当且仅当： $d^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$

**以勒让德符号表示，即为： $d^{\frac {p-1}{2}}\equiv \left({\frac {d}{p}}\right){\pmod {p}}$ **

例子一：对于给定数，寻找其为二次剩余的模数

令_a_ = 17。对于怎样的质数_p_，17是模_p_的二次剩余呢？

根据判别法里给出的准则，我们可以从小的质数开始检验。

首先测试_p_ = 3。我们有：17(3 − 1)/2 = 171 ≡ 2 (mod 3) ≡ -1 (mod 3)，因此17不是模3的二次剩余。

再来测试_p_ = 13。我们有：17(13 − 1)/2 = 176 ≡ 1 (mod 13)，因此17是模13的二次剩余。实际上我们有：17 ≡ 4 (mod 13)，而22 = 4.

运用同余性质和勒让德符号可以加快检验速度。继续算下去，可以得到：
对于质数_p_ =![{\displaystyle 13,19,\cdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/13f9e1c9d7777e4eaa86f9c200cb0a5dfa30ae89)
，(17/p) = +1（也就是说17是模这些质数的二次剩余）。
对于质数_p_ =![{\displaystyle 3,5,7,11,23,\cdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ce5efd99278b3d8563cec3f661de8071a7c7b0a)
，(17/p) = -1（也就是说17是模这些质数的二次非剩余）。
（**kk:简单得说，就是从小到大枚举质数p，验证a^((p-1)/2)）%p等于1还是-1.）**

例子二：对指定的质数_p_，寻找其二次剩余

哪些数是模17的二次剩余？

我们可以手工计算：（kk:手算考虑数的平方是因为，勒让德符号是完全积性函数&& $\left({\frac {a^{2}}{p}}\right)=1$ ）
12 = 1
22 = 4
32 = 9
42 = 16
52 = 25 ≡ 8 (mod 17)
62 = 36 ≡ 2 (mod 17)
72 = 49 ≡ 15 (mod 17)
82 = 64 ≡ 13 (mod 17)
于是得到：所有模17的二次剩余的集合是 ${1,2,4,8,9,13,15,16}$ 。要注意的是我们只需要算到8，因为9=17-8，9的平方与8的平方模17是同余的：92 = (−8)2 = 82 ≡ 13 (mod 17).（同理不需计算比9大的数）。
但是对于验证一个数是不是模17的二次剩余，就不必将所有模17的二次剩余全部算出。比如说要检验数字3是否是模17的二次剩余，只需要计算3(17 − 1)/2 = 38 ≡ 812 ≡ ( − 4)2 ≡ − 1 (mod 17)，然后由欧拉准则判定3不是模17的二次剩余。

维基百科_二次互反律

对于两个奇[素数](https://zh.wikipedia.org/wiki/)![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36) 和 ![q](https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d) ，![\left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)=(-1)^{{{\frac {(p-1)(q-1)}{4}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea3d157eba9f88a16c19f7606afa04873c76a2b9)
其中 $\left({\tfrac {p}{q}}\right)$ 是勒让德符号。

关于二次互反律的证明就不多说了。。。据说高斯一次给出了五个（还是七个？)，到现在一共有200+种证明。

然后。。。感觉。。。。二次互反律。。。。太神了。。。。太美了。。。。真的被震撼到了orz

wiki_Cipolla's algorithm

acdreamer_二次同余方程的解二次剩余Cipolla算法学习小记