Python。求大数因子。

Question

如何在python中找到像1636695303948070935006594848413799576108321023021532394741645684048066898202337277441635046162952078575443342063780035504608628272942696526664263794691这样的数字因子？你知道吗

它不应该是最好的。除1和数字以外的任何因素-可接受。你知道吗

我回顾了类似于here的解决方案，但没有结果。你知道吗

天真的解决方案，如：

def factor(n):
    i = 2
    limit = n / 2
    while i <= limit:
      if n % i == 0:
        return i
      i += 1
    return 1

也不起作用。你知道吗

Answer 1

Pollard's Rho是分解素数因子相对较小的大数的好工具。下面是一个简单的实现：

import random
from fractions import gcd

def pollardRho(n, seed = None):
    def f(x): return (x**2 + 1) % n
    if seed == None: seed = random.randint(0,n-1)
    t = h = seed
    t = f(t)
    h = f(f(h))
    d = gcd(t-h,n)
    while d == 1:
        t = f(t)
        h = f(f(h))
        d = gcd(t-h,n)
    return d,n//d

这将在几秒钟内找到问题中n的10位数因子。作为练习，您可以实现Wikipedia文章中描述的一些加速。用这个，13位数的系数在大约一分钟内下降。我不确定我是否有耐心接受25位数的因素，但这应该是可行的。你知道吗