#11095: Add BMSS algorithm for isogenies of elliptic curves
------------------------------------------+---------------------------------
Reporter: defeo | Owner: cremona
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-4.7.1
Component: elliptic curves | Keywords: isogenies
Work_issues: | Upstream: N/A
Reviewer: John Cremona, Marco Streng | Author: Luca De Feo
Merged: | Dependencies:
------------------------------------------+---------------------------------
Comment(by defeo):
Replying to [comment:13 mstreng]:
>
> First of all, the comment "or a non-sense polynomial if no such isogeny
exists" (line 110) is inconsistent with the documentation of
{{{isogeny_BMSS}}}. Which of the two is correct?
I fixed the docs to be more explicit on this, hope it is clear now.
>
> Second, the test "{{{ker_poly.degree() != ell-1}}}" (line 113)
implicitly assumes that there is only one possible degree for a normalized
isogeny. It would help future developers to have a comment explaining that
this is always the case (it is, isn't it?)
Marco is right: the "normalized" requirement is very strong. Indeed if two
isogenies are normalized for the same models, then they are solution to
the same differential equation with the same initial conditions. In
characteristic 0, this means that their power series expansion at infinity
is the same, which I think should be enough to prove that there is only
one such isogeny.
In positive characteristic, this means that the power series are equal at
least up to the (p-1)/2-th term (which is the limit up to which the BMSS
algorithm can compute the solution). I am less sure about unicity in this
case, but I am inclined to think that only one isogeny of degree less than
p/4 will satisfy the condition (this is true for multiplication-by-m maps,
at least).
As an example, take the multiplication maps by 1 and by p-1 on a curve E:
they are both normalized for the models (E,E), which implies that the
expansion at infinity of the multiplication-by-(p-1) map is x +
O(x^((p-1)/2)). Of course the BMSS algorithm will refuse to compute the
second map, because it has degree (p-1)^2 > p/4.
As a final remark, if we know the right (u,r,s,t) we can normalize the
models, as John suggests. But, except for the case of scalar
multiplication maps, computing such an isomorphisms is very expensive. I'm
working on this in another patch.
> Third, why is the test "{{{not check}}}" there in the Stark case (line
100)? Could {{{isogeny_Stark}}} return non-sense polynomials just like you
say {{{isogeny_BMSS}}} does? Does a non-sense polynomial always imply that
no normalized isogeny exist?
Maybe not, but these algorithms all tend to have some special cases which
were not considered in the literature and which yield false answers. So
why not test as long as the test comes for free (we have to compute the
square root anyway).
> 2. The word "separable" seems to be missing from the {{{ValueErrors}}}
The constraints on the degree imply that if such an error is returned,
then p does not divide `ell` (otherwise a {{{ZeroDivisionError}}} is
returned instead), thus no unseparable isogeny of degree `ell` exists
either.
> 3. I noticed that (with the default options) the function
{{{isogeny_kernel}}} will first test if algorithm equals "Stark", "stark",
"Starks", or "starks", before detecting that it actually equals "BMSS". It
may speed things up by epsilon to put the most-used case first. (this is
not the reason for "needs work")
done
> ps. The patch bot seems to have understood that you only want the second
patch.
Yes, but it also used to mention a failure that I was not able to
reproduce. It seems to be down now, anyway.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11095#comment:18>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
