【学习笔记】Miller Rabin & Pollard-rho
$Miller-Rabin$ 为大质数测试算法, $Pollard-rho$ 为大数因式分解算法.
费马小定理
若 $p \in Prime$ , 且 $gcd(a,p) = 1$ , 那么 $a^{p-1} \equiv 1 \pmod{p}$ , 如果存在 $a < p$ , 且 $a^{p-1} \bmod p \not= 1$ , 则 $p$ 肯定不是素数.
有限域上的平方根定理
如果 $p$ 是一个奇素数且 $e \geqslant 1$ , 则方程
仅有两个根 $x = 1$ 或者 $x = -1$ , 注意到是在模 $p$ 的意义下 , $x = -1$ 等价于 $x = p-1$ , $\pm1$ 也称为 $1$ 的平凡平方根.
很容易有一个推论 , 如果对模 $n$ 存在 $1$ 的非平凡平方根 , $n$ 一定是合数.
$Miller-Rabin$
对以一个大数 $n$ , 判断 $n$ 是不是素数的时候 , 可以先考虑 $a^{n-1} \equiv 1 \pmod{n}$
对于 $n-1$ , 一定可以拆分成 $2^s+d$ :
可以从 $x = a^d$ 开始 , 依次平方 $s$ 次 , 每次平方的时候模上 $n$ , 按照平方根定理 , 如果模上 $n$ 的结果为 $1$ 的话 , 那么 $x$ 一定为 $1$ 或者 $n-1$ , 如果不满足则不是素数 , $x = x^2$ 再次循环 , 最后再判断是否满足费马小定理 .
每次随机选择一个在 $\left[2,n-1 \right]$ 的数字作为 $a$ , 可以重复测试 .
由于 $mod$ 上的是 $n$ , $n$ 是一个大数 , 所以快速幂中的乘法 , 需要快速乘法实现 . 不然就算模上之后再相乘也会溢出 .
虽然是随机算法 , 但正确率很客观 .
$Pollard-rho$
算法大致流程如下 , 先判断当前数是否是素数了 , 如果是则直接返回 . 如果不是素数的话 , 试图找到当前数的一个因子 $\left(可以不是质因子 \right)$ . 然后递归对该因子和约去这个因子的另一个因子进行分解 .
那么自然的疑问就是 , 怎么找到当前数 $n$ 的一个因子 . 我们假设要找到的因子为 $p$ , 随机取一个 $x_1$ , 由 $x_1$ 构造 $x_2$ , 使得 $p$ 可以整除 $x_1-x_2$ 且 $x_1-x_2$ 不能整除 $n$ 则 $p = gcd(x_1-x_2,n)$ , 结果可能是 $1$ 也可能不是 $1$ . 如果不是 $1$ 就寻找成功了一个因子 , 返回因子 ; 如果是 $1$ 就寻找失败 , 那么我们就要不断调整 $x_2$ , 具体的办法通常是 $x_2 = x_2 \times x_2 +c$ ( $c$ 是自己定的) 直到出现 $x_2$ 出现了循环等于 $x_1$ 表示 $x_1$ 选取失败重新选取 $x_1$ 重复上述过程 .