#python
#python
Вопрос:
Это доморощенная функция с некоторыми проблемами. Я предполагаю, что я где-то ошибся в цикле. Это не дает последовательных ответов — я понимаю, что это то, что означает «эвристический», но я думаю, что это не должно быть проблемой, скажем, для n = = 57.
def Rho_Heuristic(n):
import random
cum_d = 1
x = random.randint(0, n-1)
y = x
k = 2
i = 1
while not(cum_d == n):
i = i 1
x = (x*x-1)%n
d = GCD(y-x, n)
if (not(d == 1) and not(d == n)):
print d
cum_d = (d * cum_d)
if i==k:
y = x
k = 2*k;
Комментарии:
1. В чем ваш вопрос? Как вы можете ожидать последовательных ответов при выборке случайного целого числа? Также, для других, кто не слышал об этом алгоритме: Rho алгоритм Полларда
2. Похоже, что эта реализация была взята из: snippets.dzone.com/posts/show/4201 .
Ответ №1:
Эвристика Rhos Полларда — это эвристика. Возвращаемые факторы всегда будут правильными, просто он редко возвращает их все. PRH хорош, если вам нужно найти факторы с определенными характеристиками. Когда я реализовал RSA-атаку proof of concept, я просто продолжал запускать ее, пока не получил простые числа, которые имели смысл.
Ответ №2:
Если вам нужен детерминированный вывод для любых заданных входных данных, вызовите :
random.seed(0)
Когда вы запускаете свою программу.