p=3700001
Fp=GF(p)
E=EllipticCurve([Fp(3),Fp(5)])
j=E.j_invariant()
l=13#Atkin prime
n=((l-1)/2).round()
r=2# Phi_13 factorize in factors of degree 2
s=12#Psi_13 factorize in factors of degree 12
#repsq(a,n) computes a^n
def repsq(a,n):
B = Integer(n).binary()
C=list(B)
k=len(B)-1
bk=a
i=1
while i <= k:
if C[i]=="1":
bk=(bk^2)*a
else:
bk=bk^2
i=i+1
return bk
d=E.division_polynomial(13)
Fps=GF(repsq(p,s),'a')
Fpr=GF(repsq(p,r),'b')
FFpr.<x>=PolynomialRing(Fpr)
Fl=GF(l)
c=GF(2)
rts=d.roots(Fps,multiplicities=False)
Px=rts[0]
Py2=Px^3+3*Px+5
c=Fl.multiplicative_generator()
def produx(n,Qx):
if is_odd(n):
pro=Qx-(E.division_polynomial(n-1,(Qx,1),two_torsion_multiplicity=1)*E.division_polynomial(n+1,(Qx,1),two_torsion_multiplicity=1))/((E.division_polynomial(n,(Qx,1),two_torsion_multiplicity=1)^2) * (Qx+3*Qx+5))
else:
pro=Qx-(E.division_polynomial(n-1,(Qx,1),two_torsion_multiplicity=1)*E.division_polynomial(n+1,(Qx,1),two_torsion_multiplicity=1))*(Qx^3+3*Qx+5)/(E.division_polynomial(n,(Qx,1),two_torsion_multiplicity=1)^2)
return pro
#Ray-polynomial
def EP(x,Qx,n):
i=2
m=(x-Qx)
while i<=n:
m=m*(x-produx(n,Qx))
i=i+1
return m
ep=EP(x,Px,n)
#A1.<theta>=FFpr.extension(ep)
#A1.<theta>=PolynomialQuotientRing(Fpr,ep)