Opened 4 months ago

Last modified 6 weeks ago

#33228 needs_work enhancement

move elliptic-curve point addition from EllipticCurvePoint_field to EllipticCurvePoint

Reported by: lorenz Owned by:
Priority: minor Milestone: sage-9.7
Component: elliptic curves Keywords:
Cc: cremona, roed, edgarcosta, alexjbest Merged in:
Authors: Lorenz Panny Reviewers:
Report Upstream: N/A Work issues:
Branch: public/move_elliptic_curve_point_addition_to_parent (Commits, GitHub, GitLab) Commit: 915b72585a0973528a11f65c741df19f189138e8
Dependencies: Stopgaps:

Status badges

Description

Currently, point addition for elliptic curves is only defined in EllipticCurvePoint_field and its children. This patch moves it up to EllipticCurvePoint. This is useful for symbolic computations, such as the ones that show up in a basic version of Schoof's algorithm (where we compute in a polynomial ring modulo the ideal generated by a division polynomial and the curve equation).

Another implication of this is that we can remove part of the "temporary" hack for elliptic-curve points over ℤ/n that was introduced in #1975.

Change History (12)

comment:1 Changed 4 months ago by chapoton

some failing doctests, see patchbot report

comment:2 Changed 4 months ago by git

  • Commit changed from 4d67190918a8e1304b32643d9c8d261b815f11cf to 915b72585a0973528a11f65c741df19f189138e8

Branch pushed to git repo; I updated commit sha1. New commits:

915b725make (P in E) return False when P is defined over an extension field

comment:3 Changed 4 months ago by lorenz

  • Status changed from new to needs_review

comment:4 Changed 4 months ago by chapoton

  • Cc cremona roed edgarcosta added

Elliptic gurus, please say your word on these changes!

comment:5 Changed 4 months ago by cremona

This is interesting -- as well as being the author of the "temporary hack", I also came across this issue when trying to implement Schoof's algorithm from basics wih a student. I'll take a look.

comment:6 Changed 4 months ago by edgarcosta

  • Cc alexjbest added

comment:7 Changed 4 months ago by edgarcosta

In case you are interested, Alex Best corrected some typos Bosma–Lenstra paper formulas for addition law for elliptic curves over a general ring, see Appendix A of https://open.bu.edu/bitstream/handle/2144/43150/Best_bu_0017E_16371.pdf

I bet he must have them implemented somewhere...

comment:8 Changed 4 months ago by lorenz

Replying to edgarcosta:

In case you are interested, Alex Best corrected some typos Bosma–Lenstra paper formulas for addition law for elliptic curves over a general ring, see Appendix A of https://open.bu.edu/bitstream/handle/2144/43150/Best_bu_0017E_16371.pdf

Interesting, thanks! Generalizing the formulas to not fail when non-units are encountered was a next step on my list (and the original motivation to move + up in the class hierarchy). I'll try this out as soon as I find time.

Replying to cremona:

This is interesting -- as well as being the author of the "temporary hack", I also came across this issue when trying to implement Schoof's algorithm from basics wih a student. I'll take a look.

Sadly, this change alone does not yet allow implementing a straightforward Schoof (e.g., because the current addition formulas attempt to divide by zero divisors rather frequently in that context). But we'll get there! :-)

comment:9 Changed 4 months ago by cremona

I reealise that it may be annoying to make comments about chunks of code which were just copied over but I would change the lines

        x1, y1 = self[0], self[1]
        x2, y2 = right[0], right[1]
        if x1 == x2 and y1 == -y2 - a1*x2 - a3:

to

        x1, y1, _ = self
        x2, y2, _ = right
        if x1 == x2 and y1 != y2:

where the first two are just python while the 3rd is simpler and mathematically equivalent.

However, are you sure that the z-coordinate will always be 1 for nonzero points over non-fields? I will keep reading...

comment:10 Changed 4 months ago by cremona

Another simplification: after the preceding check, if x1==x2 then also y1==y2 (unless you do not want me to assume that quadratics over non-fields have no more than 2 roots, in which case my previous suggestion may not be valid either):

    if x1==x2:
       num = 3*x1*x1 + 2*a2*x1 + a4 - a1*y1
       den = 2*y1 + a1*x1 + a3
    else:
       num = y1-y2
       den = x1-x2
   try:
      m = num/den
   except ZeroDivisionError:
              R = E.base_ring()
              if R.is_finite():
                  N = R.characteristic()
                  N1 = N.gcd(Integer(den))
                  N2 = N//N1
                  raise ZeroDivisionError("Inverse of %s does not exist (characteristic = %s = %s*%s)" % (den, N, N1, N2))
              else:
                   raise ZeroDivisionError("Inverse of %s does not exist" % (den))

Apart from these (which I know don't have much to do with your chenges) I think this looks good. Can you add at least one test to show that what used to work (over Z/NZ say) still does, and also something which used not to work but now does?

comment:11 Changed 3 months ago by lorenz

  • Status changed from needs_review to needs_work

comment:12 Changed 6 weeks ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.