pollard-rho

前言 其实很早就看到过了，下定决心去学的，居然是因为翻到之前口胡的题目，然后发现之前做法假了，继续尝试做的时候发现需要这个算法，于是，题目就绿->黑了。 Step.1 引入 求一个数的所有因数，这个问题伴随了我们很久了，现在又要翻出来鞭尸。 最开始的时候，我们使用的是最朴素的 \(O(n)\) 试除 ......

prelogue 怎么感觉我这个人和随机化关系这么好。 鲤鱼我是从这篇博客中进行学习的。 Pollard-Rho 算法 Pollard-Rho 算法是一种求非 1 非自身的因子的高效算法。 main body 我们求素数平常是用的复杂度为 \(O(sqrt(n))\) 的试除法，如果 \(n\) 这 ......

Miller-Rabin 素性检测 部分内容摘自 题解 P4718/论 Miller-Rabin 算法的确定性化 - It's LUNATIC time!) 根据费马小定理，若 \(p\) 为素数，那么对于 \(1 \leq a < p\)，都有 \(a^{p-1} \equiv 1 \pmod p ......

补写算法流程。 生日悖论：值域为 \(n\)，时，期望随机 \(O(\sqrt{n})\)（OI-wiki 上给的是 \(\sqrt{2 n \ln 2}\)）个数有数字相同。（感觉有点奇怪，原表述是这么多次有数字相同的概率是 \(\frac{1}{2}\)。） 算法流程： 尝试分解 \(n\) 的 ......

# Pollard-Rho 分解算法 Pollard-Rho 算法是一种用于快速找到$n$的一个非平凡约数的方法。 ## 生日悖论 在不少于$23$个人中至少有两人生日相同的概率已经大于$50\%$。 更一般的形式，随机选取在$\left[ 1,N \right]$范围内的整数，期望到第$O(\sq ......