请选择 进入手机版 | 继续访问电脑版

Pollard Rho 质因数分解

[复制链接]
谢世民 发表于 2021-1-2 19:42:51 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
暴力算法

这是一个暴力递归分解质因数的伪代码
  1. void rp(int n) {    if (n 是 质数) n 是 rp 的一个质因子, return;    罗列找到 n 的一个非 1 因子 p;    rp(p), rp (n / p);}
复制代码
此中判断质数可以用 Miller Rabin。该暴力复杂度的瓶颈是找因子,如果给定的                               n                          n               n 是一个大质数如                               1                               0                         9                              +                      7                          10^9+7               109+7,那么罗列的复杂度就一飞冲天了。
生日悖论

假设                               n                      =                      1                               0                         9                              +                      7                          n=10^9+7               n=109+7,只有一个非                               1                          1               1 因子。
如果一个班上有                               k                          k               k 个人,那么有两个生日相同的人的概率是多少?
答案为                               P                      (                      k                      )                      =                      1                      −                               ∏                                   i                            =                            1                                  k                                                 365                            −                            i                            +                            1                                  365                                  P(k)= 1 - \prod_{i=1}^k \frac{365-i+1}{365}               P(k)=1−∏i=1k​365365−i+1​。当                               k                      =                      48                          k=48               k=48 时,                              P                      (                      k                      )                      ≈                      0.960598                          P(k) \approx 0.960598               P(k)≈0.960598。
那么我们可以用生日悖论来举行找因子
我们在                               [                      1                      ,                      n                      ]                          [1,n]               [1,n] 中随便选一个数,那么他是因子的概率为                                        1                         n                                  \frac{1}{n}               n1​。
我们在                               [                      1                      ,                      n                      ]                          [1,n]               [1,n] 中随便选两个数                               a                          a               a 和                               b                          b               b,那么                               ∣                      a                      −                      b                      ∣                          |a-b|               ∣a−b∣ 是因子的概率为                                        2                         n                                  \frac{2}{n}               n2​。这相当于                               a                      =                      b                      +                      n                          a = b + n               a=b+n 和                               a                      =                      b                      −                      n                          a = b - n               a=b−n 两个情况。
我们在                               [                      1                      ,                      n                      ]                          [1,n]               [1,n] 中随便选                               k                          k               k 个数                                        a                         1                              ∼                               a                         k                                  a_1 \sim a_k               a1​∼ak​,对于任意两个数                                        a                         i                                  a_i               ai​ 和                                        a                         j                                  a_j               aj​,如果有                               gcd                      ⁡                      (                      ∣                               a                         i                              −                               a                         j                              ∣                      ,                      n                      )                      ≠                      1                          \gcd(|a_i-a_j|,n) \not =1               gcd(∣ai​−aj​∣,n)​=1,意味着我们找到了                               n                          n               n 的一个因子,它的概率为                                                  2                            ×                                                   k                                  (                                  k                                  −                                  1                                  )                                          2                                            n                                  \frac{2 \times \frac{k(k-1)}{2}}{n}               n2×2k(k−1)​​。当                               k                      =                               n                                  k = \sqrt{n}               k=n                                  ​ 时,概率已经靠近百分之百了。但如果求这                               k                          k               k 个数的两两差,复杂度又回到了                               O                      (                      n                      )                          O(n)               O(n),显然不可行。
伪随机函数

                                              f                            i                                  =                         (                                   f                                       i                               −                                           1                                  2                                          +                               c                                            )                                    m                            o                            d                                   n                               f_i = (f_{i-1^2+c}) \bmod n                   fi​=(fi−12+c​)modn
此中                               c                          c               c 可以是                               [                      1                      ,                      n                      ]                          [1,n]               [1,n] 内的任意一个数,我们任取一个数作为                                        f                         1                                  f_1               f1​,然后剩下的数列根据这个函数随机生成。可以发现在                                               m                         o                         d                               p                          \bmod p               modp 下,一旦有两个数相同,那么这个数列会陷入循环节,陷入循环节前的长度渴望是                                        n                                  \sqrt n               n                                  ​ 的。
那么这个函数的优点是什么呢?如果                               gcd                      ⁡                      (                               f                         i                              −                               f                         j                              ,                      n                      )                      ≠                      1                          \gcd(f_i-f_j,n) \not=1               gcd(fi​−fj​,n)​=1,那么有                                        f                                   i                            +                            1                                       −                               f                                   j                            +                            1                                       =                      (                               f                         i                              −                               f                         j                              )                      (                               f                         i                              +                               f                         j                              )                          f_{i+1}-f_{j+1}=(f_i-f_j)(f_i+f_j)               fi+1​−fj+1​=(fi​−fj​)(fi​+fj​),                              gcd                      ⁡                      (                               f                                   i                            +                            1                                       ,                               f                                   j                            +                            1                                       ,                      p                      )                      ≠                      1                          \gcd(f_{i+1},f_{j+1},p) \not = 1               gcd(fi+1​,fj+1​,p)​=1。
算法实现

  1. int f(int a, int n, int c){        return (1ll * a * a + c) % n;}void factor(int n) {        if (miller_rabin(n)) {                z[++cnt] = n; return ;        }        int g = n;        while (g == n) g = pollard_rho(n);     //若 g == n,则这次 pollard_rho 的 rp 欠好,没有找到因子        factor(g), factorn(n / g);}
复制代码
现在我们要实现 Pollard_Rho 的主体了。Pollard_Rho 的思想就是在随机数列上选一些数与                               n                          n               n 求最大公约数,如果遇到环则跳出。现在有一个效率低下的双指针法。
  1. int pollard_rho(int n) {        int c = rand() % (n - 1) + 1;        int v1 = c;        int v2 = f(v1,n,c);        while (v1 != v2) {                int g = gcd(n, abs(v1 - v2));                if (g > 1) return g;                v1 = f(v1,n,c); //v1 跳一次                v2 = f(v2,n,c); v2 = f(v2,n,c); //v2 跳两次        }        return n;}
复制代码
我们知道求                               gcd                      ⁡                          \gcd               gcd 的复杂度是                               log                      ⁡                          \log               log 的,求太多次会使得代码时间复杂度低下。我们不如用倍增的思想,让                               v                      2                          v2               v2 在一个范围中跳上好反复,把这反复的效果一起求一下                               gcd                      ⁡                          \gcd               gcd。这样看上去比力玄学,但是对复杂度却如虎添翼。
[code]int pollard_rho(int n) {        int c = rand() % (n - 1) + 1;        int v1 = 0;        for (int s = 1, t = 2; s
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )