wk6PA.py

import sys
sys.path.append('/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/')
import numbthy
import gmpy2
N1 = 179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581
N2 = 648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236866252211790085787877
N3 = 720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929
# challenge 1

gmpy2.get_context().precision = 1000
A1 = gmpy2.isqrt(N1) + 1

x1 = gmpy2.isqrt(A1 * A1 - N1)
p1,q1 = A1 - x1, A1 + x1

assert gmpy2.c_mod(N1,p1) == 0
print p1
#challenge 2

A2 = gmpy2.isqrt(N2) + 1
for i in range(2**20+1):
	x2 = gmpy2.isqrt(A2 * A2 - N2)
	if gmpy2.c_mod(N2,A2 - x2) == 0:
		print A2 - x2
		break
	A2 += 1
else:
	print "None found"

# challenge 3

A3 = gmpy2.isqrt(N3 * 24) + 1
for i in range(2**20 + 1):
	x3 = gmpy2.isqrt(A3 * A3 - 24*N3)
	if gmpy2.c_mod(N3,(A3+x3)/4) == 0:
		print (A3-x3)/6
		break
	A3 += 1
else:
	print "None found"

# challenge 4
ct = 22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256465839967942889460764542040581564748988013734864120452325229320176487916666402997509188729971690526083222067771600019329260870009579993724077458967773697817571267229951148662959627934791540
fn = N1 - p1 - q1 + 1
e = 65537
d = gmpy2.powmod(e,-1,fn)
assert gmpy2.c_mod(e * d,fn) + fn == 1
pt = gmpy2.powmod(ct,d,N1)
pt = str(hex(pt)).split('00')[-1]
print pt.decode("hex")