蟒蛇.找到数量巨大的因素.

Question

如何1636695303948070935006594848413799576108321023021532394741645684048066898202337277441635046162952078575443342063780035504608628272942696526664263794691在python中找到数字因子？

它不应该是素数.任何因素除了1和数量 - 可接受.

我从这里查看过没有结果的解决方案.

天真的解决方案如:

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

也行不通.

Answer 1

Pollard的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位数因子.作为练习,您可以实现维基百科文章中描述的一些加速.使用它,13位数因子大约在一分钟内.我不确定我对25位因子有耐心,但它应该是临界可行的.