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
