CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:namespace:初等数论三大定理和缩系乘法群 [2020/06/17 17:05]
great_designer [推广]
+++ 2020-2021:teams:namespace:初等数论三大定理和缩系乘法群 [2020/06/23 17:32] (当前版本)
great_designer
@@ 行 97: / 行 97: @@
 模2的幂的那个维度与它不相关。每有一个模4余1的解，必然也有一个模4余-1的解与它配对。因此是偶数个。
-同理，模2的幂的部分也可以采用配对法。
+同理，模2的幂的部分也可以采用配对法。含有多个奇素数的情形也同理。
 那么最终结果为：
@@ 行 106: / 行 106: @@
 &1&otherwise\end{cases}
 $$
+注：推理中容易犯的错误是，尽管一个缩系的乘积模某个分量的结果可能是-1，但是在最终得数中含有的分量缩系可能不止一个。
@@ 行 230: / 行 232: @@
 循环结束后，我们得到一个二进制数：在每个得到的h-2处为1，其它处为0。因为我们使用了乘法而不是除法，最后用$2^{t-2}$减去得到的二进制数，就得到了所求的对数。
+=====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存储其中一边的结果，枚举另一边时查找即可。
+因为时间复杂度是根号量级，在大素数情形很高，而反过来的快速幂却是对数量级，是复杂度低的算法，事实上也说明求对数是个世界级难题，至今还没有得到解决。

CVBB ACM Team

用户工具

站点工具

页面工具