n_pour_dh = 71632723108922042565754944705405938190163585182073827738737257362015607916694427702407539315166426071602596601779609881448209515844638662529498857637473895727439924386515509746946997356908229763669590304560652312325131017845440601438692992657035378159812499525148161871071841049058092385268270673367938496513
e_pour_dh = 1009

p = 1068522512900119147557173208241671116649415470577282880246316447896772822847296055763408358990225038564394875651124083651221230420679921054094436578154107
q = 67039039649712985497870124991029230637396829102961966888617807218608820150367734884009371490834517138450159290932430254268769414059732849732168245030420659

qdh_chiffre_avec_RSA = 70785482415899901219256855373079758876285923471951840038722877622097582944768442919300478197733262514534911901131859013939654902078384994979880540719293485131574905521151256806126737353610928922434810670654618891838295876181905553857594653764136067479449117470741836721372149447795646290103141292761424726007
pdh_chiffre_avec_RSA = 55044587110698448189468021909149190373421069219506981148292634221985403129928367209713497911359302701069378532959510957622709061077384648566361893749771744973388835727259855002207844685526295296408852878202498675158924213264474587673461598376054133832370354928763624202425050121409987087150490459351809040858
gdh_chiffre_avec_RSA = 43089172300844684958445369204000423742543038862350925279569289644298734265625491619486408239703259462606739540181409010715678916496299388069246398890469779970287613357772582024703107603034996120914490203805569384580718393586094166173301167583379300330660182750028000520221960355249560831414918130647224546308


phi_n = (p-1)*(q-1)

def gcd(a, b):
    if (a < b):
        t = a
        a = b
        b = t
    r = a % b
    while (r != 0):
        a = b
        b = r
        r = a % b
    return b

def factor(n,b):
	""" Factor using Pollard's p-1 method """

	a = 2;
	for j in range(2,b):
		a = a**j % n

	d = gcd(a-1,n);
	print "d:",d,"a-1:",a-1
	if 1 < d < n: return d;
	else: return -1;

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1]

d = (MMI(e_pour_dh, n_pour_dh))%phi_n;

qdh = (qdh_chiffre_avec_RSA^d)%n_pour_dh;
pdh = (pdh_chiffre_avec_RSA^d)%n_pour_dh;
gdh = (gdh_chiffre_avec_RSA^d)%n_pour_dh;

print("d = %s" %(d))
print("qdh = %s " %(qdh))
print("pdh = %s " %(pdh))
print("gdh = %s " %(gdh))