thanks for your help. I see that arithmetic is possible with a composite N on an elliptic curve.
My inital question focused on the ECPP (Goldwasser-Kilian) algorithm which uses the cardinality() command. In case of ECPP/GoldwasserKilian (but not in the case of ECM...), any code in sage that uses EllipticCurve() for curve computations is currently superfluous as long as is_prime is called ! Would it be possible to include a flag such as "check=false" into EllipticCurve() or cardinality() to suppress the is_prime() call and to do all computations at the user's risk (as proposed by Jean-René Reinhard on http://trac.sagemath.org/sage_trac/ticket/10562)? Verification of results, exception handling etc. would be in the user's responsibility... Then, all existing code would be still usable and the (ECM and) ECPP problem would be solved. Georg On 16 Jan., 18:43, John Cremona <john.crem...@gmail.com> wrote: > Ticket #1975 (seehttp://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/co... > >> 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 > > athttp://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
