#18589: isogeny efficiency improvement
-------------------------+-------------------------------------------------
Reporter: | Owner:
cremona | Status: needs_work
Type: | Milestone: sage-6.8
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers:
elliptic curves | Work issues:
Keywords: | Commit:
isogeny | 47ccfd587402b953c612fcd3cddaa541a6847bd3
Authors: John | Stopgaps:
Cremona |
Report Upstream: N/A |
Branch: |
u/cremona/18589 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by cremona):
Replying to [comment:22 jdemeyer]:
> Since you write {{{Every kernel polynomial is a product of irreducible
factors of the division polynomial of the same degree}}}, could special
case 2 apply by just considering the polynomials of a given degree?
Yes: if for some degree d dividing l2=(l-1)/2 there are exactly (l-1)/2d
factors then their product must be a kernel poly.
Some more theory: each subgroup has l2 x-coordinates and the rational
function m(x) permutes these in a single cycle (by definition of "semi-
primitive root" as a class mod l which generates the multiplcative group
modulo <-1>). A kernel poly is a poly of degree l2 whose set of roots is
invariant under this map. Since the map is defined over the ground field,
each of the x-coordinates in any subgroup has the same degree d over the
base, so d is a divisor of l2 and the kernel poly is a product of l2/d
polys of degree d. On the other hand, an irreducible factor f of degree
d (where d didvides l2) need not be a factor of a kernel poly, as the F_3
example with l=13 shows. If that is the case then the orbit of f under
mult() will be longer than l2/d and we will detect that after l2/d steps
we have not returned to the start. In this circumstance we will have
removed l2/d factors from the list but this is only *part of* an orbit, so
later on when we start with one of the remaining factors in that orbit, we
may well iterate onto a factor which is already removed.
There, I have proved that g need not be in factors! And more -- if we
find a g which is not in factors then we have hit a part-orbit already
seen so can break.
--
Ticket URL: <http://trac.sagemath.org/ticket/18589#comment:29>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
