2011-07-01-saturate

K.<a> = NumberField(x^2 - x - 1) import psage.ellcurve.lseries.sqrt5 as sqrt5w 

def aplist(E, B): # doesn't give 2, 3, 5 yet v = sqrt5w.TracesOfFrobenius(E, B) v._compute_split_traces() return v.aplist() 

def ap(E,p): return E.change_ring(p.residue_field()).trace_of_frobenius() 

E = EllipticCurve([0,-a,1,-a-1,2*a+1] ); E 

Elliptic Curve defined by y^2 + y = x^3 + (-a)*x^2 + (-a-1)*x + (2*a+1)
over Number Field in a with defining polynomial x^2 - x - 1

Elliptic Curve defined by y^2 + y = x^3 + (-a)*x^2 + (-a-1)*x + (2*a+1) over Number Field in a with defining polynomial x^2 - x - 1

E.gens() 

[(0 : -a - 1 : 1), (-3/4*a + 1/4 : -5/4*a - 5/8 : 1)]

[(0 : -a - 1 : 1), (-3/4*a + 1/4 : -5/4*a - 5/8 : 1)]

time v = aplist(E,10^6) 

Time: CPU 3.48 s, Wall: 3.48 s

Time: CPU 3.48 s, Wall: 3.48 s

v[:10] 

[(2, 0, None), (3, 0, None), (5, 0, None), (7, 0, None), (11, 4, 0),
(11, 7, -3), (13, 0, None), (17, 0, None), (19, 9, -7), (19, 10, 2)]

[(2, 0, None), (3, 0, None), (5, 0, None), (7, 0, None), (11, 4, 0), (11, 7, -3), (13, 0, None), (17, 0, None), (19, 9, -7), (19, 10, 2)]

class ReductionMap: """ INPUT: - E -- Elliptic curve over K=Q(sqrt(5)) - P -- a split prime in K - ell -- a prime that exactly divides the cardinality of E mod P. OUTPUT: - a callable map from E(K) to GF(ell) """ def __init__(self, E, P, ell): self.E = E self.P = P self.ell = ell self.k = self.P.residue_field() Emod = E.change_ring(self.k) self.Emod = Emod self.GFell = GF(ell) # compute the ell-torsion subgroup T = Emod(0).division_points(ell) if len(T) != ell: raise ValueError, "must have Emod[ell] of order ell" self.T = T # compute multiplier self.card = Emod.cardinality() self.multiplier = ZZ(self.card / ell) # make discrete log table # 1. find first nonzero element g in T i = 0 g = T[i] while g == 0: i += 1 g = T[i] dlog = {g:1} # 2. set h to 2*g, 3*g, .., recording the multiple h = g + g for n in range(2,ell+1): dlog[h] = n h += g self.dlog = dlog def __call__(self, Q): # Reduce Q to the curve over the finite field. # Then multiple the result by #Emod/ell. # Finally write in terms of generator using dlog table. Qbar = self.Emod(Q) n = self.dlog[self.multiplier * Qbar] return self.GFell(n) 

ell = 5 E = EllipticCurve([0,-a,1,-a-1,2*a+1] ) P0 = K.primes_above(89)[1] psi0 = ReductionMap(E, P0, ell) P1 = K.primes_above(179)[1] psi1 = ReductionMap(E, P1, ell) 

Q = E.gens(); Q 

[(0 : -a - 1 : 1), (-3/4*a + 1/4 : -5/4*a - 5/8 : 1)]

[(0 : -a - 1 : 1), (-3/4*a + 1/4 : -5/4*a - 5/8 : 1)]

def phi(x): return vector([psi0(x), psi1(x)]) 

phi(Q[0]) 

(3, 2)

(3, 2)

phi(Q[1]) 

(0, 1)

(0, 1)

ell = 3 E = EllipticCurve([0,-a,1,-a-1,2*a+1] ) P0 = K.primes_above(89)[1] psi0 = ReductionMap(E, P0, ell) P1 = K.primes_above(179)[1] psi1 = ReductionMap(E, P1, ell) def phi(x): return vector([psi0(x), psi1(x)]) phi(Q[0]), phi(Q[1]) 

((1, 1), (0, 0))

((1, 1), (0, 0))

Q[1] 

(-3/4*a + 1/4 : -5/4*a - 5/8 : 1)

(-3/4*a + 1/4 : -5/4*a - 5/8 : 1)

Q2 = Q[1].division_points(3)[0]; Q2 

(a + 1 : -a - 1 : 1)

(a + 1 : -a - 1 : 1)

phi(Q[0]), phi(Q2) 

((1, 1), (0, 2))

((1, 1), (0, 2))

 

 

 

for ell in primes(300): if ell!=5 and len(K.factor(ell))==2: for P in K.primes_above(ell): n = E.change_ring(P.residue_field()).cardinality() if n%15==0: print ell, n 

89 90
179 195
269 270
281 300

89 90
179 195
269 270
281 300

 

Q = E.gens(); Q 

[(0 : -a - 1 : 1), (-3/4*a + 1/4 : -5/4*a - 5/8 : 1)]

[(0 : -a - 1 : 1), (-3/4*a + 1/4 : -5/4*a - 5/8 : 1)]

psiQ[0] 

(0 : -a - 1 : 1)

(0 : -a - 1 : 1)

psi(Q) 

2

2

psi(G[1]) 

0

0