Pollard Rho 因式分解算法

- 日理万妓 2022-05-16 14:07 155阅读 0赞

转载自：[https://www.cnblogs.com/dalt/p/8437119.html][https_www.cnblogs.com_dalt_p_8437119.html]

# [Pollard Rho因子分解算法][https_www.cnblogs.com_dalt_p_8437119.html] #

<div class="postBody">
            <div id="cnblogs_post_body" class="blogpost-body"><p>　　有一类问题，要求我们将一个正整数x，分解为两个非平凡因子（平凡因子为1与x）的乘积x=ab。</p>

显然我们需要先检测x是否为素数（如果是素数将无解），可以使用[Miller-Rabin算法][Miller-Rabin]来进行测试。

Pollard Rho是一个非常玄学的方式，用于在O(n^1/4)的期望时间复杂度内计算合数n的某个非平凡因子。事实上算法导论给出的是O(√p)，p是n的某个最小因子，满足p与n/p互质。但是这些都是期望，未必符合实际。但事实上Pollard Rho算法在实际环境中运行的相当不错。

Pollard Rho利用伪随机数生成公式来提供待测因子，其公式为xi=xi-1^2+c(mod n)，其中c是开始时确认的随机常数。我们只要给出x1，利用这个公式可以生成一系列数值。由于每个数完全依赖于前一个数，因此数值的分布中必定含环，我们设t为环的路口，u为环的周长，那么有xt+i=xt+u+i。而整个数值分布就像一个ρ符号，因此该算法的后缀用Rho来表示。我们将该公式得出的序列视作随机序列。

生日悖论中指出一个√d个学生的班级中，期望至少有一对人在同一天生日，其中d是一年中的日期，即365。同样一个√d个人的班级中，至少有一对人在同一天生日的概率大于50%。我们将n视作一年中的天数，而1~n-1中的每个值都对应一年中的日期，将x1,x2,…视作学生，那么序列中期望有两个有两个人相同，只需要序列的长度达到√n即可。因此我们可以认为ρ符号的尾部与环的周长的期望均为√n。

假设n=ab，其中a与b均不是n的平凡因子，我们假设a<=b，可知a<=√n。我们记yi=xi(mod a)。可知：

yi=xi(mod&\#xA0;a)=(xi&\#x2212;12+c)(mod&\#xA0;n)(mod&\#xA0;a)=(xi&\#x2212;12+c)(mod&\#xA0;a)” role=”presentation”>yi=xi(mod a)=(x2i−1\+c)(mod n)(mod a)=(x2i−1\+c)(mod a)yi=xi(mod a)=(xi−12+c)(mod n)(mod a)=(xi−12+c)(mod a)

我们依据a为模数建立了新的一个ρ型轨迹，且a的ρ型轨迹的环必然仅出现n的ρ型轨迹的环上的数值（模a的结果）。由同样的分析可得a的ρ型轨迹的环的尾部和环的长度的期望均为n^(1/4)。对于a的ρ型轨迹的环上的任意一点k，假设其对应的是两个不同的值xi与xj，即xi<>xj(mod n)但xi=xj(mod a)。此时可以知(xi-xj)=rp(mod n)，而gcd(xi-xj, n)的结果必然是n的一个非平凡因子（且能被a整除）。我们可以利用一个特定的变量p先后在迭代到x1,x2,x4,x8,…时记录这些值，之后每次都校验gcd(xi-p, n)是否既非1又非n，如果满足则找到n的非平凡因子，否则继续迭代。之前说过a的ρ型轨迹的环的尾部和环的长度的期望均为n^(1/4)，因此当我们p记录xh时，其中xh落在a的ρ型轨迹的环上且h大于等于环的周长时，此时我们会沿着a的ρ型轨迹的环进行周而复始的循环迭代，最终在修改p之前xi回到了xh的位置，此时借助gcd(xi-p, n)我们就找到了一个n的非平凡因子。h的期望应该为O(n^(1/4))，因此时间复杂度的期望应该为O(n^(1/4))。

下面给出代码：

![复制代码][Image 1]

pollard_rho(x)
        c = random()
        xi = random()
        i = 1
        h = 1
        xh = xi
        while(true)
            xi = xi * xi + c
            f = gcd(x, abs(xi - xh))
            if(f != 1 && f != n)
                return f
            i = i + 1
            if( i == h * 2)
                h = i
                xh = xi

![复制代码][Image 1]

[https_www.cnblogs.com_dalt_p_8437119.html]: https://www.cnblogs.com/dalt/p/8437119.html
[Miller-Rabin]: http://www.cnblogs.com/dalt/p/8436883.html
[Image 1]: