质因数分解

WeLikeStudying · 2021-08-20 23:52:03 · 题解

素性测试

• 测试一个数是否是质数。
• 应该都学过 O(\sqrt n) 的试除法，基于 \forall ab=c(a,b,c\in \mathbf{Z^+}),\min(a,b)\leq\sqrt c
• 米勒·拉宾算法，O(\log_2n) 的随机算法。（没错这就是正确率接近 100% 的随机算法）
• 印度小哥有个非随机算法唤作 AKS，不过实用性稍低不讲，米勒·拉宾已经足够优秀同时足够简单。
• 米勒·拉宾算法基于费马小定理，即： \forall p\nmid a,\quad a^{p-1}\equiv1\pmod p
• 于是便产生了一种朴素的想法：对于待测试的数 n ，随机一个 0<a<n 计算 a^{n-1}\bmod n 若结果不为 1 即可排除 n 是质数。
• 但这显然是必要不充分条件，事实上，存在一些合数 n，满足： \forall a\bot n,\quad a^{n-1}\equiv1\pmod n
• 这类数称为 Carmichael 数，如 561=3×11×17 ，这类做法很难试出来，也许你见到的 Carmichael 数因子都很小，但是在题目的数据范围，我可以构造出 n=999211956328352449=550177\times 1100353\times 1650529，没错，他也是 Carmichael 数，此时，你又该如何应对！
• 哈哈哈，是不是没有办法了。
• 所以还需要平方差公式奇素数判定，除了 2 以外的质数，都是奇数！而奇数减一，就是偶数啊！两句大废话。
• 换句话说，若 a^{n-1}\equiv1\pmod n 则 (a^{\frac{n-1} 2}+1)(a^{\frac{n-1} 2}-1)\equiv0\pmod n，也就是 a^{\frac{n-1} 2}\equiv-1\pmod n，a^{\frac{n-1} 2}\equiv1\pmod n ，如果 \frac {n-1} 2 是偶数，还可以验证 \frac {n-1} 4 。
• 也就是说我们实际上用来判定的定理是：令 n-1=2^x\cdot y （y 是奇数），若 n\in\mathbf{P} 则 ，对于 a^y\equiv1\pmod n 或 \exists k\in[0,x],\quad a^{2^k\cdot y}\equiv-1\pmod n（其实那个区间是左闭右开的，我只是讨厌下划线，而且加上也不影响）
• 用原根我们不会涉及的原理可以证明至少存在一个 a\bot n 把 n 是合数的情况判掉。
• 用仍然不会涉及的知识可以证明对于奇合数 n 非证据的数目至多是 \dfrac{n-1}4 。
• 根据维基百科的说法，用不超过 37 的质数即可判定 2^{64} 或 18446744073709551616 范围的 n 。
• 代码实现。
• 如果不是枚举再快速幂是可以做到 O(\log_2n) 而非 O(\log_2^2n) 的。
• 注意 \text{OI wiki} 上给出的复杂度是考虑了巨大整数无法进行 O(1) 加减乘除的情况。

质因数分解

• 试除法仍然是 O(\sqrt n) 复杂度。
• Pollard-rho 可以做到理论 O(\sqrt[4]n\log_2n) 的复杂度，且在实际运行中跑得飞快。
• 主要思想是如何快速用随机数试出某个数的因子。
• 生日攻击悖论：对于一个理想的取值为 [1,n] 的随机数生成器，生成 \sqrt {\dfrac{\pi n}2} 个数期望得到两个数相同。
• 如果一个数 n 不是质数，那么它的最小质因子 p_x 满足 p\leq\sqrt n
• 如果我们随机生成 \sqrt[4]n 个数，那么期望存在两个数 a,b 使得 a\equiv b\pmod {p_x}。那么 |a-b| 就是 p 的倍数，可以通过求 \gcd(|a-b|,n) 得到一个因子。
• 但我们发现这样做复杂度又乘了回去，由于还有 gcd 的运算，复杂度直接变成 O(\sqrt n\log_2n) 。
• Pollard 构造了这样一组数列 \lbrace a_i\rbrace 满足 a_0=x 且 a_{i+1}=(a_i^2+c)\bmod n 。
• 这个数列有一个不得了的性质，任取数列中的两个数 a_i,a_j ，若 a_i-a_j\equiv0\pmod {p_x}，根据平方差公式: a_{i+1}-a_{j+1}=(a_i^2+c)-(a_j^2+c)=a_i^2-a_j^2 =(a_i+a_j)(a_i-a_j)\equiv0\pmod {p_x}
• 所以我们最好每次检查不同的距离。
• 这样的数据随机性当然有保证。
• 给张 Excel 自制散点图看一下。(a_0=3222,a_{i+1}=(a_i^2+24)\bmod9409，给出数列的前 1000 项)
• 大概一看，的确是分布地比较均匀，不过仔细一看你就会发现：数列之间好像有循环？
• 没错，显然这种伪随机数一旦出现相同的就会循环，而由于数据范围固定，很容易进入循环，形成混循环（即rho形结构）（我之前的数据经过特制，使得环长较长，实际环长还要更短）（如图 a_0=121,a_{i+1}=(a_i^2+11)\bmod 1014），如果进入循环还一直不停地检查就太傻了。
• 给出一种名叫 floyd （没错就是弗洛伊德）的判环方法。
• 第 k 次操作让一个数为 a_k ，另一个数为 a_{2k}（这很容易做到，迭代两次就好了），如果 a_k=a_{2k} 那么显然已经进入环中，直接跳出即可。
• 显然进入环中后 k 会慢慢增加到某个环长的倍数，终止可行。
• 而且这样每次只要检查 \gcd(|a_{2k}-a_k|,n) 就能够保证不同的距离，可谓一举两得。（另外 a_{2k}=a_k 时，即使整除）
• 不过，你有没有发现一些问题？
• 这其实并没有做到检查全部的数对，你可以暂时理解成，由于以上的性质，其实我们已经检查了大部分的情况。毕竟我们绝对不能讲超过高中的知识。
• 刚才那个问题令我们想到一个问题，就是如果环长为1，那么一下子慢的跳到 a_1，快的跳到 a_2，下一步直接结束然后无限循环，所以正确的做法是在第 k 步跳到 a_{k-1} 和 a_{2k-1}。
• 如果我们给的伪随机数随机性够高，且我们的检测方法事实上接近于两两求差，则期望在 O(\sqrt[4] p\log_2n) 的复杂度内给出 n 的最小质因子 p 。
• 很遗憾，这里不能给出复杂度的严格证明，但事实上时间复杂度并没有因为多次寻找因子而改变，仍然是 O(\sqrt[4]n\log_2n)，给出一个表格看一下这个算法在不同数字下的运算次数当然在我的程序下。

• 代码实现。
• 上例题！
• 【模板】Pollard-Rho算法
• 这道题靠之前那个模板会 TLE 一个点。
• 于是我们可以进行一个简单的优化，我们可以尝试把一段数乘起来 \bmod n 来减少常数。
• 但这样可能会导致 floyd 过晚退出，而且乘出 n (一点用也没有）的概率也会增加。
• 我们可以进行一个折中的方法：每隔约 \log(n) 次进行一次 gcd，然后就可以消掉 gcd 的复杂度，理论时间复杂度为 O(\sqrt[4]n)。
• AC 地太轻松了？
• 再次给出这个算法复杂度的表。

• 对比即可发现这个简单优化的优越性能。
• 不过 Pollard 算法确实不是很稳定。
• 代码实现。