Комментарии 11
Вы бы хоть программу показали, это же Хабр, а не защита курсовой.
Ну и по-хорошему для анализа эффективности программу нужно запустить не три раза, а три тысячи раз и привести один усреднённый график.
P. S. С недавнего времени Хабр может в формулы.
Ну и по-хорошему для анализа эффективности программу нужно запустить не три раза, а три тысячи раз и привести один усреднённый график.
P. S. С недавнего времени Хабр может в формулы.
+4
Как оценивали нагрузку на память?
0
Статья хоть и короткая, но хорошая для первого раза. Но с точки зрения выводов и информативности ниочём.
0
Что-то у вас не так с кодом или алгоритмом.
При помощи ро-метода Полларда на питоне:
Число 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
При помощи ро-метода Полларда на питоне:
Число 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))
+2
А как вы определили, что что-то не так с кодом, сравнивая при этом с совсем другим алгоритмом?
+1
Число 19120211505964799 разложено на множители [39916801, 479001599] за 0.028161c
Число 87178204020795979291199 разложено на множители [87178291199, 999999000001] за 1.611496c
Число 126040091637447457926052165206241443360998401 разложено на множители [479001599, 263130836933693530167218012159999999] за 0.427691c
14с в статье против 0.000842c у Полларда (который экспоненциальный, sqrt(мин. делитель))
Отличие по времени на 4 порядка…
Число 87178204020795979291199 разложено на множители [87178291199, 999999000001] за 1.611496c
Число 126040091637447457926052165206241443360998401 разложено на множители [479001599, 263130836933693530167218012159999999] за 0.427691c
Он имеет много общего с методом Полларда (p – 1), но работает значительно быстрей, следует отметить, что он является субэкспоненциальным методом.
14с в статье против 0.000842c у Полларда (который экспоненциальный, sqrt(мин. делитель))
Отличие по времени на 4 порядка…
+1
Я правильно понимаю, что в рассчетах все числа укладываются в int? Тоесть к реальному RSA статья не имеет никакого отношения.
-1
1435186847 Перебором делителей находится от 0,44 мсекунды.
Число 19120211505964799 разложено на множители [39916801, 479001599] за 0.088c
Число 19120211505964799 разложено на множители [39916801, 479001599] за 0.088c
0
«На практике лучше всего подходит для нахождения небольших простых делителей числа, и поэтому считается узкоспециализированным алгоритмом.… потому что его сложность в основном зависит от наименьшего простого делителя p, а не от факторизируемого числа».
А примеры из статьи с максимальными делителями.
А примеры из статьи с максимальными делителями.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Анализ эффективности метода факторизации на эллиптических кривых. Практика