python 中大数的质因数分解

Question

whazzup,

遇到以下问题，我无法解决。处理长度在 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)

二.

x = input("Number: ")
mode = x[-1:]
x = int(x[:-1])
if int(x) < 1000000000000:
    faktorisiere(x)
else:
    if mode == 'f':
        faktorisiere(x)
    rx = int(sqrt(x)) + 1

    for i in range(1, rx+1):
        if mode == 'a':
            if x % i == 0:
                y = int(x/i)
                print(str(x), "=", i, "*", str(y))
        if mode == 'u':
            if i % 2 != 0:
                if x % i == 0:
                    y = int(x/i)
                    print(str(x), "=", i, "*", str(y))

但是第一个代码计算这些数字非常慢： 1917141215419419171412154194191714

第二个运行得更快一些，但是我得到了错误的输出，而且我找不到代码中的错误。我们以给定的数字为例。这些是 pythons 输出的第一行：

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。要因式分解更大的数字，您需要查看 椭圆曲线方法 或 二次筛法 等算法，但请注意，这两种算法都是复杂。

python 中大数的质因数分解

prime factorization with large numbers in python

python

primes

numbers

factorization

output