如何在python中找到像1636695303948070935006594848413799576108321023021532394741645684048066898202337277441635046162952078575443342063780035504608628272942696526664263794691
这样的数字因子?
它不应该是黄金时段。除1
和数字外的任何因素-可接受。
我从这里查看了类似的解决方案,但没有结果。
天真的解决方案,如:
def factor(n):
i = 2
limit = n / 2
while i <= limit:
if n % i == 0:
return i
i += 1
return 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位数的因素有耐心,但这应该是可行的。