On May 14, Daniel Loughran wrote:
Ha that is quite a funny mistake. The outputs of my experiments start to make more sense now.Does this also explain the error I found when working modulo 16? Just this was slightly different in nature. On Thursday, 14 May 2020 16:17:59 UTC+1, Reimundo Heluani wrote: On May 14, Daniel Loughran wrote: >Hello. I think that I may have found a bug involving elliptic curves modulo >powers of primes. I have attached the working jupyter notebook, but my code and >results are also below. > >In my code I have an elliptic curve E over Q with good reduction at 2 and the >point P = (2:-3:8) (homogeneous coordinates). > >It is clear that the reduction modulo 4 of this point in projective space is >(2:1:0). > >However, sage is telling me that when I reduce the curve modulo 4 then ask what >point P reduces to, I get the identity element (0:1:0). > >My guess is that sage does something like put this point into the form (1/ 4:-3/ >8:1), then notices that 4 divides the denominator of the x-coordinate so just >kills it. But really it should be clearing denominators before it tries to >reduce modulo 4. > Ok the issue is in ell_generic.__call__() that calls _reduce_point with characteristic p=4 which is not a prime. This function in turn creates the curve E' = E.change_ring(GF(4)) instead of your E4 = E.change_ring(Integers(4)) And then returns the point E'(P) which indeed is the identity.
Looking at the documentation for EllipticCuve? it says the following
...
"EllipticCurve(R, [a1,a2,a3,a4,a6])": Create the elliptic curve
over R with given a-invariants. Here R can be an arbitrary
commutative ring, although most functionality is only implemented
over fields.
...
So this may not be a bug per-se. But anyway, if you bypass the call to
_reduce_point and call directly ProjectivePlaneCurve.__call__ as in the
attached diff, there is still an issue: the point (2:1:0) will not be
recognized as a point in E4 because the test when z=0 considers that the point
is over a field, it tests that x = 0 instead of x**3 = 0.
The attached diff would be a very temporary workaround to this issue. With it
applied you'd get the right reduction for both integers or rationals in the
definition of E:
sage: E = EllipticCurve(ZZ,[0,0,1,-1,0]);E4 = E.change_ring(Integers(4)); P = E(2,-3,8); P (2 : -3 : 8) sage: E4(P) (2 : 1 : 0) sage: E = EllipticCurve([0,0,1,-1,0]);E4 = E.change_ring(Integers(4)); P = E(2,-3,8); P (1/4 : -3/8 : 1) sage: E4(P) (2 : 1 : 0) However this is still wrong because sage: E = EllipticCurve(ZZ,[0,0,1,-1,0]);E4 = E.change_ring(Integers(4)); P = E(2,-3,8); P (2 : -3 : 8) sage: isinstance(P,ell_point.EllipticCurvePoint_field) False sage: isinstance(E4(P),ell_point.EllipticCurvePoint_field) TruePerhaps a trac issue should be open. I'll see if the check for x^3 can be moved somewhere else and may open it
R.
R > >There is another related bug: if I try to instead reduce this point modulo 16, >then I just get the error "inverse of Mod(4, 16) does not exist". I guess this >is a similar problem to the above. > > >----------------------------------------------------------- ------------------------------------------------------------------- >[ ] > >E=EllipticCurve([0, 0, 1, -1, 0]); E > >Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field > > >[ ] > >P=E(2,-3,8); P > >(1/4 : -3/8 : 1) > > >[ ] > >E4=E.change_ring(Integers(4)); E4 > >Elliptic Curve defined by y^2 + y = x^3 + 3*x over Ring of integers modulo 4 > > >[ ] > >E4(P) > >(0 : 1 : 0) > > >[ ] > >P2.<X,Y,Z> = ProjectiveSpace(Integers(4),2); P2 > >Projective Space of dimension 2 over Ring of integers modulo 4 > > >[ ] > >P2(2,-3,8) > >(2 : 1 : 0) > > >[ ] > >P2(0,1,0) > >(0 : 1 : 0) > > >[ ] > >P2(2,-3,8)==P2(0,1,0) > >False > > >[ ] > >E16=E.change_ring(Integers(16)); E16 > >Elliptic Curve defined by y^2 + y = x^3 + 15*x over Ring of integers modulo 16 > > >[ ] > >E16(P) >ZeroDivisionError: inverse of Mod(4, 16) does not exist > >-- >You received this message because you are subscribed to the Google Groups >"sage-devel" group. >To unsubscribe from this group and stop receiving emails from it, send an email >to [11][1]sage-...@googlegroups.com. >To view this discussion on the web visit [12][2]https://groups.google.com/ d/msgid/ >sage-devel/f2900af4-6aad-4450-9e12-6f1ec95596f8%[3]40googlegroups.com. > >References: > >[11] mailto:[4]sage-...@googlegroups.com >[12] [5]https://groups.google.com/d/msgid/sage-devel/f2900af4- 6aad-4450-9e12-6f1ec95596f8%40googlegroups.com?utm_medium=email&utm_source= footer -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to [6]sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit [7]https://groups.google.com/d/msgid/ sage-devel/e174eb2c-f21b-402d-b0f0-fac380916650%40googlegroups.com. References: [1] javascript: [2] https://groups.google.com/d/msgid/ [3] http://40googlegroups.com/ [4] javascript: [5] https://groups.google.com/d/msgid/sage-devel/f2900af4-6aad-4450-9e12-6f1ec95596f8%40googlegroups.com?utm_medium=email&utm_source=footer [6] mailto:sage-devel+unsubscr...@googlegroups.com [7] https://groups.google.com/d/msgid/sage-devel/e174eb2c-f21b-402d-b0f0-fac380916650%40googlegroups.com?utm_medium=email&utm_source=footer
-- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/20200514165730.GA197854%40vertex.
[33mdiff --git a/src/sage/schemes/elliptic_curves/ell_generic.py
b/src/sage/schemes/elliptic_curves/ell_generic.py[m
[33mindex 730cb2bce9..e94832250e 100644[m
[33m--- a/src/sage/schemes/elliptic_curves/ell_generic.py[m
[33m+++ b/src/sage/schemes/elliptic_curves/ell_generic.py[m
[36m@@ -543,66 +543,14 @@[m [mclass EllipticCurve_generic(WithEqualityById,
plane_curve.ProjectivePlaneCurve):[m
characteristic = self.base_ring().characteristic()[m
if characteristic != 0 and isinstance(args[0][0], rings.Rational)
and isinstance(args[0][1], rings.Rational):[m
if rings.mod(args[0][0].denominator(),characteristic) == 0 or
rings.mod(args[0][1].denominator(),characteristic) == 0:[m
[31m- return self._reduce_point(args[0], characteristic)[m
[32m+[m[32m x, y = args[0].xy()[m
[32m+[m[32m d = lcm(x.denominator(), y.denominator())[m
[32m+[m[32m args = ([x*d, y*d, d],)[m
[32m+[m
args = tuple(args[0])[m
[m
return plane_curve.ProjectivePlaneCurve.__call__(self, *args,
**kwds)[m
[m
[31m- def _reduce_point(self, R, p):[m
[31m- r"""[m
[31m- Reduces a point R on an elliptic curve to the corresponding point
on[m
[31m- the elliptic curve reduced modulo p.[m
[31m-[m
[31m- Used to coerce points between[m
[31m- curves when p is a factor of the denominator of one of the[m
[31m- coordinates.[m
[31m-[m
[31m- This functionality is used internally in the ``call`` method
for[m
[31m- elliptic curves.[m
[31m-[m
[31m- INPUT:[m
[31m-[m
[31m- - R -- a point on an elliptic curve[m
[31m- - p -- a prime[m
[31m-[m
[31m- OUTPUT:[m
[31m-[m
[31m- S -- the corresponding point of the elliptic curve containing[m
[31m- R, but reduced modulo p[m
[31m-[m
[31m- EXAMPLES:[m
[31m-[m
[31m- Suppose we have a point with large height on a rational elliptic
curve[m
[31m- whose denominator contains a factor of 11::[m
[31m-[m
[31m- sage: E = EllipticCurve([1,-1,0,94,9])[m
[31m- sage: R = E([0,3]) + 5*E([8,31])[m
[31m- sage: factor(R.xy()[0].denominator())[m
[31m- 2^2 * 11^2 * 1457253032371^2[m
[31m-[m
[31m- Since 11 is a factor of the denominator, this point corresponds
to the[m
[31m- point at infinity on the same curve but reduced modulo 11. The
reduce[m
[31m- function tells us this::[m
[31m-[m
[31m- sage: E11 = E.change_ring(GF(11))[m
[31m- sage: S = E11._reduce_point(R, 11)[m
[31m- sage: E11(S)[m
[31m- (0 : 1 : 0)[m
[31m-[m
[31m- The 0 point reduces as expected::[m
[31m-[m
[31m- sage: E11._reduce_point(E(0), 11)[m
[31m- (0 : 1 : 0)[m
[31m-[m
[31m- Note that one need not explicitly call[m
[31m- \code{EllipticCurve._reduce_point}[m
[31m- """[m
[31m- if R.is_zero():[m
[31m- return R.curve().change_ring(rings.GF(p))(0)[m
[31m- x, y = R.xy()[m
[31m- d = lcm(x.denominator(), y.denominator())[m
[31m- return R.curve().change_ring(rings.GF(p))([x*d, y*d, d])[m
[31m-[m
def is_x_coord(self, x):[m
r"""[m
Return True if ``x`` is the `x`-coordinate of a point on this curve.[m
[33mdiff --git a/src/sage/schemes/elliptic_curves/ell_point.py
b/src/sage/schemes/elliptic_curves/ell_point.py[m
[33mindex fdd20ab16f..e7f1256c35 100644[m
[33m--- a/src/sage/schemes/elliptic_curves/ell_point.py[m
[33m+++ b/src/sage/schemes/elliptic_curves/ell_point.py[m
[36m@@ -294,7 +294,7 @@[m [mclass
EllipticCurvePoint_field(SchemeMorphism_point_abelian_variety_field):[m
[m
x, y, z = v[m
if z == 0:[m
[31m- test = x[m
[32m+[m[32m test = x**3[m
else:[m
a1, a2, a3, a4, a6 = curve.ainvs()[m
test = y**2 + (a1*x+a3)*y - (((x+a2)*x+a4)*x+a6)[m
signature.asc
Description: PGP signature
