Алгоритмы факторизации числа 30 десятичных чисел git

Question

Мой профессор дал мне задачу факторинга RSA. Данный модуль имеет длину 30 десятичных цифр. Я много искал об алгоритмах факторинга. Но было довольно сложно выбрать один для моих требований. Какие все алгоритмы дают лучшую производительность для 30 десятичных чисел di git?

Примечание. До сих пор я читал о приближении грубой силы и квадратичном сите. Последний сложен и занимает много времени.

Answer 1

Есть еще один метод, называемый Алгоритм Полларда Rho , который не так быстр, как GNFS, но способен вычислять числа 30-ди git в считанные минуты, а не часы.

Алгоритм очень прост. Он останавливается, когда находит какой-либо фактор, поэтому вам нужно вызывать его рекурсивно, чтобы получить полную факторизацию. Вот базовая c реализация в Python:

def rho(n):
    def gcd(a, b):
        while b > 0:
            a, b = b, a%b
        return a
    g = lambda z: (z**2 + 1) % n
    x, y, d = 2, 2, 1
    while d == 1:
        x = g(x)
        y = g(g(y))
        d = gcd(abs(x-y), n)
    if d == n:
        print("Can't factor this, sorry.")
        print("Try a different polynomial for g(), maybe?")
    else:
        print("%d = %d * %d" % (n, d, n // d))

rho(441693463910910230162813378557) # = 763728550191017 * 578338290221621

Или вы можете просто использовать существующую библиотеку программного обеспечения. Я не вижу особого смысла в изобретении этого конкретного колеса.