解决 RSA 分解挑战需要什么样的时间复杂度？

Question

虽然挑战早就结束了，但我有点无聊所以我决定尝试分解一些数字。

我最初有一个 O(n) 算法，但后来，我决定研究大 O 表示法。

显然（我可能是错的），O(n) 算法和 O(2n) 算法基本上具有相同的运行时间。 O(n) 和 O(4n) 算法也是如此。事实上，O(n) 和 O(cn) 算法（其中 c 是一个整数）本质上具有相同的运行时间。

所以现在，我有一个 O(8n) 算法，但它对于 77 位数字来说不够快。

分解前几个 RSA 数字需要什么样的时间复杂度（不到 5 分钟）？

我的 O(8n) 算法：

import math

num = int(input())

sq = math.sqrt(num)

if num % 2 == 0:
  print(2, int(num / 2))

elif sq % 1 == sq:
  print(int(sq), int(sq))

else:

  sq = round(sq)

  a = 3
  b = sq + (1 - (sq % 2))

  c = ((b + 1) / 2)
  d = ((b + 1) / 2)
  c -= (1 - (c % 2))
  d += (1 - (d % 2))

  e = ((c + 1) / 2)
  f = ((c + 1) / 2)
  e -= (1 - (e % 2))
  f += (1 - (f % 2))
  g = ((d + 1) / 2) + d
  h = ((d + 1) / 2) + d
  g -= (1 - (g % 2))
  h += (1 - (h % 2))


  while a <= sq and num % a != 0 and b > 2 and num % b != 0 and c <= sq and num % c != 0 and d > 2 and num % d != 0 and e <= sq and num % e != 0 and f > 2 and num % f != 0 and g <= sq and num % g != 0 and h > 2 and num % h != 0:

    a += 2
    b -= 2
    c += 2
    d -= 2
    e += 2
    f -= 2
    g += 2
    h -= 2


  if num % a == 0:
    print(a, int(num / a))
  elif num % b == 0:
    print(b, int(num / b))
  elif num % c == 0:
    print(c, int(num / c))
  elif num % d == 0:
    print(d, int(num / d))
  elif num % e == 0:
    print(e, int(num / e))
  elif num % f == 0:
    print(f, int(num / f))
  elif num % g == 0:
    print(g, int(num / g))
  elif num % h == 0:
    print(h, int(num / h))

Answer 1

你的算法是执行不力的试验划分。扔掉它。

这是我的基本素数库，使用 Eratosthenes 筛法来枚举素数，使用 Miller-Rabin 算法来识别素数，然后使用轮因式分解和 Pollard 的 rho 算法来因式组合，我留给你翻译成 Python:

function primes(n)
    i, p, ps, m := 0, 3, [2], n // 2
    sieve := makeArray(0..m-1, True)
    while i < m
        if sieve[i]
            ps := p :: ps # insert at head of list
            for j from (p*p-3)/2 to m step p
                sieve[i] := False
        i, p := i+1, p+2
    return reverse(ps)

function isPrime(n, k=5)
    if n < 2 then return False
    for p in [2,3,5,7,11,13,17,19,23,29]
        if n % p == 0 then return n == p
    s, d = 0, n-1
    while d % 2 == 0
        s, d = s+1, d/2
    for i from 0 to k
        x = powerMod(randint(2, n-1), d, n)
        if x == 1 or x == n-1 then next i
        for r from 1 to s
            x = (x * x) % n
            if x == 1 then return False
            if x == n-1 then next i
        return False
    return True

function factors(n, limit=10000)
    wheel := [1,2,2,4,2,4,2,4,6,2,6]
    w, f, fs := 0, 2, []
    while f*f <= n and f < limit
        while n % f == 0
            fs, n := f :: fs, n / f
        f, w := f + wheel[w], w+1
        if w = 11 then w = 3
    if n == 1 return fs
    h, t, g, c := 1, 1, 1, 1
    while not isPrime(n)
        repeat
            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)
        while g == 1
        if isPrime(g)
            while n % g == 0
                fs, n := g :: fs, n / g
        h, t, g, c := 1, 1, 1, c+1
    return sort(n :: fs)

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e%2 == 1
            x, e := (x*b)%m, e-1
        else b, e := (b*b)%m, e//2
    return x

function gcd(a, b)
    if b == 0 then return a
    return gcd(b, a % b)

如果实施得当，该算法几乎可以立即因式分解 79 位数字。

要因式分解更大的数字，您将需要更加努力。查找 "elliptic curve factorization" 和 "self-initializing quadratic sieve" 以查找您可以自己实现的因式分解算法。

解决 RSA 分解挑战需要什么样的时间复杂度？

What sort of time complexity would be required to solve the RSA Factoring Challenge?

algorithm

big-o

rsa

time-complexity

python-3.x