import owiener
from math import gcd
from random import randint

def findPrimes(N, e, d):
	k = d * e - 1
	t = 1
	while t % 2 != 0:
		g = randint(2, N - 1)
		t = k
		print(t)
		x = pow(g, t, N)
		y = gcd(x - 1, N)
		while (not x > 1) or (not y > 1):
			t = t//2
			x = pow(g, t, N)
			y = gcd(x - 1, N)
		print("-------------------")

	p = y
	q = N//y
	return (p, q)

#Process can get stuck - if this happens end it and try again

#Enter values for N (the modulus) and e (the public exponent) here.
N = 62152379594791577050751898570724586922535551913356729458879540912241599620393562354793195069862013351547201293349813581115474199793236264722419357366262217643521043026183021191314384106480284544811693077375412055005880244282288564021774242100400928923767513937948900469441194121548432267221312254285623792367
e = 7374806538798594390337692624380085160123465503930753453406013411837629206061470231765641955123139013411847774165562876170649638176172519473411709935616472596656665469362429169679474703069993679610212529503460059650686853507575425563882260400217361559197173863292179409555388111772640536181921038506281844647
d = owiener.attack(e, N)

if d is None:
    print("Failed")

else:
	factors = findPrimes(N, e, d)
	print("Private exponent d={}".format(d))
	print("The factors: ", factors)
	print("The smallest factor: ", min(factors))
