points on elliptic curves mod N

[Kenneth A. Ribet]

Hi,

I'd like to present Lenstra's elliptic curve factoring method to a class. This means that I'd like to define an elliptic curve over Integers(N), where N is composite, and then add points on that curve in sage. I may be doing something stupid, but I'm getting a NotImplementedError with the method I'm using:

sage: E=EllipticCurve([0,Mod(1,59)]); E
Elliptic Curve defined by y^2 = x^3 + 1 over Ring of integers modulo 59
sage: E([0,1])
(0 : 1 : 1)
sage: E=EllipticCurve([0,Mod(1,5963)]); E
Elliptic Curve defined by y^2 = x^3 + 1 over Ring of integers modulo 5963
sage: E([0,1])
Traceback (most recent call last):
...
NotImplementedError

Is there a workaround? Does an alternative approach allow the desired computations?

Thanks much in advance!

Best,
Ken R

[William Stein]

You can see how I do this in the code samples in Chapter 6.3 of my
elementary number theory book:

http://wstein.org/ent/ent.pdf

The key trick is:

sage: R = Integers(2010)
sage: # Make Sage think that R is a field
sage: R.is_field = lambda : True
sage: E = EllipticCurve(R, [0,1])
sage: E
Elliptic Curve defined by y^2 = x^3 + 1 over Ring of integers modulo 2010

William

-- William

[Ken Ribet]

> The key trick is:
>
> sage: R = Integers(2010)
> sage: # Make Sage think that R is a field

I'm stunned. Thanks!

Ken

[Robert Bradshaw]

Much of Sage's elliptic curve functionality assumes that it is defined
over a field, so you may have to pretend that your basering is a
field, though I think the above should work. Try this:

sage: R = Integers(5963)

sage: R.is_field = lambda : True

sage: R.is_field()
True
sage: E = EllipticCurve([0, R(1)]); E

Elliptic Curve defined by y^2 = x^3 + 1 over Ring of integers modulo
5963
sage: E([0,1])

(0 : 1 : 1)

This particular point however seems to have order 3 on both E(GF(67))
and E(GF(89)).

- Robert

[Alec Mihailovs]

On Apr 10, 8:27 pm, Robert Bradshaw <rober...@math.washington.edu>
wrote:

> This particular point however seems to have order 3 on both E(GF(67))  
> and E(GF(89)).

E=EllipticCurve([1,R(1)])

seems to be working,

7*E([0,1])

Traceback (click to the left of this block for traceback)
...
ZeroDivisionError: Inverse of 5092 does not exist

Alec

[John Cremona]

Here's the problem. For an elliptic curve defined over a ring, not a
field, the _point_class (which is the class used to hold its points)
is the class EllipticCurvePoint, but that class has almost no methods
at all defined for it, not even an __init__ method. By contrast, for
elliptic curves defined over fields the point class is
EllipticCurvePoint_field (or EllipticCurvePoint_finite_field, etc),
which all have a huge amount of functionality.

One could defined a new class called something like
EllipticCurvePoint_commutative_ring, and move most of the
functionality from the field class to the ring class, but that would
be a lot of work, and there would be a danger that the operations over
fields would be slowed down. And one would have to decide how to deal
with the group law now only being partial (which I know can be done,
but I forget the details).

It would be a good student project to at least handle the case where
the base ring was of the form Integers(n), where the error message
produced by trying to invert a non-invertible constant would helpfully
tell you the factorization of the modulus.

John

[chris wuthrich]

Let link the discussion to the old ticket :
http://trac.sagemath.org/sage_trac/ticket/1975

chris.

[John Cremona]

The same point came up in another thread on sage-support, which
spurred me to actually come with a solution. There's a patch at #1975
which sorts this out, and should allow Ken to teach what he wanted to!

John

On Apr 12, 7:00 pm, chris wuthrich <christian.wuthr...@gmail.com>
wrote:

> Let link the discussion to the old ticket :http://trac.sagemath.org/sage_trac/ticket/1975
>
> chris.

--
To post to this group, send email to sage-s...@googlegroups.com
To unsubscribe from this group, send email to sage-support...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-support
URL: http://www.sagemath.org