Ask Your Question
0

Elliptic Curves defined over Z/nZ rings for general n

asked 2017-02-09 16:25:57 +0200

fagui gravatar image

An Elliptic curve is the union of its affine part Eaff(Z/nZ)={ [x,y,1] in P2(Z/nZ) such that y2 =x3+ax+b } and the point at infinity O = [0,1,0]

P2(Z/nZ) is the projective plane:

T = { (x,y,z) in (Z/nZ)^3 such that gcd(x,y,z,n) = 1}

P2(Z/nZ) = (T / ~) where ~ is the equivalence relation defined by (x,y,z) ~ (x0,y0,z0) iff there is an INVERSIBLE element u in Z/nZ ⇤ such that (x,y,z) = u(x0,y0,z0).

I found those doc pages

http://fe.math.kobe-u.ac.jp/icms2010-...

http://doc.sagemath.org/html/en/refer...

I think to define an Elliptic Curve here with

q=10
E1 = EllipticCurve(Zmod(q),[0,1])
E1

Elliptic Curve defined by y^2 = x^3 + 1 over Ring of integers modulo 10

but

E1.points()

is not working. is there a method to get all the points of this Elliptic Curve ? its cardinality etc ????

edit retag flag offensive close merge delete

Comments

The error AttributeError: 'EllipticCurve_generic_with_category' object has no attribute 'points' seems pretty clear. Maybe this should be a NotImplementedError instead? Interestingly, for some composite q we get a different error about it being a singular curve, so in those cases of course we never get to the point counting in the first place.

kcrisman gravatar imagekcrisman ( 2017-02-09 19:04:35 +0200 )edit

do you see a way around that ?

fagui gravatar imagefagui ( 2017-02-10 02:12:10 +0200 )edit

1 Answer

Sort by » oldest newest most voted
0

answered 2017-02-10 03:20:29 +0200

kcrisman gravatar image

I guess a naive workaround would be this:

var('x,y')
solve_mod(y^2==x^3+1,10)

Result seems correct:

[(0, 1), (0, 9), (2, 7), (2, 3), (4, 5), (5, 6), (5, 4), (7, 2), (7, 8), (9, 0)]

But this has a very boring algorithm that has nothing to do with elliptic curves and surely is very slow and inefficient. Not being an expert, I would wonder whether there is a reason why this is not implemented in the first place - perhaps such "curves" over non-prime moduli aren't really well understood or do not obey the usual theorems?

edit flag offensive delete link more

Comments

i think they should be well understood to some extent. there are the basis of some powerful popular methods for integer factorization or proving that a large number is prime for example.

fagui gravatar imagefagui ( 2017-02-10 09:52:38 +0200 )edit

Indeed, I had been under the impression that such factoring algorithms utilized only prime or prime power moduli, but https://en.wikipedia.org/wiki/Lenstra... says I was misinformed!

kcrisman gravatar imagekcrisman ( 2017-02-10 16:35:16 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-02-09 16:25:57 +0200

Seen: 662 times

Last updated: Feb 10 '17