Pollard p-1算法 Python实现

以下是Pollard p-1算法的Python实现：

def pollard_p_1(n, B):
    a = 2
    for j in range(2, B+1):
        a = pow(a, j, n)
        d = math.gcd(a-1, n)
        if d > 1:
            return d
    return None

其中，参数`n`为待分解的数，参数`B`为算法中的参数，表示试除的范围。该算法的时间复杂度为O(B^2 log n)。

可以通过以下代码测试该算法：

n = 1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567
B = 1000
d = pollard_p_1(n, B)
print(d)

输出结果为`3`，表示`n`可以分解为`3 * 41152263004011559633744855963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893004115226300401155963374426826337448559670781893`。