Opened 9 years ago
Closed 9 years ago
#10026 closed enhancement (fixed)
Complex elliptic logs -- simplified algorithm
Reported by: | cremona | Owned by: | cremona |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.6.1 |
Component: | elliptic curves | Keywords: | elliptic logarithms |
Cc: | wuthrich, was | Merged in: | sage-4.6.1.alpha2 |
Authors: | John Cremona | Reviewers: | Chris Wuthrich |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Complex elliptic logs were implemented in #6390 following joint work by John Cremona and Thotsaphon Thongjunthug (as talked about by JC at SD23 in Leiden). Now the final touches are being put to our joint paper, we found a small simplification to the algorithm, where the iteration now deals with pairs of complex numbers rather than triples. There is no essential difference except very slightly simpler code, but it is desirable that the code should match the paper in which the algorithm is developed.
Attachments (2)
Change History (11)
comment:1 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
Note: this should not get a positive review until this example works properly (reported by WAS):
K.<w> = QuadraticField(2); K E = EllipticCurve([ 0, -1, 1, -3*w -4, 3*w + 4 ])
and both elliptic_logarithm and elliptic_exponential take a long time (i.e., don't finish while I'm waiting). Is this expected? I don't understand the complexity, but I sort of thought they would be nearly instant.
embs = K.embeddings(CC) Lambda = E.period_lattice(embs[0]); Lambda T = E.simon_two_descent() P,Q = T[2] Lambda.elliptic_logarithm(P,10)
[wait foreover?]
I have not yet checked that this behaviour still happens after the patch.
comment:4 Changed 9 years ago by
- Milestone changed from sage-4.6 to sage-4.6.1
- Status changed from needs_review to needs_work
The patch does not fix that, so I have put it back to "needs work" and when fixed, this example should be included as a new doctest.
comment:5 Changed 9 years ago by
- Cc was added
- Status changed from needs_work to needs_review
I have replaced the patch by one which now works for the reported problem example. Essentially, I just made the elliptic_logarithm function use my new code in all cases, and adjusted some doctests slightly.
Ready for review again.
comment:6 Changed 9 years ago by
Another update with a better solution: there is now specific code for all three cases of real points on real curves, which uses the simplified iteration (with real variables).
comment:7 Changed 9 years ago by
- Reviewers set to Chris Wuthrich
- Status changed from needs_review to positive_review
apart from the minor documentation error that I found (and corrected with the second patch) I can not see any problem with this. All the test pass. I do trust the authors of the paper about the algorithms in the patch.
comment:8 Changed 9 years ago by
Thanks, Chris. The paper is now at http://arxiv.org/abs/1011.0914 .
comment:9 Changed 9 years ago by
- Merged in set to sage-4.6.1.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
I just checked that this still applies properly, and tests still pass, with the updated patch at #8820 (which still needs a new review).