Opened 13 years ago

Closed 13 years ago

Last modified 13 years ago

#6193 closed defect (fixed)

[with patch, positive review] implement elliptic logarithm

Reported by: robertwb Owned by: was
Priority: major Milestone: sage-4.0.2
Component: number theory Keywords:
Cc: cremona Merged in: 4.0.2.alpha0
Authors: John Cremona Reviewers: Robert Bradshaw
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Depends on #6021.

Attachments (2)

cperiods-2.patch (25.8 KB) - added by robertwb 13 years ago.
6193-ell-log-referee.patch (1.5 KB) - added by robertwb 13 years ago.

Download all attachments as: .zip

Change History (10)

Changed 13 years ago by robertwb

comment:1 Changed 13 years ago by robertwb

Comment from previous ticket:

Yet another patch, to be applied after the previous ones.

  1. Better handling of precision. The algebraic quantities needed for both periods and elliptic logs are now cached. Then period and log computations just have to coerce into the appropriate Real/ComplexField?, and do the transcendental part via agm.
  2. Elliptic log implementation now moved into period lattice class (except for the algorithm="pari" case which is unchanged). Also available via call i.e. as L.elliptic_logarithm(P) or just L(P). Uses an extended agm function which has been separated off.
  3. Earlier precision issues with a difficult example are fixed; we get all the same digits as pari, and faster. To do this we compute the extended AGM in double the required precision and then revert to desired precision at the end. (I tried adding 10 or 20 bits of precision, but that nasty example (18074g1) needs more).

The only remaining thing is to implement elliptic logs for non-real lattices. This is not hard to do but harder to justify! Before I do that, to test it I need to implement the reverse of the elliptic log -- using Weierstrass P-functions and derivative to go from z mod L back to P(x,y) with complex coords in general.

comment:2 follow-up: Changed 13 years ago by robertwb

The code looks good after my first reading.

  • I assume by on_egg you're implying the non-identity component of an elliptic curve over R?
  • Where does the terminology ei come from for the x-coordinates of the 2-torsion? (I may just not be familiar with the notation, if so, just let me know.)
  • What assurance is there that extended_agm_iteration will terminate in the presence of numerical noise? (I suppose if delta is around machine epsilon, then (1+delta).sqrt() should be identically 1. Is that enough?
  • It would be good to have an example demonstrating that the elliptic log is actually the inverse of the standard Weierstrass isomorphism (at least using Pari's version so far)

I am still building a 4.0 so I haven't actually applied/tested it, but will when that's done building.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 13 years ago by cremona

Replying to robertwb:

The code looks good after my first reading.

  • I assume by on_egg you're implying the non-identity component of an elliptic curve over R?

That is right. Some people call this (the compact component in R^2) the "egg". Perhaps a comment should be included to explain this, but the name has the advantage of being short.

  • Where does the terminology ei come from for the x-coordinates of the 2-torsion? (I may just not be familiar with the notation, if so, just let me know.)

I thought it was standard to call the real roots e1, e2, e3 (i.e. these are the x-coords of the points of order 2). Less standard is the ordering (for curves over R): when they are all real then either e1<e2<e3 or the other way round; and when only one is real, it is e1 for some people and e3 for others. Hence I do make this explicit.

  • What assurance is there that extended_agm_iteration will terminate in the presence of numerical noise? (I suppose if delta is around machine epsilon, then (1+delta).sqrt() should be identically 1. Is that enough?

That does worry me. I am hopeless at numerical analysis; I put this simple test in while testing and it seemed to work fine; otherwise we should be testing that delta is small enough that 1+delta is exactly 1 within the current precision. (Note that the way this is coded it is already using relative rather than absolute precision, which is good).

  • It would be good to have an example demonstrating that the elliptic log is actually the inverse of the standard Weierstrass isomorphism (at least using Pari's version so far)

Of course; and that is listed in the things I have not done yet.

I am still building a 4.0 so I haven't actually applied/tested it, but will when that's done building.

comment:4 in reply to: ↑ 3 Changed 13 years ago by robertwb

Replying to cremona:

Replying to robertwb:

The code looks good after my first reading.

  • I assume by on_egg you're implying the non-identity component of an elliptic curve over R?

That is right. Some people call this (the compact component in R^2) the "egg". Perhaps a comment should be included to explain this, but the name has the advantage of being short.

I think it's fine, the terminology is very evocative of what it is :)

  • Where does the terminology ei come from for the x-coordinates of the 2-torsion? (I may just not be familiar with the notation, if so, just let me know.)

I thought it was standard to call the real roots e1, e2, e3 (i.e. these are the x-coords of the points of order 2). Less standard is the ordering (for curves over R): when they are all real then either e1<e2<e3 or the other way round; and when only one is real, it is e1 for some people and e3 for others. Hence I do make this explicit.

Oh, of course. I wasn't thinking of the i as an index, now ei makes total sense with the e1, e2, and e3 conventions.

comment:5 Changed 13 years ago by robertwb

  • Summary changed from [with patch, needs review] implement elliptic logarithm to [with patch, positive review] implement elliptic logarithm

There was some numerical noise, I fixed it with this patch. Also, I added a test to see that it does actually invert the Weierstrass P function (though this should be done more cleanly when we have a native and/or better wrapped Weierstrass P.)

Thinking about the agm termination condition, the convergence of agm is quadratic, so delta will be ~1upl < 3upl, so it should not be an issue.

Changed 13 years ago by robertwb

comment:6 Changed 13 years ago by cremona

Thanks. Pity about the ..., but it's the only one. I'm working on getting the ellztopoint (via pari's ellwp) but will put that on another ticket. John

comment:7 Changed 13 years ago by ncalexan

  • Authors set to Robert Bradshaw
  • Merged in set to 4.0.2.alpha0
  • Resolution set to fixed
  • Reviewers set to John Cremona
  • Status changed from new to closed

comment:8 Changed 13 years ago by robertwb

  • Authors changed from Robert Bradshaw to John Cremona
  • Reviewers changed from John Cremona to Robert Bradshaw
Note: See TracTickets for help on using tickets.