2020-2021:teams:namespace:剩余和互反律
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:剩余和互反律 [2020/06/23 17:40] great_designer |
2020-2021:teams:namespace:剩余和互反律 [2020/06/23 17:42] (当前版本) great_designer |
||
|---|---|---|---|
| 行 15: | 行 15: | ||
| <del>写完这四篇基本上可以出版一本初等数论教科书了。</del> | <del>写完这四篇基本上可以出版一本初等数论教科书了。</del> | ||
| - | =====二次Kronecker符号===== | + | =====二次剩余与互反律===== |
| + | |||
| + | ====二次Kronecker符号==== | ||
| 剩余符号一般分为Legendre符号、Jacobi符号和Kronecker符号，三者为包含关系，前一个是后一个的特例，后一个是前一个的推广。勒让德符号要求下方为**非分歧本原素数**（二次为正奇素数），雅可比符号要求下方为**非分歧本原数**（二次为正奇数），而Kronecker符号什么限制都没有。当然，绝大多数剩余都能轻易地推广到Jacobi符号，这是为了计算互反律方便，但是推广到Kronecker符号就很困难。 | 剩余符号一般分为Legendre符号、Jacobi符号和Kronecker符号，三者为包含关系，前一个是后一个的特例，后一个是前一个的推广。勒让德符号要求下方为**非分歧本原素数**（二次为正奇素数），雅可比符号要求下方为**非分歧本原数**（二次为正奇数），而Kronecker符号什么限制都没有。当然，绝大多数剩余都能轻易地推广到Jacobi符号，这是为了计算互反律方便，但是推广到Kronecker符号就很困难。 | ||
| 行 85: | 行 87: | ||
| 另一个性质是**互反律**，在下文的二次互反律再介绍。 | 另一个性质是**互反律**，在下文的二次互反律再介绍。 | ||
| - | =====Gauss引理===== | + | ====Gauss引理==== |
| 将奇素数p的缩系分为前后两个区间：前半个区间是1到二分之p-1，后半个区间是二分之p+1到p-1。 | 将奇素数p的缩系分为前后两个区间：前半个区间是1到二分之p-1，后半个区间是二分之p+1到p-1。 | ||
| 行 157: | 行 159: | ||
| $$u^{\frac{p+1}{2}} |h(1+u)+u^{\frac{p-1}{2}} \frac{1}{\frac{p-1}{2}!}$$ | $$u^{\frac{p+1}{2}} |h(1+u)+u^{\frac{p-1}{2}} \frac{1}{\frac{p-1}{2}!}$$ | ||
| - | =====Gauss和===== | + | ====Gauss和==== |
| 要想讲解二次互反律，首先必须讲高斯和，从其根源处讲起。 | 要想讲解二次互反律，首先必须讲高斯和，从其根源处讲起。 | ||
| 行 271: | 行 273: | ||
| 两多项式均不超p-1次，最终只能相等。 | 两多项式均不超p-1次，最终只能相等。 | ||
| - | =====二次互反律===== | + | ====二次互反律==== |
| 根据上面多项式g与高斯和的定义，可以证明二次互反律。对于奇素数p、q，模q意义下有： | 根据上面多项式g与高斯和的定义，可以证明二次互反律。对于奇素数p、q，模q意义下有： | ||
| 行 295: | 行 297: | ||
| 表中0的位置标蓝了，而对角线对称后不相同的元素标成了黄色，为了更加直观地看到二次互反律。 | 表中0的位置标蓝了，而对角线对称后不相同的元素标成了黄色，为了更加直观地看到二次互反律。 | ||
| - | =====二次Hilbert符号===== | + | ====二次Hilbert符号==== |
| 事实上纯数学的美感到这里顶多展示了一半，甚至可以说才刚刚开始。接下来的结论更加适合科普。如果愿意写个算法研究一下，其实也无所谓。事实上学算法的话，看到上文的二次互反律就足够了，只是互反律深刻的本质还没有被揭示出来，甚至到今天仍旧是纯数学的最艰深的课题之一。毕竟在Hilbert的23问中，第6个问题就是**在任意数域中证明最一般的互反律**，即Artin大佬百年前解决的问题。可知，互反律是数论的核心之一。 | 事实上纯数学的美感到这里顶多展示了一半，甚至可以说才刚刚开始。接下来的结论更加适合科普。如果愿意写个算法研究一下，其实也无所谓。事实上学算法的话，看到上文的二次互反律就足够了，只是互反律深刻的本质还没有被揭示出来，甚至到今天仍旧是纯数学的最艰深的课题之一。毕竟在Hilbert的23问中，第6个问题就是**在任意数域中证明最一般的互反律**，即Artin大佬百年前解决的问题。可知，互反律是数论的核心之一。 | ||
| 行 399: | 行 401: | ||
| 注意定义要求自变量非0，即a不能是0或1。 | 注意定义要求自变量非0，即a不能是0或1。 | ||
| - | =====互反律与p进数的关系===== | + | ====二次互反律与p进数的关系==== |
| - | 终于到了最后的部分，也是本篇最精华的部分。 | + | 这里是本篇最精华的部分。 |
| 由于上一部分二次Hilbert符号里面直接给出了结论，略去了证明，于是这部分的难度被大大降低了，似乎随便写写就能写明白了。 | 由于上一部分二次Hilbert符号里面直接给出了结论，略去了证明，于是这部分的难度被大大降低了，似乎随便写写就能写明白了。 | ||
| 行 453: | 行 455: | ||
| 因此验证有理点，只需验证实数域，以及除一个素数以外所有的p进数域即可。 | 因此验证有理点，只需验证实数域，以及除一个素数以外所有的p进数域即可。 | ||
| - | =====Cipolla平方根算法===== | + | ====Cipolla平方根算法==== |
| 由于三次方程的解法较为复杂，开三次方根的算法并不容易。但是在这里有一种简洁有效的开平方根的算法，它需要将研究对象进行域扩张，扩张到$Q(\sqrt{a^2-n})$上。 | 由于三次方程的解法较为复杂，开三次方根的算法并不容易。但是在这里有一种简洁有效的开平方根的算法，它需要将研究对象进行域扩张，扩张到$Q(\sqrt{a^2-n})$上。 | ||
| 行 517: | 行 519: | ||
| 对于四次方根的求解，可以用两次Cipolla算法来解决，也不算困难。然而对于三次方根就麻烦得多。 | 对于四次方根的求解，可以用两次Cipolla算法来解决，也不算困难。然而对于三次方根就麻烦得多。 | ||
| - | =====一一映射情形的求根===== | + | =====高次剩余与互反律===== |
| + | |||
| + | ====一一映射情形的求根==== | ||
| 这里指当素数p不是tk+1情形的时候，t次方运算在p的缩系中是一一映射。那么这种情形的求根相当容易，甚至不需要用到上文的扩域。 | 这里指当素数p不是tk+1情形的时候，t次方运算在p的缩系中是一一映射。那么这种情形的求根相当容易，甚至不需要用到上文的扩域。 | ||
| 行 541: | 行 545: | ||
| 同时也看到，当p是tk+1情形的时候，这个映射不是一一映射，那么就不能采用这种办法了。即p是3k+1情形的时候，无法用这种办法开三次方。 | 同时也看到，当p是tk+1情形的时候，这个映射不是一一映射，那么就不能采用这种办法了。即p是3k+1情形的时候，无法用这种办法开三次方。 | ||
| - | =====Peralta算法开立方===== | + | ====Peralta算法开立方==== |
| Cipolla算法开平方是一种特别优秀的算法，时间复杂度很低。而这里写出的Peralta算法仍旧属于一种暴力算法，比用原根与对数计算（至少根号量级）要优秀，相对Cipolla算法（对数量级）时间复杂度比较高。 | Cipolla算法开平方是一种特别优秀的算法，时间复杂度很低。而这里写出的Peralta算法仍旧属于一种暴力算法，比用原根与对数计算（至少根号量级）要优秀，相对Cipolla算法（对数量级）时间复杂度比较高。 | ||
| 行 581: | 行 585: | ||
| 当然一个优势是，这种暴力算法是可推广的，即可以轻松推广到任意次数的剩余中，只是时间复杂度会非常高。它退化成二次的形式的时候，其实和上文的Cipolla算法比较接近，相当于Cipolla的弱化版。 | 当然一个优势是，这种暴力算法是可推广的，即可以轻松推广到任意次数的剩余中，只是时间复杂度会非常高。它退化成二次的形式的时候，其实和上文的Cipolla算法比较接近，相当于Cipolla的弱化版。 | ||
| - | =====三四次剩余的初步介绍===== | + | ====三四次剩余的初步介绍==== |
| 我们看到优秀的Cipolla算法的关键是，在Euler判别法中，二次非剩余的二分之p-1次方恰好回到了-1，即-1是二次单位根。因此，在一开始考察的方程中，做p次方之后x1和x2恰好互换了位置。这是Cipolla算法的关键。 | 我们看到优秀的Cipolla算法的关键是，在Euler判别法中，二次非剩余的二分之p-1次方恰好回到了-1，即-1是二次单位根。因此，在一开始考察的方程中，做p次方之后x1和x2恰好互换了位置。这是Cipolla算法的关键。 | ||
| 行 609: | 行 613: | ||
| $${\left(\frac{\xi}{\pi}\right)}_4\equiv a^{\frac{N(\pi)-1}{4}}\mod\pi$$ | $${\left(\frac{\xi}{\pi}\right)}_4\equiv a^{\frac{N(\pi)-1}{4}}\mod\pi$$ | ||
| - | =====三次互反律与四次互反律简介===== | + | ====三四次互反律简介==== |
| 有了前面的铺垫，这部分就简单了。 | 有了前面的铺垫，这部分就简单了。 | ||
2020-2021/teams/namespace/剩余和互反律.1592905216.txt.gz · 最后更改: 2020/06/23 17:40 由 great_designer
