CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:namespace:剩余和互反律 [2020/06/23 15:32]
great_designer [互反律与p进数的关系]
+++ 2020-2021:teams:namespace:剩余和互反律 [2020/06/23 17:42] (当前版本)
great_designer
@@ 行 15: / 行 15: @@
 <del>写完这四篇基本上可以出版一本初等数论教科书了。</del>
-<del>以下内容只是计划中，考期没有时间写。这个系列再下一篇就是多项式和组合数学了（如果还能写的话（如果暑假能写完的话（我看悬）））。</del>
+=====二次剩余与互反律=====
-<del>当然暑假写别的算法页面应该挑战性更强一些。</del>
+====二次Kronecker符号====
-<del>当然，第三篇还没写完。不出意外的话（没时间的话），本篇和第三篇基本会鸽了。</del>
-=====Euler判别法=====
-Euler判别法是对于计算机而言最简单的判断一个数a是不是模素数p的n次剩余的办法。
-对于人而言就太难了。人一般采用互反律等等的办法笔算。
-我们熟知模p的缩系乘法群是循环群，那么下面的结论就显然了。
-首先，如果p-1和n互素，那么a一定是n次剩余。因为这个时候n次方在p的缩系中是一个置换。
-如果n是p-1的倍数，显然缩系中只有1是n次剩余（p-1次剩余）。
-那么，如果p-1和n不互素，就可以将n替换为(n,p-1)。这个数一定是p-1的约数，只需要看a是不是(n,p-1)次剩余即可。
-于是，计算这个式子的值：
-$$a^{\frac{p-1}{(n,p-1)}}$$
-如果这个式子的值为1，说明a是n次剩余，否则就不是n次剩余。这就是欧拉判别法，一般用快速幂算法计算。
-另外，对于二次非剩余，这个式子的值一定是-1。其他的非剩余则不确定。
-=====原根的判定=====
-既然已经知道模p的缩系乘法群是循环群，那么就有很明显的推论：
-判断g是模素数p原根，则要求对于任意一个n，只要n与p-1不互素，g就不是n次剩余。
-这显然是一个等价命题。意思就是说，原根和剩余几乎是互斥的概念，原根如果是剩余，只有可能这个次数构成一一对应，即上文的互素。
-事实上，对于p-1的每一个因数d，只要判断g是不是d次剩余就够了。这个因数甚至可以改进为素因数q。即要求p-1的每一个素因数q：
-$$g^{\frac{p-1}{q}}$$
-这个式子都不是1，则g是原根。
-模p-1的原根总共有$\varphi(p-1)$个。在随机枚举g的情况下，显然当p-1的素因数非常少的时候，枚举到原根的概率大，最高能达到50%。但是当p-1的素因数很多的时候，枚举到的概率就非常小了。这个概率甚至可以任意趋近于0。总之无论什么情况，都需要枚举多次。
-=====BSGS离散对数算法=====
-BSGS（Baby Step Giant Step），即大步小步算法，常用于求解离散对数问题。该算法可以在根号p的时间内求解模p意义下的$\log_a b$。
-当然，如果a是原根，一定有解。否则不一定有解。
-由于群的阶是p-1，设待求的对数为：
-$$\log_a b=A\left\lceil\sqrt{p-1}\right\rceil-B$$
-于是A和B都不超过$\sqrt{p-1}$。变形一下就有：
-$$a^{A\left\lceil\sqrt{p-1}\right\rceil}\equiv ba^B \mod p$$
-分别存储等式的两边，用map存储其中一边的结果，枚举另一边时查找即可。
-因为时间复杂度是根号量级，在大素数情形很高，而反过来的快速幂却是对数量级，是复杂度低的算法，事实上也说明求对数是个世界级难题，至今还没有得到解决。
-=====Cipolla平方根算法=====
-由于三次方程的解法较为复杂，开三次方根的算法并不容易。但是在这里有一种简洁有效的开平方根的算法，它需要将研究对象进行域扩张，扩张到$Q(\sqrt{a^2-n})$上。
-对于一个二次剩余n，我们想对它开平方根，即求解：
-$$t^2\equiv n\mod p$$
-考虑方程：
-$$x^2-2ax+n=0$$
-这个方程的两根之积是n。因此根据Fermat-Eular定理，两根之积的p次方应该也是n。
-$${x_1}^p{x_2}^p\equiv n\mod p$$
-注意这里的两个根都未必是整数。下面分别考虑两个根单独的p次方是什么，即考虑：
-$${x_1}^p\mod p$$
-如果这个根本身是整数，那么根据Fermat-Eular定理，它的值应当回到这个根本身。
-不是整数的情形会怎样？在扩域$Q(\sqrt{a^2-n})$当中，没有引入p分之1作为因子。因此，下面的常见二项式展开结论应当成立：
-$${(a+b)}^p\equiv a^p+b^p\mod p$$
-这里的取模是对两个分量1和根号的系数取模。不妨取比较大的根x1（较小的根同理），于是：
-$${x_1}^p={(a+\sqrt{a^2-n})}^p\equiv a^p+{(\sqrt{a^2-n})}^p\equiv a+{(a^2-n)}^{\frac{p}{2}}\mod p$$
-由于a是整数，根据Fermat-Eular定理，a的p次方还是a。因此关键在于后面根号部分的p次方是多少，这部分未必满足Fermat-Eular定理。事实上，这一部分不满足Fermat-Eular定理。
-根据Euler判别法，根号下的部分的半群阶次方很好计算。在是二次剩余的时候为1，否则二次非剩余的时候为-1。即：
-$${(a^2-n)}^{\frac{p-1}{2}}\equiv 1\ or\ -1\mod p$$
-两边再乘一个这个数的根号就有：
-$${(a^2-n)}^{\frac{p}{2}}\equiv \sqrt{a^2-n}\ or\ -\sqrt{a^2-n}\mod p$$
-上文中，根是整数的情形，即根号可以被开出来，那么这里就是二次剩余，右面的根号系数为1，代回原式可以得到p次方后不变的结果，与之前结论吻合。
-但是，根不是整数的情形，对应根号下为二次非剩余，这里的同余式右端根号为负，即：
-$${(\sqrt{a^2-n})}^p\equiv -\sqrt{a^2-n}\mod p$$
-因此，**在p次方作用下，原方程的两个根交换了位置**：
-$${x_1}^p\equiv a-\sqrt{a^2-n}=x_2\mod p$$
-换位的前提，是根号下的数为二次非剩余，即这个根号开不出来的情形。
-那么这个结论有什么用呢？我们在两边再同乘一个x1：
-$${x_1}^{p+1}\equiv x_1x_2=n\mod p$$
-发现p+1恰好是偶数，而右边恰好是要开方的整数n。因此最开始的开方值t就应该是：
-$$t_1\equiv{x_1}^{\frac{p+1}{2}}\mod p$$
-这就是Cipolla平方根算法。第一步随机出一个a，使得a的平方减n是二次非剩余。然后只需计算x1的二分之p加1次方即可。由于二次剩余和二次非剩余恰好各占总体的一半，一般认为随机一次的a符合条件的概率是50%。
-对于四次方根的求解，可以用两次Cipolla算法来解决，也不算困难。然而对于三次方根就麻烦得多。
-=====一一映射情形的求根=====
-这里指当素数p不是tk+1情形的时候，t次方运算在p的缩系中是一一映射。那么这种情形的求根相当容易，甚至不需要用到上文的扩域。
-这里仅举个简单的例子作为参考。对于p是3k+2情形的时候，3次方运算是一一对应。我们已知下面的n，要求解x：
-$$x^3\equiv n\mod p$$
-首先根据Fermat-Eular定理，这个同余式一定是成立的：
-$$x^{3k+1}\equiv 1\mod p$$
-那么对n作k次方，就有：
-$$n^k\equiv x^{3k}\equiv x^{-1}\mod p$$
-那么再来一次数论倒数就完事了。即完整的式子是：
-$$n^{3k^2}=n^{k(p-2)}\equiv x\mod p$$
-其实上面的操作，就是缩系循环群里面，取对数之后，对3进行的数论倒数操作，即寻找一个逆映射。我们看到，3乘以3k方是9k方，再减去1之后，恰好是p-1即3k+1的倍数。因此，在缩系循环群的观点下，这样的逆映射就是跑了若干个整循环之后，恰好多跑出了一个幂次。这样类似于不定方程的思想就求解出了逆映射。
-同时也看到，当p是tk+1情形的时候，这个映射不是一一映射，那么就不能采用这种办法了。即p是3k+1情形的时候，无法用这种办法开三次方。
-=====Peralta算法开立方=====
-Cipolla算法开平方是一种特别优秀的算法，时间复杂度很低。而这里写出的Peralta算法仍旧属于一种暴力算法，比用原根与对数计算（至少根号量级）要优秀，相对Cipolla算法（对数量级）时间复杂度比较高。
-它的思路是这样的。要求解：
-$$x^3\equiv n\mod p$$
-其中p是3k+1形式，即3次方不是一一对应，并且n是三次剩余，即满足Euler判别法：
-$$n^{k}\equiv 1\mod p$$
-那么对x进行待定系数。考虑全体x的整系数二次多项式：
-$$y=ax^2+bx+c$$
-因此记录y的时候只需记录整数三元组abc即可。利用最开始的方程关系：
-$$x^3\equiv n\mod p$$
-可以对指数模3，即计算多项式的乘法之后，仍旧还是二次三项式，即y的幂还是整数三元组abc。对于这样的多项式y也满足Fermat-Euler定理：
-$$y^{p-1}\equiv 1\mod p$$
-即p-1次方（3k次方）之后，整数三元组abc变为001。那么在这个多项式空间里就有三次单位根：
-$$y^{k}\equiv w\mod p$$
-那么w也是二次三项式，w的三次方是1，即整数三元组001。
-如果随机生成一个y，即随机生成一组初始三元组abc，使得w恰好满足w的abc三元组中，a和c都是0，即：
-$$w=bx$$
-那么根据w的三次方是1，我们计算出的b恰好就是x的数论倒数。
-进一步分析表明，这种随机生成y的方法里，最终计算出的w中a和c都是0的概率只有九分之一，即平均随机九次才能算出一个合格的w。
-当然一个优势是，这种暴力算法是可推广的，即可以轻松推广到任意次数的剩余中，只是时间复杂度会非常高。它退化成二次的形式的时候，其实和上文的Cipolla算法比较接近，相当于Cipolla的弱化版。
-=====三四次剩余的初步介绍=====
-我们看到优秀的Cipolla算法的关键是，在Euler判别法中，二次非剩余的二分之p-1次方恰好回到了-1，即-1是二次单位根。因此，在一开始考察的方程中，做p次方之后x1和x2恰好互换了位置。这是Cipolla算法的关键。
-然而，三四次剩余不是这样。问题在于在缩系乘法群当中，三四次单位根并不固定，并非像二次单位根一样一直是-1。
-解决这个问题的办法还是扩域。三四次单位根不固定的原因，是因为固定的三次单位根和四次单位根本来就不在考察范围里。因此需要将**分圆域**添加进来，才能在新范围中实现固定。
-之前提到的高斯整环就是四次分圆整环，艾森斯坦整环就是三次（也是六次）分圆整环。
-于是在这种情形下引入三次剩余符号和四次剩余符号（Legendre符号），要求**符号下方的数必须是新数域中的非分歧本原素数**（可推广至Jacobi符号，下方为**不含分歧数的本原数**），则总有：
-$${\left(\frac{\xi}{\pi}\right)}_3=0\ or\ 1\ or\ \frac{-1+\sqrt{3}}{2} or\ \frac{-1-\sqrt{3}}{2}$$
-$${\left(\frac{\xi}{\pi}\right)}_4=0\ or\ 1\ or\ -1\ or\ i\ or\ -i$$
-总代表整除（不互素），1代表是三次剩余或四次剩余，-1代表是二次剩余但不是四次剩余，其余均为非剩余。
-例如，对于3k+2型素数p，扩充根号三i之后仍为新数域中的素数，其中每个原来的整数都是三次剩余，在新数域中由原来的一一对应变为三一对应，因为新数域中完系扩充到了p的平方个。于是三次剩余性质不变，每一个原来的整数代入符号之后右端为1。原来的三次单位根只有1一个，现在多了复平面上的两个。
-对于3k+1型素数p，扩充根号三i之后不为素数，分裂为两个共轭的新素数，原来的三次剩余性质由新素数继承了。这时，原来看似混乱的三次单位根在模新素数的情况下，同余于复平面上的单位根。
-综上所述，在扩域后三次或四次剩余符号里面（下方未扩展至Jacobi），欧拉判别法仍然是成立的。
-$${\left(\frac{\xi}{\pi}\right)}_3\equiv a^{\frac{N(\pi)-1}{3}}\mod\pi$$
-$${\left(\frac{\xi}{\pi}\right)}_4\equiv a^{\frac{N(\pi)-1}{4}}\mod\pi$$
-=====二次Kronecker符号=====
 剩余符号一般分为Legendre符号、Jacobi符号和Kronecker符号，三者为包含关系，前一个是后一个的特例，后一个是前一个的推广。勒让德符号要求下方为**非分歧本原素数**（二次为正奇素数），雅可比符号要求下方为**非分歧本原数**（二次为正奇数），而Kronecker符号什么限制都没有。当然，绝大多数剩余都能轻易地推广到Jacobi符号，这是为了计算互反律方便，但是推广到Kronecker符号就很困难。
