作用
一种能快速找到大整数的一个非1、非自身的因子（也称非平凡因子）的算法。对于目前我所涉及的邻域来说，或许是用于RSA中N的分解。
相关思想
设分解$n，n=pq$，$q为n的非平凡因子$。这时我们需要一个用于生成伪随机数列的模$n$的多项式，设为：$g(x) \equiv x^2 + 1 (mod n)，x_1 = g(x)，x_2 = g(g(x))……$
可以知道，由于$n和初始值x$的存在，这个数列会不断重复某个子序列，可以举几个小的数验证。这种循环的结构即产生了$\rho$算法。
这里引用大佬的：
$Floyd’s cycle-finding algorithm$发现：设立两个节点，$i，j$，在每一步中，$i$每次移动一个节点，$j$每次移动两个节点，然后检查$gcd(x_i−x_j,n)$是否$≠1$，如果不等于，那么$gcd$的结果便是$p$。并且，这也意味着序列$x_k(modp)$也会重复。这是因为，如果$x_i \equiv x_j (modp)$, 那么$x_i与x_j$之间的差必然是p的倍数。同时，这也说明，$gcd(x_i−x_j，n)$不等于1的结果无论如何最终都会到来，但是可能是n自己，此时，代表$Pollard’s ρ algorithm$失败了，可以使用不同的起始值，再次运算。
在这个伪随机数列中，利用Floyd的循环检测算法的思想找出$p$来，当然也有可能失败，代码如下：
n = ...
def mapx(x):
x = (x*x+1)%n
return x
def pollard_rho (x1,x2):
while True:
x1 = mapx(x1)
x2 = mapx(mapx(x2))
p = gcd(x1-x2,n) #这里我用的gmpy2库里的函数
if (p == n):
print("fail")
return
elif (p!=1):
print("p: "+str(p))
print("q: "+str(n/p))
break
可以随机选个$n$来测试一下，例如$n = 160$，当我们选取不同的初始值，时会产生不同的结果（前提是选的n有不同的因子组合）：
pollard_rho(1, 1)
pollard_rho(2, 1)
pollard_rho(4, 3)
#输出结果
p: 32
q: 5.0
fail
p: 4
q: 40.0
变体
用相关的 Brent’s cycle finding method取代了 Floyd’s cycle-finding algorithm，使用了不同的循环检测方法，同样引用大佬的：
如果 $gcd(a,n)>1$，那么$gcd(ab,n)>1$（b为任意正整数）。所以，取代$Floyd’s cycle-finding algorithm$的每一步都检查$gcd(a,n)$，他定义了一个$z，z=(x_2−x_3(x_3−x_5……(x_{101}−x_{201}(modn)$即每一百步才检查一次$gcd(x_i−x_j,n)$，这么作主要是为了加速结果。 但有时它可能会引入重复因子导致算法失败，例如当n是一个正方形时。 但是
说不定哪次题目就用了变体。
相关例题
from Crypto.Util.number import getPrime, isPrime
flag = 'BCNS{***************}'
nbits = 2048
gbits = 1000
g = getPrime(int(gbits))
while True:
a = getPrime(int(nbits * 0.5) - gbits)
p = 2 * g * a + 1
if isPrime(p):
break
while True:
b = getPrime(int(nbits * 0.5) - gbits)
q = 2 * g * b + 1
if p != q and isPrime(q):
break
N = p * q
e = 65537
def str2int(s):
return int(s.encode('hex'), 16)
with open('pubkey.txt', 'w') as f:
f.write(str(e) + '\n')
f.write(str(N) + '\n')
plain = str2int(flag)
c = pow(plain, e, N)
with open('cipher.txt', 'w') as f:
f.write(hex(c))
需要引入相关论文$FURTHER \space ATTACKS \space ON \space SERVER-AIDED \space RSA \space CRYPTOSYSTEMS$：
条件：$当N=pq(N≥512bit),其中，(p−1)和(q−1)有一个大的公因数β$ ，在论文中提到的第一个攻击阶段：运用$Pollard’s \space ρ methods$ ，其中用于取伪随机值的maps函数为$ g(x)=x^{N−1}+3(modN)$
$通过分析p、q的生成过程，可以知道p、q有因子2g$，所以运用$Pollard’s \space ρ methods$分解n：
def mapx(x):
x = (pow(x,n-1,n)+3) % n
return x
def pollard_rho (x1,x2):
while True:
x1 = mapx(x1)
x2 = mapx(mapx(x2))
p = gcd(x1-x2,n)
if (p == n):
print "fail"
return
elif (p!=1):
print("p: "+str(p))
print("q: "+str(n/p))
break
def main():
pollard_rho(1,1)#初始点从1开始
return
n = ...
main()
总结
学到了RSA中能分解n的又一种方法！！！所以碰到n正常思路走不通的时候，可以尝试走这一条路。
参考：
算法学习笔记(55): Pollard-Rho算法 - 知乎 (zhihu.com)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com