python中的大数素因式分解

Question

砰的一声

有以下问题，我无法修好。 处理长度在5-52之间的数字，我不想得到它们的素因子。 使用Python，我发现了以下两种算法：

一

def faktorisiere(n):
    l = []  # Lösungsmenge
    # Auf Teilbarkeit durch 2, und alle ungeraden Zahlen von 3..n/2 testen
    for i in chain([2], range(3, n//2 + 1, 2)):
        # Ein Teiler kann mehrfach vorkommen (z.B. 4 = 2 * 2), deswegen:
        while n % i == 0:
            l.append(i)
            print(i)
            n = n // i  # "//" ist ganzzahlige Division und entspricht int(n/i)
        if i > n:  # Alle Teiler gefunden? Dann Abbruch.
            break
    print(l)

二。

^{pr2}$

但是第一个代码是非常慢的，像这样计算数字： 1917141215419419171412154194191714

第二个是工作速度快一点，但是我得到了错误的输出，我在代码中找不到错误。 我们以给定的数字为例。 以下是Python输出的第一行：

• 1917141215419419171412154194191714=1* 1917141215419419143900621852114944

• 1917141215419419171412154194191714 =2*958570607709709571950310926057472

• 1917141215419419171412154194191714=3* 639047071806473023947675938062336

但正如你所见，这些乘法并不等于结果。 密码有错误吗？ 还是仅仅因为数字的长度？ 希望你能帮助我。

致以最良好的祝愿， 计时工

Answer 1

你需要一个比试除法更好的算法来计算你正在处理的数字的大小。一个简单的步骤是从试验组升级到John Pollard的rho算法：

Python 2.7.13 (default, Mar 13 2017, 20:56:15)
[GCC 5.4.0] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> def isPrime(n, k=5): # miller-rabin
...     from random import randint
...     if n < 2: return False
...     for p in [2,3,5,7,11,13,17,19,23,29]:
...         if n % p == 0: return n == p
...     s, d = 0, n-1
...     while d % 2 == 0:
...         s, d = s+1, d/2
...     for i in range(k):
...         x = pow(randint(2, n-1), d, n)
...         if x == 1 or x == n-1: continue
...         for r in range(1, s):
...             x = (x * x) % n
...             if x == 1: return False
...             if x == n-1: break
...         else: return False
...     return True
...
>>> def factors(n, b2=-1, b1=10000): # 2,3,5-wheel, then rho
...     def gcd(a,b): # euclid's algorithm
...         if b == 0: return a
...         return gcd(b, a%b)
...     def insertSorted(x, xs): # linear search
...         i, ln = 0, len(xs)
...         while i < ln and xs[i] < x: i += 1
...         xs.insert(i,x)
...         return xs
...     if -1 <= n <= 1: return [n]
...     if n < -1: return [-1] + factors(-n)
...     wheel = [1,2,2,4,2,4,2,4,6,2,6]
...     w, f, fs = 0, 2, []
...     while f*f <= n and f < b1:
...         while n % f == 0:
...             fs.append(f)
...             n /= f
...         f, w = f + wheel[w], w+1
...         if w == 11: w = 3
...     if n == 1: return fs
...     h, t, g, c = 1, 1, 1, 1
...     while not isPrime(n):
...         while b2 <> 0 and g == 1:
...             h = (h*h+c)%n # the hare runs
...             h = (h*h+c)%n # twice as fast
...             t = (t*t+c)%n # as the tortoise
...             g = gcd(t-h, n); b2 -= 1
...         if b2 == 0: return fs
...         if isPrime(g):
...             while n % g == 0:
...                 fs = insertSorted(g, fs)
...                 n /= g
...         h, t, g, c = 1, 1, 1, c+1
...     return insertSorted(n, fs)
...
>>> factors(1917141215419419171412154194191714)
[2, 3, 13, 449941L, 54626569996995593878495243L]

因子分解立即返回。请参见here以了解其工作原理的说明。要计算更大的数，您需要研究像椭圆曲线法或二次筛法这样的算法，但要注意这两种算法都很复杂。在