Factoring_PollardRho_gmpy2_int.py

# Factoring_PollardRho_gmpy2_int.py
# RSA-avaimen murtaminen: tulontekijöiden p ja q löytäminen
# Pollard Pho-menetelmällä
# Sopii suurillekin (yli 100 bit avaimille)
# Pääosa source: Pollard Rho algorithm - Wikipedia
# Käytetty kahdessa funktiosa gmpy2 korvaamaan Pythonin vakiofuntiot
# gcd korvattu gmpy2:n versiolla gmpy2.gcd
# (x**2+1) % n korvatt gmpy2:n gmpy2.f_mod(x**2+1,n)
# Nämä korvaukset pudottavat suurilla kokonaisluvuilla laskenta-ajan puoleen
# Juhani Kaukoranta, versio 22.8.2019

import time
import gmpy2

def PollardRho(n):
    x, y, p = 2, 2, 1
    f=lambda x: gmpy2.f_mod(x**2+1, n)
    while p == 1:
        x = f(x)
        y = f(f(y))
        p = gmpy2.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")