Какая временная сложность потребуется для решения RSA Factoring Challenge?

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

Ваш алгоритм плохо реализован пробным делением. Выброси это.

Вот моя базовая библиотека простых чисел, использующая сито Эратосфена для перечисления простых чисел, алгоритм Миллера-Рабина для распознавания простых чисел и факторизацию колес, за которой следует алгоритм 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-битный номер практически мгновенно.

Чтобы учесть большие числа, вам придется работать усерднее. Посмотрите "Факторизация эллиптической кривой" и "Самоинициализирующееся квадратичное сито", чтобы найти алгоритмы факторинга, которые вы можете реализовать самостоятельно.