Elliptic curve over Z modulo composite N

asked 2025-06-30 22:16:48 +0200

Xxxharsh gravatar image

updated 2025-06-30 22:39:22 +0200

It's known, that $$E_{A,B}(Z_p^2) \cong E_{A,B}(Z_p) \oplus Z_p \text{ when } q:=|E_{A,B}(Z_p) | \neq p$$ Therefore $exp (E_{A,B}(Z_p^2) )=lcm(q,p)$. But when it comes to implementing this on sage

p=115792089237316195423570985008687907853269984665640564039457584007913129639747
K  = GF(p)
E  = EllipticCurve(K, [a, b])
EE = EllipticCurve(IntegerModRing(p^2), [a, b])
q=E.order()
c=12010
P=EE.lift_x(c)
q*P

I keep getting ZeroDivisionError. I looked at the traceback and it seems, that sage just tries to compute $P+Q$ as if the elliptic curve is defined over a field. Can someone explain this and/or find another way to compute $qP$ for arbitrary $P \in (E_{A,B}(Z_p^2) )$ ?

edit retag flag offensive close merge delete

Comments

What is a and b in your code?

Max Alekseyev gravatar imageMax Alekseyev ( 2025-06-30 23:08:41 +0200 )edit

a = -3 b = 2697448053935541741976221051345108825177671050689533270507

Xxxharsh gravatar imageXxxharsh ( 2025-06-30 23:48:13 +0200 )edit

Your code works fine in Sagecell: https://sagecell.sagemath.org/?q=ydnjkt Perhaps, it's time to update your Sage version.

Max Alekseyev gravatar imageMax Alekseyev ( 2025-07-01 04:46:36 +0200 )edit

Interesting, but I have Sagemath 10.4. Anyway, thanks for the help!

Xxxharsh gravatar imageXxxharsh ( 2025-07-01 09:06:16 +0200 )edit

Sagecell runs SageMath version 10.6, Release Date: 2025-03-31

Max Alekseyev gravatar imageMax Alekseyev ( 2025-07-01 19:06:26 +0200 )edit