Factoring_PollardRho_int.py

# RSA-avaimen murtaminen: tulontekijöiden p ja q löytäminen Pythonilla
# Pollard Pho-menetelmällä
# Sopii suurillekin (yli 100 bit avaimille)
# Pääosa source: Pollard Rho algorithm - Wikipedia
# Factoring_PollardRho_int.py
# Juhani Kaukoranta, versio 20.8.2019

from math import gcd
import time

def PollardRho(n):
    x, y, p = 2, 2, 1
    f=lambda x: (x**2+1) % n
    while p == 1:
        x = f(x)
        y = f(f(y))
        p = gcd(abs(x-y),n)
    if p == n:
        return "Ei tekijöitä, avain alkuluku tms"
    else:
        q = n // p
        return [p,q]

n= int(input("anna RSA-avain "))
number = n
time0 = time.perf_counter()  # timer alku
print("Alkulukutekijät [p,q] = ",PollardRho(n))
time1 = time.perf_counter()
print("Aikaa kului ",time1-time0," sekuntia")