@@ 行 303: / 行 87: @@
 另一个性质是**互反律**，在下文的二次互反律再介绍。
-=====Gauss引理=====
+====Gauss引理====
 将奇素数p的缩系分为前后两个区间：前半个区间是1到二分之p-1，后半个区间是二分之p+1到p-1。
@@ 行 374: / 行 158: @@
 $$u^{\frac{p+1}{2}} |h(1+u)+u^{\frac{p-1}{2}}  \frac{1}{\frac{p-1}{2}!}$$
-=====Gauss和=====
+====Gauss和====
 要想讲解二次互反律，首先必须讲高斯和，从其根源处讲起。
@@ 行 488: / 行 273: @@
 两多项式均不超p-1次，最终只能相等。
+====二次互反律====
-=====二次互反律=====
 根据上面多项式g与高斯和的定义，可以证明二次互反律。对于奇素数p、q，模q意义下有：
@@ 行 514: / 行 297: @@
 表中0的位置标蓝了，而对角线对称后不相同的元素标成了黄色，为了更加直观地看到二次互反律。
-=====三次互反律与四次互反律简介=====
+====二次Hilbert符号====
-有了前面的铺垫，这部分就简单了。
-三四次互反律的**主体部分**特别简单：**非分歧本原数可以直接颠倒。**
-$${\left(\frac{\xi_1}{\xi_2}\right)}_k={\left(\frac{\xi_2}{\xi_1}\right)}_k$$
-这里的应用范畴是Jacobi符号。如上所见，二次互反律中的Kronecker符号的相应形式都不太一样，因此个人感觉不太可能直接推广到相应的Kronecker符号形式。
-与二次互反律一样，除了主体部分，一定还有一个**辅助定理**，用于处理上方是分歧数的情形。对于二次互反律，就是上方是2的情形作为辅助定理。而三四次互反律的这部分比较复杂，就先不再给出了。
-（缺了辅助定理这部分，计算可能会变得较为繁杂呢）
-到更难的类域论的部分，阿廷（Artin）为每一个数域上都推广出了相应的互反律，称为阿廷互反律。这就实在太难了，估计即使是数学系也得要博士才会研究，本科和研究生肯定不会去研究这些（所以我当然不会喽）。
-=====p进数中的平方元=====
 事实上纯数学的美感到这里顶多展示了一半，甚至可以说才刚刚开始。接下来的结论更加适合科普。如果愿意写个算法研究一下，其实也无所谓。事实上学算法的话，看到上文的二次互反律就足够了，只是互反律深刻的本质还没有被揭示出来，甚至到今天仍旧是纯数学的最艰深的课题之一。毕竟在Hilbert的23问中，第6个问题就是**在任意数域中证明最一般的互反律**，即Artin大佬百年前解决的问题。可知，互反律是数论的核心之一。
 要想解释上文二次Kronecker符号中，为什么互反律不仅与本原数有关，还与数的正负有关，参考后文三四次互反律只与本原数有关，这点确实令人匪夷所思。那么要想解释这个问题，就不得不提到p进数，以及后文的Hilbert符号，还有前文中二次曲线上的整点问题一起讨论，才能解释清楚。
