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 cremona)

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.

Patch up for review: depends on #8820 and #9931.

Attachments (2)

trac_10026-elog.patch (14.7 KB) - added by cremona 9 years ago.
applies to 4.6.rc0
trac_10026_reviewer.patch (915 bytes) - added by wuthrich 9 years ago.
to be applied after the first patch

Download all attachments as: .zip

Change History (11)

comment:1 Changed 9 years ago by cremona

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 9 years ago by cremona

I just checked that this still applies properly, and tests still pass, with the updated patch at #8820 (which still needs a new review).

comment:3 Changed 9 years ago by cremona

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 cremona

  • 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 cremona

  • 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.

Changed 9 years ago by cremona

applies to 4.6.rc0

comment:6 Changed 9 years ago by cremona

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).

Changed 9 years ago by wuthrich

to be applied after the first patch

comment:7 Changed 9 years ago by wuthrich

  • 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 cremona

Thanks, Chris. The paper is now at http://arxiv.org/abs/1011.0914 .

comment:9 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.6.1.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.