class ReductionMap:
"""
INPUT:
- E -- Elliptic curve over K=Q(sqrt(5))
- P -- a prime in Q that splits 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.v = K.factor(self.P)
Emod0 = E.change_ring(self.v[0][0].residue_field())
Emod1 = E.change_ring(self.v[1][0].residue_field())
self.Emod0 = Emod0
self.Emod1 = Emod1
self.GFell = GF(ell)
# compute the ell-torsion subgroup
T0 = Emod0(0).division_points(ell)
T1 = Emod1(0).division_points(ell)
if len(T0) == ell:
self.T = T0
self.Emod = Emod0
elif len(T1) == ell:
self.T = T1
self.Emod = Emod1
else:
raise ValueError, "must have Emod[ell] of order ell"
# compute multiplier
self.card = self.Emod.cardinality()
self.multiplier = ZZ(self.card / ell)
# make discrete log table
# 1. find first nonzero element g in T
i = 0
g = self.T[i]
while g == 0:
i += 1
g = self.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)