CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:namespace:剩余和互反律 [2020/06/23 17:37]
great_designer
+++ 2020-2021:teams:namespace:剩余和互反律 [2020/06/23 17:42] (当前版本)
great_designer
@@ 行 15: / 行 15: @@
 <del>写完这四篇基本上可以出版一本初等数论教科书了。</del>
-=====Cipolla平方根算法=====
+=====二次剩余与互反律=====
-由于三次方程的解法较为复杂，开三次方根的算法并不容易。但是在这里有一种简洁有效的开平方根的算法，它需要将研究对象进行域扩张，扩张到$Q(\sqrt{a^2-n})$上。
+====二次Kronecker符号====
-对于一个二次剩余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符号就很困难。
@@ 行 241: / 行 87: @@
 另一个性质是**互反律**，在下文的二次互反律再介绍。
-=====Gauss引理=====
+====Gauss引理====
 将奇素数p的缩系分为前后两个区间：前半个区间是1到二分之p-1，后半个区间是二分之p+1到p-1。
@@ 行 312: / 行 158: @@
 $$u^{\frac{p+1}{2}} |h(1+u)+u^{\frac{p-1}{2}}  \frac{1}{\frac{p-1}{2}!}$$
-=====Gauss和=====
+====Gauss和====
 要想讲解二次互反律，首先必须讲高斯和，从其根源处讲起。
@@ 行 426: / 行 273: @@
 两多项式均不超p-1次，最终只能相等。
+====二次互反律====
-=====二次互反律=====
 根据上面多项式g与高斯和的定义，可以证明二次互反律。对于奇素数p、q，模q意义下有：
@@ 行 452: / 行 297: @@
 表中0的位置标蓝了，而对角线对称后不相同的元素标成了黄色，为了更加直观地看到二次互反律。
-=====三次互反律与四次互反律简介=====
+====二次Hilbert符号====
-有了前面的铺垫，这部分就简单了。
-三四次互反律的**主体部分**特别简单：**非分歧本原数可以直接颠倒。**
-$${\left(\frac{\xi_1}{\xi_2}\right)}_k={\left(\frac{\xi_2}{\xi_1}\right)}_k$$
-这里的应用范畴是Jacobi符号。如上所见，二次互反律中的Kronecker符号的相应形式都不太一样，因此个人感觉不太可能直接推广到相应的Kronecker符号形式。
-与二次互反律一样，除了主体部分，一定还有一个**辅助定理**，用于处理上方是分歧数的情形。对于二次互反律，就是上方是2的情形作为辅助定理。而三四次互反律的这部分比较复杂，就先不再给出了。
-（缺了辅助定理这部分，计算可能会变得较为繁杂呢）
-到更难的类域论的部分，阿廷（Artin）为每一个数域上都推广出了相应的互反律，称为阿廷互反律。这就实在太难了，估计即使是数学系也得要博士才会研究，本科和研究生肯定不会去研究这些（所以我当然不会喽）。
-=====二次Hilbert符号=====
 事实上纯数学的美感到这里顶多展示了一半，甚至可以说才刚刚开始。接下来的结论更加适合科普。如果愿意写个算法研究一下，其实也无所谓。事实上学算法的话，看到上文的二次互反律就足够了，只是互反律深刻的本质还没有被揭示出来，甚至到今天仍旧是纯数学的最艰深的课题之一。毕竟在Hilbert的23问中，第6个问题就是**在任意数域中证明最一般的互反律**，即Artin大佬百年前解决的问题。可知，互反律是数论的核心之一。
@@ 行 572: / 行 401: @@
 注意定义要求自变量非0，即a不能是0或1。
-=====互反律与p进数的关系=====
+====二次互反律与p进数的关系====
-终于到了最后的部分，也是本篇最精华的部分。
+这里是本篇最精华的部分。
 由于上一部分二次Hilbert符号里面直接给出了结论，略去了证明，于是这部分的难度被大大降低了，似乎随便写写就能写明白了。
@@ 行 625: / 行 454: @@
 因此验证有理点，只需验证实数域，以及除一个素数以外所有的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

用户工具

站点工具

页面工具