#6384: [with patch, needs work] elliptic curve -- isogeny function is not robust
-- it doesn't check validity of its input
---------------------------+------------------------------------------------
Reporter: was | Owner: shumow
Type: defect | Status: new
Priority: major | Milestone: sage-4.1.1
Component: number theory | Keywords: elliptic curves, isogeny,
Reviewer: | Author:
Merged: |
---------------------------+------------------------------------------------
Changes (by shumow):
* cc: shu...@… (added)
Comment:
So, over all, thanks for the thorough once over here.[[BR]]
Sorry I didn't look at this lately. I have been very busy. I work full
time and I am finishing my master's thesis (which I wrote this class to do
research for.)[[BR]]
I changed this to "needs work", not because it is necessarily bad, but
because I want to discuss it more.[[BR]]
1) I don't think you should remove the algorithm parameter, which
defaults to none. First off I was planning on adding another algorithm
which is similar to the kohel from kernel polynomial variant, and that is
the main reason why I had the parameter. That, or someone smarter than me
can come along and add a new algorithm, and add the parameter to make it
easier to select the new version (or specify the old version for backward
compatibility.)[[BR]]
2) I am fine with taking the input as a point (or a pair of points) to
specify the generators of the kernel. However, I do not think that this
should replace the kernel list way of doing things. First off, it
unnecessarily breaks backwards compatibility. Second off, there was a
very good reason that I did not initially do the solution that you have
here, generating the list of input points from generators is quite slow.
Specifically, as you have it coded here, you end up doing n**2 work
inflating the kernel list. Now, if someone knows the list of points in
the kernel, (or knows that the kernel is cyclic) they have no choice but
to allow the init to run a quadratic complexity algorithm, when it would
have otherwise been linear. This actually becomes the slowest part of the
isogeny computation. I see no reason to not have this new way of doing
input work alongside the old way.[[BR]]
3) When changing this to work side by side with the old way, obviously not
all of the examples should be changed, as we still want to exercise the
old way of doing things.[[BR]]
I think that your general modification here is good, however, I would like
to switch this to work along side the old way of doing things. By
detecting the type of the input. If you prefer I make the change, that is
fine, but it will need to wait until I file my ms thesis, so after next
week.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6384#comment:8>
Sage <http://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
-~----------~----~----~----~------~----~------~--~---
