Opened 4 months ago
Last modified 6 weeks ago
#33228 needs_work enhancement
move ellipticcurve point addition from EllipticCurvePoint_field to EllipticCurvePoint
Reported by:  lorenz  Owned by:  

Priority:  minor  Milestone:  sage9.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: 
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 ellipticcurve points over ℤ/n that was introduced in #1975.
Change History (12)
comment:1 Changed 4 months ago by
comment:2 Changed 4 months ago by
 Commit changed from 4d67190918a8e1304b32643d9c8d261b815f11cf to 915b72585a0973528a11f65c741df19f189138e8
Branch pushed to git repo; I updated commit sha1. New commits:
915b725  make (P in E) return False when P is defined over an extension field

comment:3 Changed 4 months ago by
 Status changed from new to needs_review
comment:4 Changed 4 months ago by
 Cc cremona roed edgarcosta added
Elliptic gurus, please say your word on these changes!
comment:5 Changed 4 months ago by
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
 Cc alexjbest added
comment:7 Changed 4 months ago by
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
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 nonunits 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
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 zcoordinate will always be 1 for nonzero points over nonfields? I will keep reading...
comment:10 Changed 4 months ago by
Another simplification: after the preceding check, if x1==x2 then also y1==y2 (unless you do not want me to assume that quadratics over nonfields 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 = y1y2 den = x1x2 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
 Status changed from needs_review to needs_work
comment:12 Changed 6 weeks ago by
 Milestone changed from sage9.6 to sage9.7
some failing doctests, see patchbot report