-首先要在p进数中引入类似于二次剩余的概念。根据p进数的定义，即取p的幂次模后能区分的程度作为p进数右侧的数位，模p的幂中的平方元放在p进数中就变为了p进数中相应的平方元。
-首先来对比一下整数、有理数和实数中的平方元：
-整数的平方元是离散的，分别为0，1，4，9，……。
-有理数的平方元，就是整数平方元之比。
-实数中的平方元是全体非负数，并且全体负数都是非平方元。
-注意，在这里就出现了负数和非负数的区分。这一点其实很重要。
-首先，p进数的书写方法与p进制数相同，但是右边有限，左边无穷，这点已经提到了。
-于是，每一个p进数都可以**唯一**表示为p的n次方乘u的形式。其中u小数点后没有内容，并且小数点前一位非0。
-（相当于将p的因子全部提出来）
-于是，p进数为平方元的充要条件为：n是偶数，并且u小数点前一位是模p的二次剩余。
-这体现了p进数中的平方元具有某种聚集的特征，除了含p偶数条件以外，只与一位有效数字有关，与再左边全没关系。
-=====二次Hilbert符号=====
 二次Hilbert符号中的变元是上方的a和b，范围不仅限于整数，而是要求a和b非零,并且使得a和b有意义的数。
@@ 行 619: / 行 361: @@
 $$\left(\frac{a,bc}{v}\right)=\left(\frac{a,b}{v}\right)\left(\frac{a,c}{v}\right)$$
