Ticket #1975 (see http://trac.sagemath.org/sage_trac/ticket/1975) is related: you can at least construct a curve over Z/NZ and do arithmetic with points on it. But the point-counting routines only work for curves defined over finite fields.
So, "it would be useful to do computations on an elliptic curve and just pretend that N was prime" -- is now possible, but cardinality is not. It might be possible to find the cardinality using random points (though at present it is not possible to call E.random_point() when E is not defined over a field. Of course, something is bound to go wrong -- example: sage: R = Zmod(91) sage: E = EllipticCurve(R,[0,0,0,1,1]) sage: P = E(0,1) sage: P.order() leads to a ZerDivisionError with the message ZeroDivisionError: Inverse of 49 does not exist (characteristic = 91 = 7*13) as does 5*P. John On 16 January 2011 02:59, Robert Bradshaw <rober...@math.washington.edu> wrote: > On Sat, Jan 15, 2011 at 4:20 PM, G Hahn <gh...@cantab.net> wrote: >> Hi, >> >> the sage reference on >> http://www.sagemath.org/doc/reference/sage/schemes/elliptic_curves/constructor.html >> reads that the EllipticCurve constructor can either be used with N >> prime (>> EllipticCurve(GF(N), [a, b])) or with N composite (>> >> EllipticCurve(Zmod(N),[a,b])), where [a,b] are the curve parameters in >> simplified Weierstrass form. However, computing the cardinality only >> works when N is prime (in both cases: GF and Zmod). >> Hence Zmod/GF/EllipticCurve must be doing an is_prime or at least >> is_pseudoprime check. For ECM (Lenstra's Elliptic Curve Method) and >> particularly Goldwasser-Kilian/ECPP (elliptic curve primality >> proving), it would be useful to do computations on an elliptic curve >> and just pretend that N was prime. As the whole purpose of ECPP is to >> prove primality, an is_prime() call within ECPP would be useless. >> >> Is there a way to use EllipticCurve() for composite N and to call >> cardinality() without calling is_prime() ? >> Alternatively, is there a way to call EllipticCurve() with a >> pseudoprimality test only ? (calling is_pseudoprime() would be >> acceptable as pseudoprimality tests only require polynomial time). >> For N composite, the cardinality/Schoof-Elkies-Atkin algorithm should >> crash or return a curve order which doesn't lie within the Hasse >> interval (and thus proves compositeness). > > Yes, GF does a primality check, as does the elliptic curve constructor > (indirectly, it calls is_field to determine the type of curve to > make). The ability to create a finite "field" object over something > known not to be prime would be a useful feature. One difficulty is > that if the assumption is that the order is prime, then there may be > algorithms which leverage this fact (and instead of crashing just > return invalid results if the field is not actually a field). In terms > of using EllipticCurve with composite N, one can (try to) do > arithmatic with the points and many other computations (this is what > you want, right?), but many of the cardinality algorithms won't work > (this is essentially the basic idea of ECM). I'm not so sure about SEA > failing detectably for composite N, especially an optimized version. > > - Robert > > -- > To post to this group, send an email to sage-devel@googlegroups.com > To unsubscribe from this group, send an email to > sage-devel+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/sage-devel > URL: http://www.sagemath.org > -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
