[sage-devel] Re: Possible bug regarding elliptic curves modulo prime powers
I fear you will have to do a lot by hand in sage. You can reduce a projective point modulo p^k as below, but the output will have to be a list of elements in Z/p^kZ, since projective spaces are not defined over general rings as far as I am aware. What I meant is that you can actually work in E( Qp ) instead and at the end extract the mod p^k information that you need. I am sure others are better placed to comment how much easier these things are in magma. Chris sage: def reduction_of_point(P,k): : """ : Reduce projective point P defined over Qp modulo p^k : """ : v = min(valuation(x) for x in P) : p = P[0].parent().prime() : R = IntegerModRing(p^k) : return [ R( p^(-v)*x ) for x in P] On Friday, 15 May 2020 09:53:46 UTC+1, Daniel Loughran wrote: > > Hi Chris, > > Thanks for the advice, but I can't seem to get this to work either. I get > the error "ValueError: element must have non-negative valuation in order > to compute residue". > > Any idea how to make this work without errors? Or should I just give up > and use magma instead? > > E=EllipticCurve(Qp(2,5),[0, 0, 1, -1, 0]); E > > Elliptic Curve defined by y^2 + (1+O(2^5))*y = x^3 + > (1+2+2^2+2^3+2^4+O(2^5))*x over 2-adic Field with capped relative precision 5 > > P=E(2,-3,8); P > > (2^-2 + O(2^3) : 2^-3 + 2^-1 + 1 + 2 + O(2^2) : 1 + O(2^5)) > > 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) > ValueError: element must have non-negative valuation in order to compute > residue. > > > Dan > > On Friday, 15 May 2020 09:44:43 UTC+1, chris wuthrich wrote: >> >> Dear Daniel >> >> indeed elliptic curves over rings (what should be called technically >> Weierstrass equations with non-zero discriminant, instead of unit >> discriminant) are rather useless in Sage. >> I would recommend to work with 2-adics in your case and to reduce modulo >> 4 in the end. You could work over Qp(p,k) if you want modulo p^k. >> >> I hope that this may help with what you do. Of course, one should >> implement this properly one day. >> >> Chris >> >> On Thursday, 14 May 2020 11:41:04 UTC+1, 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. >>> >>> 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. = 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 sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/43d0ccd8-bbe1-4305-b816-e97791e5d25e%40googlegroups.com.
[sage-devel] Re: Possible bug regarding elliptic curves modulo prime powers
Hi Chris, Thanks for the advice, but I can't seem to get this to work either. I get the error "ValueError: element must have non-negative valuation in order to compute residue". Any idea how to make this work without errors? Or should I just give up and use magma instead? E=EllipticCurve(Qp(2,5),[0, 0, 1, -1, 0]); E Elliptic Curve defined by y^2 + (1+O(2^5))*y = x^3 + (1+2+2^2+2^3+2^4+O(2^5))*x over 2-adic Field with capped relative precision 5 P=E(2,-3,8); P (2^-2 + O(2^3) : 2^-3 + 2^-1 + 1 + 2 + O(2^2) : 1 + O(2^5)) 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) ValueError: element must have non-negative valuation in order to compute residue. Dan On Friday, 15 May 2020 09:44:43 UTC+1, chris wuthrich wrote: > > Dear Daniel > > indeed elliptic curves over rings (what should be called technically > Weierstrass equations with non-zero discriminant, instead of unit > discriminant) are rather useless in Sage. > I would recommend to work with 2-adics in your case and to reduce modulo 4 > in the end. You could work over Qp(p,k) if you want modulo p^k. > > I hope that this may help with what you do. Of course, one should > implement this properly one day. > > Chris > > On Thursday, 14 May 2020 11:41:04 UTC+1, 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. >> >> 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. = 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 sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/6d5a9cd1-dfb2-4cd1-baba-6e51f1f39d15%40googlegroups.com.
[sage-devel] Re: Possible bug regarding elliptic curves modulo prime powers
I think I can explain this. Basically, Sage does *not* support elliptic curves over rings which are not integral domains, and in particular does not support them over Z/NZ except for N prime. BUT at some opint in the past it had been possible to demonstrate the elliptic curve factorization method by creating elliptic curves over Z/NZ (where N is the number to be factored), and when that stoppped working becuase someone actually put in a test that the base ring was in integral domain, people who used Sage for teaching complained. One such person was Ken Ribet, whose opinion counts for something among number theorists (and beyond, he has been President of the AMS). So someone else (OK it was me) put a fudge into the constructor whereby if the base field is finite then it constructs the curve of type elliptic_curve_field -- so that one is then allowed to construct points and add them etc -- which kept Ribet happy. Now one can remove that fudge -- ot at least have a big warning output when it is used, but there will be people who object. If someone wants to implement elliptic curves over Z/NZ for arbitrary N (or just prime power N) then they are welcome, but you will want to think very carefully about what you are doing and whether it even makes sense to do arithmetic on points. John On Thursday, May 14, 2020 at 11:41:04 AM UTC+1, 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. > > 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. = 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 sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/c41b3535-0fc7-4246-a814-67b8b05a602d%40googlegroups.com.
[sage-devel] Re: Possible bug regarding elliptic curves modulo prime powers
Dear Daniel indeed elliptic curves over rings (what should be called technically Weierstrass equations with non-zero discriminant, instead of unit discriminant) are rather useless in Sage. I would recommend to work with 2-adics in your case and to reduce modulo 4 in the end. You could work over Qp(p,k) if you want modulo p^k. I hope that this may help with what you do. Of course, one should implement this properly one day. Chris On Thursday, 14 May 2020 11:41:04 UTC+1, 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. > > 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. = 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 sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/cda39b98-71be-462d-aa41-7d1195a0383e%40googlegroups.com.
