Анализ эффективности метода факторизации на эллиптических кривых. Практика

[saluev]

Вы бы хоть программу показали, это же Хабр, а не защита курсовой.
Ну и по-хорошему для анализа эффективности программу нужно запустить не три раза, а три тысячи раз и привести один усреднённый график.
P. S. С недавнего времени Хабр может в формулы.

[Qwarri]

Спасибо за комментарий, буду стремиться не допускать больше таких недочётов. А что насчёт программы, так у меня были сомнения по поводу нужна ли она здесь, так как это уже отдельная тема.

[Coocos]

Как оценивали нагрузку на память?

[Qwarri]

Я не делал тщательный анализ нагрузки на память, я лишь следил за производительностью и монитором ресурсов в Windows. В общем счёте программа занимает 0,4 МБ памяти в любой момент времени работы. И я сделал вывод, что нагрузки, как таковой, на память нет.

[novoxudonoser]

Статья хоть и короткая, но хорошая для первого раза. Но с точки зрения выводов и информативности ниочём.

[ShashkovS]

Что-то у вас не так с кодом или алгоритмом.

При помощи ро-метода Полларда на питоне:

Число 10 разложено на множители [2, 5] за 0.000020c
Число 437 разложено на множители [19, 23] за 0.000158c
Число 3127 разложено на множители [53, 59] за 0.000099c
Число 23707 разложено на множители [151, 157] за 0.000096c
Число 1752967 разложено на множители [1321, 1327] за 0.000142c
Число 6682189 разложено на множители [2579, 2591] за 0.000267c
Число 12659363 разложено на множители [3557, 3559] за 0.000249c
Число 494370889 разложено на множители [22079, 22391] за 0.000362c
Число 1435186847 разложено на множители [37781, 37987] за 0.000842c

Код на Python

from random import randint
from time import perf_counter


def gcd(a, b):
    """НОД(a,b). Считаем, что числа натуральные"""
    while b:
        a, b = b, a % b
    return a


def miller_rabin_test(a, n, s, d):
    """Один тест Миллера-Рабина.
    Является ли число 2 <= a <= n-2 свидетелем простоты для числа n (n-1 = d * 2**s)
    Если вдруг среди чисел a**(d*2**0), ..., a**(d*2**s) перед какой-то 1 идёт не -1,
    то число n — составное, а a — не является свидетелем простоты."""
    x = pow(a, d, n)  # x = a**(d*2**0)
    if x in (1, n - 1):
        return True
    for r in range(s - 1):
        x = (x * x) % n  # Из числа a**(d*2**r) вычисляем a**(d*2**(r+1))
        if x == 1:  # Ну всё, число составное
            return False
        elif x == n - 1:  # Нашлась -1. Число a — свидетель простоты для n
            return True
    return False  # Даже тест Ферма не пройден: a**(n-1) != 1


def miller_rabin(n):
    """Проверяет простоту числа n>3, выполняя log2(n) тестов Миллера-Рабина"""
    # Ищем разложение n-1 = n-1 = d * 2**s
    s, d = 0, n - 1
    while d % 2 == 0:
        s, d = s + 1, d // 2
    for _ in range(n.bit_length()):  # Повторяем тест log2(n) раз.
        a = randint(2, n - 2)  # берём случайное число
        if not miller_rabin_test(a, n, s, d):  # Если тест не пройден, то число составное
            return False
    return True  # С вероятностью 1/n**2 число простое


def pollards_rho_iter(n):
    """Поиск делителя у нечётного составного числа"""
    # Начинаем с функции F(x) = x**2 + 1 из точки x=2. Обычно это срабатывает
    x = y = 2
    a = 1
    while True:
        d = 1
        while d == 1:  # Если 1 < d < n, то мы нашли делитель d
            x = (x * x + a) % n  # x = F(F(..(F(x)..))
            y = (y * y + a) % n
            y = (y * y + a) % n  # y = F(F(F(F(..(F(F(x))..))))   (в два раз больше раз F)
            d = gcd(n, abs(x - y))
        if d < n:  # Если 1 < d < n, то мы нашли делитель d
            return d
        # Редко бывает так, что для функции x**2 + 1 при старте с 2 делитель не находится
        # В этом случае используем F(x) = x**2 + a, и стартуем с другого случайного числа
        x = y = randint(1, n - 1)
        a = randint(-100, 100) % n


def factor(n):
    """Факторизация числа при помощи ро-метода Полларда и тестов Миллера-Рабина"""
    # Избавляемся от всех двоек, троек и пятёрок
    ans = []
    for x in (2, 3, 5):
        while n % x == 0:
            ans.append(x)
            n //= x
    if n == 1:
        pass  # n = 2**a * 3**b * 5**c
    elif miller_rabin(n):  # Остаток простой
        ans.append(n)
    else:  # Ищем делители
        d = pollards_rho_iter(n)
        ans.extend(factor(d))
        ans.extend(factor(n // d))
    return sorted(ans)


nums = [10, 437, 3127, 23707, 1752967, 6682189, 12659363, 494370889, 1435186847]
for num in nums:
    st = perf_counter()
    fct = factor(num)
    en = perf_counter()
    print('Число {} разложено на множители {} за {:02f}c'.format(num, fct, en-st))

[sdev]

А как вы определили, что что-то не так с кодом, сравнивая при этом с совсем другим алгоритмом?

[ShashkovS]

Число 19120211505964799 разложено на множители [39916801, 479001599] за 0.028161c
Число 87178204020795979291199 разложено на множители [87178291199, 999999000001] за 1.611496c
Число 126040091637447457926052165206241443360998401 разложено на множители [479001599, 263130836933693530167218012159999999] за 0.427691c

Он имеет много общего с методом Полларда (p – 1), но работает значительно быстрей, следует отметить, что он является субэкспоненциальным методом.

14с в статье против 0.000842c у Полларда (который экспоненциальный, sqrt(мин. делитель))
Отличие по времени на 4 порядка…

[sdev]

Я правильно понимаю, что в рассчетах все числа укладываются в int? Тоесть к реальному RSA статья не имеет никакого отношения.

[vlanko]

1435186847 Перебором делителей находится от 0,44 мсекунды.
Число 19120211505964799 разложено на множители [39916801, 479001599] за 0.088c

[vlanko]

«На практике лучше всего подходит для нахождения небольших простых делителей числа, и поэтому считается узкоспециализированным алгоритмом.… потому что его сложность в основном зависит от наименьшего простого делителя p, а не от факторизируемого числа».
А примеры из статьи с максимальными делителями.