implement elliptic-curve point addition for general rings #33228

yyyyx4 · 2022-01-25T05:42:03Z

Currently, point addition for elliptic curves is only defined in EllipticCurvePoint_field and its children. This patch implements point arithmetic for EllipticCurvePoint, while also keeping the specialized (faster) implementation for fields. 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.

Depends on #34417
Depends on #34463

CC: @JohnCremona @roed314 @edgarcosta @alexjbest

Component: elliptic curves

Author: Lorenz Panny

Branch/Commit: public/generalize_elliptic_curve_point_addition_to_rings @ 940f8a2

Issue created by migration from https://trac.sagemath.org/ticket/33228

The text was updated successfully, but these errors were encountered:

fchapoton · 2022-01-25T19:07:30Z

comment:1

some failing doctests, see patchbot report

sagetrac-git · 2022-01-26T05:24:02Z

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`

sagetrac-git · 2022-01-26T05:24:02Z

Changed commit from 4d67190 to 915b725

fchapoton · 2022-02-02T20:40:54Z

comment:4

Elliptic gurus, please say your word on these changes!

JohnCremona · 2022-02-02T20:50:19Z

comment:5

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.

edgarcosta · 2022-02-02T21:36:48Z

comment:7

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

yyyyx4 · 2022-02-03T04:22:14Z

comment:8

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 @JohnCremona:

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! :-)

JohnCremona · 2022-02-03T10:21:54Z

comment:9

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

JohnCremona · 2022-02-03T10:52:24Z

comment:10

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?

yyyyx4 · 2022-08-24T09:24:13Z

Dependencies: #34417

yyyyx4 · 2022-08-24T09:24:13Z

Changed commit from 915b725 to 2b4509e

yyyyx4 · 2022-08-24T09:24:13Z

comment:13

I've included Alex' version of the Bosma-Lenstra formulas to compute point additions over fairly general rings. One thing I'm not quite sure about is how to combine the results of the two formulas in case neither gives a valid projective point — in the current code, this is done by brute-forcing random linear combinations, but there must be a more algebraic way. (It's fairly straightforward for Bézout rings.)

New commits:

`020c9e5`	`move elliptic-curve point addition to superclass`
`52c622b`	`make (P in E) return False when P is defined over an extension field`
`c73444e`	`undo ancient hack for elliptic-curve points modulo composites`
`45ba391`	`update documentation to reflect this change`
`d0d6100`	`implement Bosma-Lenstra formulas (corrected version from Best)`
`f890d6c`	`add random test for point addition in ℤ/n`
`8b56f25`	`undo ancient hack for ECM examples`
`2b4509e`	`add changes to history`

yyyyx4 · 2022-08-24T09:24:13Z

Changed branch from public/move_elliptic_curve_point_addition_to_parent to public/generalize_elliptic_curve_point_addition_to_rings

roed314 · 2022-08-24T17:21:49Z

comment:14

Looks pretty good to me. Here are some questions/suggestions.

Are there other cases where we can use simpler formulas? For example, over a Euclidean domain you could use the field-formula and then clear denominators. And over Z/N you could try to use the field-formula and only fall back on the more general one when you hit a zero divisor. I haven't done any profiling, but the general formula looks pretty slow, so this change will probably slow down any toy ECM implementations out there.
Relatedly, I'm not sure exactly how to handle deprecation warnings for this change. Making arithmetic work when it didn't before is great, but this is one of the few cases where people may be relying on having a ZeroDivisionError rather than getting an actual point out. I know that my ECM demos would break with this change. Perhaps one way forward would be to print a deprecation warning whenever someone does arithmetic on an elliptic curve over Z/N with a pointer to this ticket so that at least they understand what has changed when their code just runs forever (as it might if they just do things until catching a ZeroDivisionError).

I'll also give John Cremona a chance to take a look at this, since he was commenting on an earlier version.

yyyyx4 · 2022-08-25T04:00:25Z

comment:15

Thanks for your comments.

Indeed, some quick experiments suggest a ≈10× slowdown. Perhaps we should try to adapt the standard formulas to quotients of Euclidean domains? This would cover both of your examples, and more.
Getting the ZeroDivisionError back should be achievable by explicitly constructing an EllipticCurvePoint_field(E, ...) rather than using E.point(...). The standard ZeroDivisionError error message is slightly less well-adjusted to the ECM use case, but it does contain the relevant non-unit so you can still easily factor the modulus from the exception string. Is this what we should recommend to users in a warning?

JohnCremona · 2022-08-25T08:53:02Z

comment:16

Since I was asked, I'll comment. Two points:

I myself have no need to ever try to define elliptic curves over general rings. The reason I put in the hack which pretended that elliptic curves over \ZZ/N were elliptic curves over fields, was to enable a simple-minded ECM to work for teaching purposes, making sure that the error message produced, when zero-divisors were encountered, displayed the nontrivial factor of N. And I did this after a complaint by Ken Ribet (eminent mathematician and AMS President 2017-2018) that the Sage code he used to teach exactly this to undergraduates at Berkeley no longer worked. It's a very good thing to have such people promoting Sage.

I think it could work to have some parameter to the elliptic curve constructor like assume_base_ring_is_field, which by default is False, but which could be set to True for this precise purpose -- with some doctests to show exactly how this could be used for such a simple ECM implementation. In (just about) all other situations, the default would do the mathematically correct thing.

Secondly, it is unacceptable to have a 10* slowdown for point operations over fields! The vast majority of point operations would be over fields. Surely the thing to do would be to put in the generic stuff introduced here for EllipticCurvePoint, while keeping the old field-only code (or whatever is fastest over fields) for the class EllipticCurvePoint_field?

yyyyx4 · 2022-08-25T11:01:41Z

comment:17

Replying to @JohnCremona:

Surely the thing to do would be to put in the generic stuff introduced here for EllipticCurvePoint, while keeping the old field-only code (or whatever is fastest over fields) for the class EllipticCurvePoint_field?

Of course; the patch does it like this already. The 10× difference is between the field-specific formulas and the general formulas, not between before and after. The only case which is now slower (but more correct!) than before is ℤ/n for composite n.

JohnCremona · 2022-08-25T11:20:09Z

comment:18

Replying to @yyyyx4:

Replying to @JohnCremona:

Surely the thing to do would be to put in the generic stuff introduced here for EllipticCurvePoint, while keeping the old field-only code (or whatever is fastest over fields) for the class EllipticCurvePoint_field?

Of course; the patch does it like this already. The 10× difference is between the field-specific formulas and the general formulas, not between before and after. The only case which is now slower (but more correct!) than before is ℤ/n for composite n.

Thanks for clarifying (and I know that I could also have looked at the code, but it is good to have this stated explicitly on the ticket).

This deals with my second point, at least!

roed314 · 2022-08-29T17:08:41Z

comment:19

Two plugin issues:

There's a pyflakes error: src/sage/schemes/elliptic_curves/ell_generic.py:56:1 'sage.rings.abc' imported but unused
The add function in addition_formulas_ring.py needs doctests.

There's also a doctest failure:

File "src/sage/schemes/elliptic_curves/ell_point.py", line 214, in sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint._add_
Failed example:
    for d in N.divisors():
        if d > 1:
            assert R.change_ring(Zmod(d)) == P.change_ring(Zmod(d)) + Q.change_ring(Zmod(d))
Exception raised:
    Traceback (most recent call last):
      File "/home/sage-patchbot/sage/src/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/sage-patchbot/sage/src/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint._add_[14]>", line 3, in <module>
        assert R.change_ring(Zmod(d)) == P.change_ring(Zmod(d)) + Q.change_ring(Zmod(d))
      File "/home/sage-patchbot/sage/src/sage/schemes/generic/morphism.py", line 1977, in change_ring
        return S.point(Q, check=check)
      File "/home/sage-patchbot/sage/src/sage/schemes/projective/projective_subscheme.py", line 122, in point
        return self._point(self.point_homset(), v, check=check)
      File "/home/sage-patchbot/sage/src/sage/schemes/projective/projective_point.py", line 203, in __init__
        X.extended_codomain()._check_satisfies_equations(v)
      File "/home/sage-patchbot/sage/src/sage/schemes/generic/algebraic_scheme.py", line 984, in _check_satisfies_equations
        raise TypeError("Coordinates %s do not define a point on %s"%(coords,self))
    TypeError: Coordinates [60, 58, 13] do not define a point on Elliptic Curve defined by y^2 + 40*x*y + 12*y = x^3 + 57*x^2 + 76*x + 55 over Ring of integers modulo 87

roed314 · 2022-08-29T17:11:50Z

comment:20

Adapting the standard formulas to quotients of Euclidean domains seems reasonable.

sagetrac-git · 2022-09-13T09:55:36Z

Changed commit from 2b4509e to 940f8a2

sagetrac-git · 2022-09-13T09:55:36Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

`ca4ac6b`	`move elliptic-curve point addition to superclass`
`d4a0a40`	`make (P in E) return False when P is defined over an extension field`
`327a902`	`undo ancient hack for elliptic-curve points modulo composites`
`38a8756`	`update documentation to reflect this change`
`0f73f57`	`implement Bosma-Lenstra formulas (corrected version from Best)`
`5fc88be`	`add random test for point addition in ℤ/n`
`5955a1e`	`undo ancient hack for ECM examples`
`9701928`	`add changes to history`
`22a9a7f`	`add doctest for generic addition formulas`
`940f8a2`	`faster isogeny formulas for quotients of Euclidean domains`

yyyyx4 · 2022-09-13T10:03:38Z

comment:22

I had a shot at adapting the standard formulas to quotients of Euclidean domains.

Performance comparison for a single point addition modulo 2^127-1:

field-specific code:  625 loops, best of 3: 21.8 μs per loop
Euclidean quotients:  625 loops, best of 3: 37.8 μs per loop
generic formulas:     625 loops, best of 3: 123 μs per loop

I think we don't need to add another hack to the EllipticCurve constructor for this because Zmod already has one that does the trick:

sage: R = Zmod(13 * 17, is_field=True)
sage: E = EllipticCurve(R, [1,0])
sage: P = E.lift_x(4)
sage: 123*P
Traceback (most recent call last):
...
ZeroDivisionError: inverse of Mod(34, 221) does not exist

Replying to David Roe:

There's also a doctest failure:

    TypeError: Coordinates [60, 58, 13] do not define a point on Elliptic Curve defined by y^2 + 40*x*y + 12*y = x^3 + 57*x^2 + 76*x + 55 over Ring of integers modulo 87

That's #34417.

yyyyx4 · 2022-09-13T10:03:38Z

Changed dependencies from #34417 to #34417, #34463

tornaria · 2022-10-21T13:16:46Z

comment:23

Replying to Lorenz Panny:

I think we don't need to add another hack to the EllipticCurve constructor for this because Zmod already has one that does the trick:
sage: R = Zmod(13 * 17, is_field=True)
sage: E = EllipticCurve(R, [1,0])
sage: P = E.lift_x(4)
sage: 123*P
Traceback (most recent call last):
...
ZeroDivisionError: inverse of Mod(34, 221) does not exist

That's nice, however:

sage: E = EllipticCurve(Zmod(35, is_field=True), [5,1])
sage: E.base_field()
...
AttributeError: 'EllipticCurve_generic_with_category' object has no attribute 'base_field'

in fact

sage: parent(E)
<class 'sage.schemes.elliptic_curves.ell_generic.EllipticCurve_generic_with_category'>

so it would still need "the hack" (broken as of 9.6 and fixed in #34681).
Compare to

sage: parent(EllipticCurve(Zmod(7, is_field=True), [5,1]))
<class 'sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field_with_category'>

Actually:

sage: Zmod(35, is_field=True).is_field()
False

so, what's the effect of is_field=True?

tornaria · 2022-10-21T13:37:09Z

comment:24

Also, this is potentially dangerous:

sage: Zmod(35, is_field=True) is Zmod(35, is_field=False)
True

This means the example above works after clearing the cache:

sage: Zmod._cache.clear()
sage: E = EllipticCurve(Zmod(35, is_field=True), [5,1])
sage: E.base_field()
Ring of integers modulo 35

But then one might get a scary error message

sage: Zmod(35).is_field(proof=True)
...
ValueError: THIS SAGE SESSION MIGHT BE SERIOUSLY COMPROMISED!
The order 35 is not prime, but this ring has been put
into the category of fields. This may already have consequences
in other parts of Sage. Either it was a mistake of the user,
or a probabilistic primality test has failed.
In the latter case, please inform the developers.

…CurvePoint The method `EllipticCurve_generic.__contains__()` checks for inheritance from `EllipticCurvePoint`; however, the other classes for points on elliptic curves do not inherit from this class. This pull request fixes this. Note that there is some overlap with sagemath#33228. This change makes `P in E` much faster: - Over **Q**: ```python E = EllipticCurve('37a1') P = E((0, -1)) %timeit P in E ``` Before: `35.3 µs ± 186 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)` After: `324 ns ± 0.535 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)` - Over a finite field: ```python F.<a> = FiniteField((23, 2), modulus='random') E = EllipticCurve_from_j(F.random_element()) P = E.random_point() %timeit P in E ``` Before: `36.4 µs ± 542 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)` After: `333 ns ± 5.03 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)` URL: sagemath#37415 Reported by: Peter Bruin Reviewer(s): Kwankyu Lee, Peter Bruin

… rings Here we revive the effort from sagemath#33228 to implement point-addition formulas on elliptic curves over (more) general rings. This resolves sagemath#33228. URL: sagemath#39036 Reported by: Lorenz Panny Reviewer(s): Lorenz Panny, Vincent Macri

yyyyx4 added this to the sage-9.6 milestone Jan 25, 2022

yyyyx4 added c: elliptic curves labels Jan 25, 2022

yyyyx4 added the s: needs review label Jan 27, 2022

yyyyx4 added s: needs work and removed s: needs review labels Mar 13, 2022

mkoeppe modified the milestones: sage-9.6, sage-9.7 Apr 17, 2022

This comment has been minimized.

Sign in to view

yyyyx4 added p: major / 3 and removed p: minor / 4 labels Aug 24, 2022

yyyyx4 modified the milestones: sage-9.7, sage-9.8 Aug 24, 2022

yyyyx4 changed the title ~~move elliptic-curve point addition from EllipticCurvePoint_field to EllipticCurvePoint~~ implement elliptic-curve point addition for general rings Aug 24, 2022

yyyyx4 added s: needs review and removed s: needs work labels Aug 24, 2022

yyyyx4 added s: needs work and removed s: needs review labels Nov 29, 2022

mkoeppe removed this from the sage-9.8 milestone Jan 29, 2023

pjbruin mentioned this issue Feb 21, 2024

make EllipticCurvePoint_field inherit from EllipticCurvePoint #37415

Merged

yyyyx4 mentioned this issue Nov 25, 2024

implement elliptic-curve point addition for general rings #39036

Merged

vbraun closed this as completed in 2df4906 Dec 15, 2024

github-actions bot removed the s: needs work label Dec 15, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

implement elliptic-curve point addition for general rings #33228

implement elliptic-curve point addition for general rings #33228

yyyyx4 commented Jan 25, 2022

fchapoton commented Jan 25, 2022

sagetrac-git mannequin commented Jan 26, 2022

sagetrac-git mannequin commented Jan 26, 2022

fchapoton commented Feb 2, 2022

JohnCremona commented Feb 2, 2022

edgarcosta commented Feb 2, 2022

yyyyx4 commented Feb 3, 2022

JohnCremona commented Feb 3, 2022

JohnCremona commented Feb 3, 2022

yyyyx4 commented Aug 24, 2022

This comment has been minimized.

yyyyx4 commented Aug 24, 2022

yyyyx4 commented Aug 24, 2022

yyyyx4 commented Aug 24, 2022

roed314 commented Aug 24, 2022

yyyyx4 commented Aug 25, 2022

JohnCremona commented Aug 25, 2022

yyyyx4 commented Aug 25, 2022

JohnCremona commented Aug 25, 2022

roed314 commented Aug 29, 2022

roed314 commented Aug 29, 2022

sagetrac-git mannequin commented Sep 13, 2022

sagetrac-git mannequin commented Sep 13, 2022

yyyyx4 commented Sep 13, 2022

yyyyx4 commented Sep 13, 2022

tornaria commented Oct 21, 2022

tornaria commented Oct 21, 2022

implement elliptic-curve point addition for general rings #33228

implement elliptic-curve point addition for general rings #33228

Comments

yyyyx4 commented Jan 25, 2022

fchapoton commented Jan 25, 2022

sagetrac-git mannequin commented Jan 26, 2022

sagetrac-git mannequin commented Jan 26, 2022

fchapoton commented Feb 2, 2022

JohnCremona commented Feb 2, 2022

edgarcosta commented Feb 2, 2022

yyyyx4 commented Feb 3, 2022

JohnCremona commented Feb 3, 2022

JohnCremona commented Feb 3, 2022

yyyyx4 commented Aug 24, 2022

This comment has been minimized.

yyyyx4 commented Aug 24, 2022

yyyyx4 commented Aug 24, 2022

yyyyx4 commented Aug 24, 2022

roed314 commented Aug 24, 2022

yyyyx4 commented Aug 25, 2022

JohnCremona commented Aug 25, 2022

yyyyx4 commented Aug 25, 2022

JohnCremona commented Aug 25, 2022

roed314 commented Aug 29, 2022

roed314 commented Aug 29, 2022

sagetrac-git mannequin commented Sep 13, 2022

sagetrac-git mannequin commented Sep 13, 2022

yyyyx4 commented Sep 13, 2022

yyyyx4 commented Sep 13, 2022

tornaria commented Oct 21, 2022

tornaria commented Oct 21, 2022