def tesbitcoincurve1():
	"""
	sage code:  http://sagemath.org, can be run in a browser in
	the cloud
	to run: %runfile file.sage

	experiments with bitcoin's SEC256k1 curve
	"""
	p=  0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
	Gx= 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
	Gy= 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
	E=EllipticCurve(GF(p),[0,7]);G=E(Gx,Gy)
	n=115792089237316195423570985008687907852837564279074904382605163141518161494337
	#print n*G==0
	#public key
	QA=E(111,110020423816543951948138174357929621064214669117893252455581053961287533632517) # x=111, private key not known

	(r,s),H=(111, 111),0
	v1=ECDSA_verify(r,s,n,H,G,QA)
	print v1==r
	(r,s),H=(78357151550401202949332147590566221935398179112989344213812814774602295022407, 97074620393858699186451566299627064894117871696032124298208988958060228258372),0
	v1=ECDSA_verify(r,s,n,H,G,QA)
	print v1==r
	r,s=(105428374047743273196882821059891338511368444654956635403964917579221889109295, 110610231642529734310226903034289623182103004467015769893285040360370025301816)
	H=r
	v1=ECDSA_verify(r,s,n,H,G,QA)
	print v1==r
	r,s=(88726997827321435678026270701493246247383349479297427343226348386495743771888, 6369173660802749257382322127278165968358828480647562576685803871983831660923)
	H=s
	v1=ECDSA_verify(r,s,n,H,G,QA)
	print v1==r
	(r,s),H=(105238699896951558262377011680716928670929106668167672998668678863061090326385, 102286764830003424766749795690788297189374412259121264591707039647964876795035),6206150873392997599270790826086018442478461413119740184175413055321497803859
	v1=ECDSA_verify(r,s,n,H,G,QA)
	print v1==r


def ECDSA_verify(r,s,n,H,G,QA):
	K=Integers(n)
	w=K(s)**(-1)
	u1=H*w
	u2=r*w
	u1,u2=lift(u1),lift(u2)
	x1,y1=(u1*G+u2*QA).xy()
	x1=lift(x1)
	#valid if r==x1
	return x1

tesbitcoincurve1()