-根据方程含义，有以下初值：
+**化归二次剩余情况**：
-$$\left(\frac{a,-a}{v}\right)=1$$
+这里a为p进数中，小数点后没有内容而前一位非0的数。当其中含一个p的时候，无论p是奇素数还是2：
-$$\left(\frac{a,1-a}{v}\right)=1$$
-注意初值要求自变量非0，即前一个式子a不能是0，后一个式子a不能是0或1。
-当其中含一个p的时候，无论p是奇素数还是2，有一个与二次剩余相关的性质：
 $$\left(\frac{a,p}{p}\right)=\left(\frac{a}{p}\right)$$
 右边就是一般的二次剩余符号，例如二次Kronecker符号。
+**双可逆元情况**：
 对于奇素数p，如果a和b均为p进数中，小数点后没有内容而前一位非0的数，就有：
@@ 行 645: / 行 383: @@
 当且仅当a和b都模4余3的时候，值为-1，否则值为1。
-那么就可以借助完全积性来计算二次Hilbert符号了。
+到这里，与利用完全积性计算二次Hilbert符号的目标，还差最后一步。
-=====互反律与p进数的关系=====
+**相等数情况**：
-终于到了最后的部分，也是本篇最精华的部分。
+$$\left(\frac{a,a}{v}\right)=\left(\frac{a,-1}{v}\right)$$
+当a就是下方的素数p的时候，代入公式得：
+$$\left(\frac{p,p}{p}\right)=\left(\frac{p,-1}{p}\right)=\left(\frac{-1}{p}\right)$$
+至此就可以借助完全积性来计算二次Hilbert符号了。
+根据方程含义，还可以推出以下初值：
+$$\left(\frac{a,1-a}{v}\right)=1$$
+注意定义要求自变量非0，即a不能是0或1。
+====二次互反律与p进数的关系====
+这里是本篇最精华的部分。
 由于上一部分二次Hilbert符号里面直接给出了结论，略去了证明，于是这部分的难度被大大降低了，似乎随便写写就能写明白了。
