Opened 5 years ago

Closed 5 years ago

Last modified 3 years ago

#6390 closed enhancement (fixed)

Implement elliptic logarithms (complex case)

Reported by: cremona Owned by: cremona
Priority: major Milestone: sage-4.4
Component: elliptic curves Keywords: elliptic curve logarithm
Cc: robertwb, rlm Merged in: sage-4.4.alpha0
Authors: John Cremona Reviewers: Chris Wuthrich
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

As of 4.0.2 we only have elliptic logs for curves defined over the reals (including curves over number fields with a real embedding). We also need the complex case, which can be implemented using the complex AGM. I expect to be adding this during June/July? 2009.

Attachments (3)

trac_6390-celog.patch (29.0 KB) - added by cremona 5 years ago.
Applies to 4.3.4
trac_6390-doc.patch (907 bytes) - added by rlm 5 years ago.
trac_6390.patch (34.3 KB) - added by wuthrich 5 years ago.
exported against 4.3.4, replaces the previous patches

Download all attachments as: .zip

Change History (21)

comment:1 Changed 5 years ago by davidloeffler

  • Component changed from number theory to elliptic curves
  • Owner changed from was to davidloeffler

comment:2 follow-up: Changed 5 years ago by cremona

Update 2009-07-21: I still have this only half done, the gap being proof of a theorem rather than any coding issue, and other responsibilities mean that it is likely to be August rather than July: sorry.

comment:3 Changed 5 years ago by davidloeffler

  • Owner davidloeffler deleted

comment:4 in reply to: ↑ 2 Changed 5 years ago by cremona

  • Report Upstream set to N/A

Replying to cremona:

Update 2009-07-21: I still have this only half done, the gap being proof of a theorem rather than any coding issue, and other responsibilities mean that it is likely to be August rather than July: sorry.

March 2010: it was clearly a mistake to put in a time estimate. We now have a preprint explaining all the relevant theory:

  1. E. Cremona and T. Thongjunthug, "On computing complex elliptic logarithms" (provisional title)

which I am now going to implement i nSage (my coauthor has already implemented it in Magma).

Changed 5 years ago by cremona

Applies to 4.3.4

comment:5 Changed 5 years ago by cremona

  • Authors set to John Cremona
  • Cc robertwb rlm added
  • Owner set to cremona

The patch implements complex elliptic logs as promised, and makes a few minor improvements to the periods & elliptic log code generally.

The new code works fine for real embeddings too, and is almost as fast: for the database curves up to conductor 1000 (and with the optional database installed so that all generators are pre-installed) the new code takes 183 seconds to find all logs of all generators (for the optimal curves) while the old code takes 154s. The new code is also rather simpler. I have left in the old code. Reviewers wishing to test this can do so by switching lines 1243 and 1244 of period_lattice.py: doctests almost all succeed, with a tiny amount of fuzz in some elliptic exponential computations.

I am CC'ing rlm since after installing the optional database of curves (and generators) and testing all of sage/schemes/elliptic_curves, I found that there were some failures in heegner.py, mainly caused by E.gens() sometimes now producing different generators. I fixed almost all of these (since I think that as a matter of principle these doctests should not be dependent on the database not being installed!) but there are two I cannot fix (lines 1409 and 1415 of heegner.py) and I am hoping that Robert M will be able to.

comment:6 Changed 5 years ago by cremona

  • Status changed from new to needs_review

Changed 5 years ago by rlm

comment:7 Changed 5 years ago by rlm

Replying to cremona:

I am CC'ing rlm since after installing the optional database of curves (and generators) and testing all of sage/schemes/elliptic_curves, I found that there were some failures in heegner.py, mainly caused by E.gens() sometimes now producing different generators. I fixed almost all of these (since I think that as a matter of principle these doctests should not be dependent on the database not being installed!) but there are two I cannot fix (lines 1409 and 1415 of heegner.py) and I am hoping that Robert M will be able to.

The following change fixes this, but I can't vouch for its advisability.

--- a/sage/schemes/elliptic_curves/heegner.py	Sat Mar 20 15:52:55 2010 +0000
+++ b/sage/schemes/elliptic_curves/heegner.py	Tue Mar 23 08:39:11 2010 -0700
@@ -4165,7 +4165,7 @@
         # etc" mentioned in Watkins' article... which involves local
         # heights.
         E = self.curve()  # over Q
-        v = sum([list(n*w) for w in E.gens()] + [list(w) for w in E.torsion_points()], [])
+        v = sum([list(n*w) for w in E.gens(use_database=False)] + [list(w) for w in E.torsion_points()], [])
         # note -- we do not claim to prove anything, so making up a factor of 100 is fine.
         max_denominator = 100*max([z.denominator() for z in v])
         try:

When testing on my laptop, I came across another doctest error, and I've included a patch for it.

comment:8 Changed 5 years ago by cremona

Thanks, Robert. With luck soem else will referee the main part of the patch, but I'm in no great hurry as I'll be on holiday for a week from tomorrow!

comment:9 Changed 5 years ago by wuthrich

  • Reviewers set to Chris Wuthrich
  • Status changed from needs_review to needs_work

I wanted to review it, then I noticed from a problem in the documentation that the first patch has many tabulators in it. Unfortunately, I can not just replace all tabs by 4 spaces in the patch as then it makes a mess out of the code. So I guess that John can do the replacement faster than me.

(Most editors allow the setting that all tabulators are replaces by 4 spaces automatically, this would avoid these problems automatically.)

It is a shame that the tabs are not visible here.

Changed 5 years ago by wuthrich

exported against 4.3.4, replaces the previous patches

comment:10 Changed 5 years ago by wuthrich

I uploaded a new patch that incorporates the previous two changes, switches the tabs to spaces and also solves the two remaining doctest problems in heegner.py (using random and only testing the squares, admittedly ugly), and it fixes a problem in the documentation (a missing ::).

I start testing now. Unless the author claims that I made an error in the indentation of the new patch (when removing the tabs), I will give it a positive review after the test.

comment:11 Changed 5 years ago by wuthrich

All tests passed. I wish to give a positive review, but the button for it has disappeared ??

comment:12 Changed 5 years ago by wuthrich

  • Status changed from needs_work to needs_review

comment:13 Changed 5 years ago by wuthrich

  • Status changed from needs_review to positive_review

Here we go !!!

comment:14 Changed 5 years ago by cremona

Many thanks, Chris, and sorry for not responding earlier but I was on holiday for a few days.

Sorry too for the tab/space issue. I just don't see to be able to set up emacs correctly on all the machines I use... but I'll try not to do it again.

comment:15 Changed 5 years ago by jhpalmieri

  • Merged in set to sage-4.4.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

Merged trac_6390.patch in 4.4.alpha0.

comment:16 Changed 3 years ago by robertwb

When #11761 gets approved, we can move using # distutils: language = c++ which is understood by Cython and can be used to specify any Extension options.

comment:18 Changed 3 years ago by robertwb

(Argh--too many trac tabs open. Wrong ticket. Think before hitting submit...)

Note: See TracTickets for help on using tickets.