+对于方程：
+$$ax^2+by^2=1$$
+我们利用下方为无穷的二次Hilbert符号就可以判定它是否有实数解，当然这一步多此一举，直接正负讨论即可。
+那么，上面有没有有理解呢？结论是这样的：
+**对于给定的非0有理数a和b，二次曲线上有有理点，等价于首先有实数点，并且其次对于所有的p进数域中都有点。**
+那么有理解的判定方法是怎样的？有下面的Hilbert乘积公式。不过先说一个显然的结论：
+**对于给定的非0有理数a和b，至多只有有限个p使得a和b的二次Hilbert符号值为-1。**
+这是因为定义中a和b非0，至多只有有限个p整除a或b，于是对于剩余的p均既不整除a、也不整除b，符号的值就为1了。
+**Hilbert乘积公式**：
+$$\prod_v \left(\frac{a,b}{v}\right)=1$$
+乘积的范围是全体v，即v取无穷以及全体素数。
+考虑完全积性的性质以及a和b的素因子分解，只需要对以下三种情形证明即可。
+当a和b为相异奇素数时：
+$$\left(\frac{a,b}{v}\right)=\begin{cases}\left(\frac{b}{a}\right)\quad &v=a\\\left(\frac{a}{b}\right)\quad &v=b\\{(-1)}^{\frac{a-1}{2}\frac{b-1}{2}}\quad &v=2\\1\quad &others\end{cases}$$
+这种情况Hilbert乘积公式恰好就是二次互反律。
+当a为奇素数，b为-1或2时：
+$$\left(\frac{a,-1}{v}\right)=\begin{cases}\left(\frac{-1}{a}\right)\quad &v=a\\{(-1)}^{\frac{a-1}{2}}\quad &v=2\\1\quad &others\end{cases}$$
+$$\left(\frac{a,2}{v}\right)=\begin{cases}\left(\frac{2}{a}\right)\quad &v=a\\{(-1)}^{\frac{a^2-1}{8}}\quad &v=2\\1\quad &others\end{cases}$$
+这种情况Hilbert乘积公式恰好就是二次互反律的补充定律。
+当a为-1，b均为-1或2时，这种情形最简单了。
+$$\left(\frac{-1,-1}{v}\right)=\begin{cases}-1\quad &v=2\ or\ \infty\\1\quad &others\end{cases}$$
+$$\left(\frac{-1,2}{v}\right)=1$$
+这个乘积公式统一了二次互反律。它的意义就是：**对于给定的非0有理数a和b，不存在有理点的p进数域加实数域的数量是偶数。**
+因此验证有理点，只需验证实数域，以及除一个素数以外所有的p进数域即可。
+====Cipolla平方根算法====
+由于三次方程的解法较为复杂，开三次方根的算法并不容易。但是在这里有一种简洁有效的开平方根的算法，它需要将研究对象进行域扩张，扩张到$Q(\sqrt{a^2-n})$上。
+对于一个二次剩余n，我们想对它开平方根，即求解：
+$$t^2\equiv n\mod p$$
+考虑方程：
+$$x^2-2ax+n=0$$
+这个方程的两根之积是n。因此根据Fermat-Eular定理，两根之积的p次方应该也是n。
+$${x_1}^p{x_2}^p\equiv n\mod p$$
+注意这里的两个根都未必是整数。下面分别考虑两个根单独的p次方是什么，即考虑：
+$${x_1}^p\mod p$$
+如果这个根本身是整数，那么根据Fermat-Eular定理，它的值应当回到这个根本身。
+不是整数的情形会怎样？在扩域$Q(\sqrt{a^2-n})$当中，没有引入p分之1作为因子。因此，下面的常见二项式展开结论应当成立：
+$${(a+b)}^p\equiv a^p+b^p\mod p$$
+这里的取模是对两个分量1和根号的系数取模。不妨取比较大的根x1（较小的根同理），于是：
+$${x_1}^p={(a+\sqrt{a^2-n})}^p\equiv a^p+{(\sqrt{a^2-n})}^p\equiv a+{(a^2-n)}^{\frac{p}{2}}\mod p$$
+由于a是整数，根据Fermat-Eular定理，a的p次方还是a。因此关键在于后面根号部分的p次方是多少，这部分未必满足Fermat-Eular定理。事实上，这一部分不满足Fermat-Eular定理。
+根据Euler判别法，根号下的部分的半群阶次方很好计算。在是二次剩余的时候为1，否则二次非剩余的时候为-1。即：
+$${(a^2-n)}^{\frac{p-1}{2}}\equiv 1\ or\ -1\mod p$$
+两边再乘一个这个数的根号就有：
+$${(a^2-n)}^{\frac{p}{2}}\equiv \sqrt{a^2-n}\ or\ -\sqrt{a^2-n}\mod p$$
+上文中，根是整数的情形，即根号可以被开出来，那么这里就是二次剩余，右面的根号系数为1，代回原式可以得到p次方后不变的结果，与之前结论吻合。
+但是，根不是整数的情形，对应根号下为二次非剩余，这里的同余式右端根号为负，即：
+$${(\sqrt{a^2-n})}^p\equiv -\sqrt{a^2-n}\mod p$$
+因此，**在p次方作用下，原方程的两个根交换了位置**：
+$${x_1}^p\equiv a-\sqrt{a^2-n}=x_2\mod p$$
+换位的前提，是根号下的数为二次非剩余，即这个根号开不出来的情形。
+那么这个结论有什么用呢？我们在两边再同乘一个x1：
+$${x_1}^{p+1}\equiv x_1x_2=n\mod p$$
+发现p+1恰好是偶数，而右边恰好是要开方的整数n。因此最开始的开方值t就应该是：
+$$t_1\equiv{x_1}^{\frac{p+1}{2}}\mod p$$
+这就是Cipolla平方根算法。第一步随机出一个a，使得a的平方减n是二次非剩余。然后只需计算x1的二分之p加1次方即可。由于二次剩余和二次非剩余恰好各占总体的一半，一般认为随机一次的a符合条件的概率是50%。
+对于四次方根的求解，可以用两次Cipolla算法来解决，也不算困难。然而对于三次方根就麻烦得多。
+=====高次剩余与互反律=====
+====一一映射情形的求根====
+这里指当素数p不是tk+1情形的时候，t次方运算在p的缩系中是一一映射。那么这种情形的求根相当容易，甚至不需要用到上文的扩域。
+这里仅举个简单的例子作为参考。对于p是3k+2情形的时候，3次方运算是一一对应。我们已知下面的n，要求解x：
+$$x^3\equiv n\mod p$$
+首先根据Fermat-Eular定理，这个同余式一定是成立的：
+$$x^{3k+1}\equiv 1\mod p$$
+那么对n作k次方，就有：
+$$n^k\equiv x^{3k}\equiv x^{-1}\mod p$$
+那么再来一次数论倒数就完事了。即完整的式子是：
+$$n^{3k^2}=n^{k(p-2)}\equiv x\mod p$$
+其实上面的操作，就是缩系循环群里面，取对数之后，对3进行的数论倒数操作，即寻找一个逆映射。我们看到，3乘以3k方是9k方，再减去1之后，恰好是p-1即3k+1的倍数。因此，在缩系循环群的观点下，这样的逆映射就是跑了若干个整循环之后，恰好多跑出了一个幂次。这样类似于不定方程的思想就求解出了逆映射。
+同时也看到，当p是tk+1情形的时候，这个映射不是一一映射，那么就不能采用这种办法了。即p是3k+1情形的时候，无法用这种办法开三次方。
+====Peralta算法开立方====
+Cipolla算法开平方是一种特别优秀的算法，时间复杂度很低。而这里写出的Peralta算法仍旧属于一种暴力算法，比用原根与对数计算（至少根号量级）要优秀，相对Cipolla算法（对数量级）时间复杂度比较高。
+它的思路是这样的。要求解：
+$$x^3\equiv n\mod p$$
+其中p是3k+1形式，即3次方不是一一对应，并且n是三次剩余，即满足Euler判别法：
+$$n^{k}\equiv 1\mod p$$
+那么对x进行待定系数。考虑全体x的整系数二次多项式：
+$$y=ax^2+bx+c$$
+因此记录y的时候只需记录整数三元组abc即可。利用最开始的方程关系：
+$$x^3\equiv n\mod p$$
+可以对指数模3，即计算多项式的乘法之后，仍旧还是二次三项式，即y的幂还是整数三元组abc。对于这样的多项式y也满足Fermat-Euler定理：
+$$y^{p-1}\equiv 1\mod p$$
+即p-1次方（3k次方）之后，整数三元组abc变为001。那么在这个多项式空间里就有三次单位根：
+$$y^{k}\equiv w\mod p$$
+那么w也是二次三项式，w的三次方是1，即整数三元组001。
+如果随机生成一个y，即随机生成一组初始三元组abc，使得w恰好满足w的abc三元组中，a和c都是0，即：
+$$w=bx$$
+那么根据w的三次方是1，我们计算出的b恰好就是x的数论倒数。
+进一步分析表明，这种随机生成y的方法里，最终计算出的w中a和c都是0的概率只有九分之一，即平均随机九次才能算出一个合格的w。
+当然一个优势是，这种暴力算法是可推广的，即可以轻松推广到任意次数的剩余中，只是时间复杂度会非常高。它退化成二次的形式的时候，其实和上文的Cipolla算法比较接近，相当于Cipolla的弱化版。
+====三四次剩余的初步介绍====
+我们看到优秀的Cipolla算法的关键是，在Euler判别法中，二次非剩余的二分之p-1次方恰好回到了-1，即-1是二次单位根。因此，在一开始考察的方程中，做p次方之后x1和x2恰好互换了位置。这是Cipolla算法的关键。
+然而，三四次剩余不是这样。问题在于在缩系乘法群当中，三四次单位根并不固定，并非像二次单位根一样一直是-1。
+解决这个问题的办法还是扩域。三四次单位根不固定的原因，是因为固定的三次单位根和四次单位根本来就不在考察范围里。因此需要将**分圆域**添加进来，才能在新范围中实现固定。
+之前提到的高斯整环就是四次分圆整环，艾森斯坦整环就是三次（也是六次）分圆整环。
+于是在这种情形下引入三次剩余符号和四次剩余符号（Legendre符号），要求**符号下方的数必须是新数域中的非分歧本原素数**（可推广至Jacobi符号，下方为**不含分歧数的本原数**），则总有：
+$${\left(\frac{\xi}{\pi}\right)}_3=0\ or\ 1\ or\ \frac{-1+\sqrt{3}}{2} or\ \frac{-1-\sqrt{3}}{2}$$
+$${\left(\frac{\xi}{\pi}\right)}_4=0\ or\ 1\ or\ -1\ or\ i\ or\ -i$$
+总代表整除（不互素），1代表是三次剩余或四次剩余，-1代表是二次剩余但不是四次剩余，其余均为非剩余。
+例如，对于3k+2型素数p，扩充根号三i之后仍为新数域中的素数，其中每个原来的整数都是三次剩余，在新数域中由原来的一一对应变为三一对应，因为新数域中完系扩充到了p的平方个。于是三次剩余性质不变，每一个原来的整数代入符号之后右端为1。原来的三次单位根只有1一个，现在多了复平面上的两个。
+对于3k+1型素数p，扩充根号三i之后不为素数，分裂为两个共轭的新素数，原来的三次剩余性质由新素数继承了。这时，原来看似混乱的三次单位根在模新素数的情况下，同余于复平面上的单位根。
+综上所述，在扩域后三次或四次剩余符号里面（下方未扩展至Jacobi），欧拉判别法仍然是成立的。
+$${\left(\frac{\xi}{\pi}\right)}_3\equiv a^{\frac{N(\pi)-1}{3}}\mod\pi$$
+$${\left(\frac{\xi}{\pi}\right)}_4\equiv a^{\frac{N(\pi)-1}{4}}\mod\pi$$
+====三四次互反律简介====
+有了前面的铺垫，这部分就简单了。
+三四次互反律的**主体部分**特别简单：**非分歧本原数可以直接颠倒。**
+$${\left(\frac{\xi_1}{\xi_2}\right)}_k={\left(\frac{\xi_2}{\xi_1}\right)}_k$$
+这里的应用范畴是Jacobi符号。如上所见，二次互反律中的Kronecker符号的相应形式都不太一样，因此个人感觉不太可能直接推广到相应的Kronecker符号形式。
+与二次互反律一样，除了主体部分，一定还有一个**辅助定理**，用于处理上方是分歧数的情形。对于二次互反律，就是上方是2的情形作为辅助定理。而三四次互反律的这部分比较复杂，就先不再给出了。
+（缺了辅助定理这部分，计算可能会变得较为繁杂呢）
+到更难的类域论的部分，阿廷（Artin）为每一个数域上都推广出了相应的互反律，称为阿廷互反律。这就实在太难了，估计即使是数学系也得要博士才会研究，本科和研究生肯定不会去研究这些（所以我当然不会喽）。
+至此，有关互反律的全部内容介绍完毕。完结撒花！

CVBB ACM Team

用户工具

站点工具

页面工具