One question: will Pari 2.4 be here to stay? If so, then it's (eventually) inevitable that a port will have to be made. However, I'm not familiar with Pari's development, so I don't know if the new API is stable enough yet to justify a port.
Ronan ________________________________ De: Hamish Ivey-Law <hamish.ivey....@gmail.com> Para: sage-devel <sage-devel@googlegroups.com> Enviadas: Quarta-feira, 24 de Março de 2010 8:45:58 Assunto: [sage-devel] Re: Bug: Elliptic Curve Point Counting Hi Robert, On Mar 23, 4:39 pm, Robert Campbell <rcamp...@umbc.edu> wrote: > There is a bug somewhere in the point counting code for elliptic > curves. Checked both on Linux/4.2.x and OSX-PowerPC/4.2.1. The bug > appears to be either in the PARI ellsea routine or in the SAGE > interface to it. With some more time I plan to look further and look > for an easy fix (unless someone else is already doing the work). The > problem shows up with moderate sized curves over prime fields - a good > example being the NIST p-384 cryptographic curve: > > sage: p384 = 2^384 - 2^128 - 2^96 + 2^32 -1 > sage: b384 = > 0xB3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF > sage: E = EllipticCurve(GF(p384),[-3,b384]) > sage: E.cardinality() > > /Applications/sage/sage-4.2.1/local/lib/python2.6/site-packages/sage/ > schemes/elliptic_curves/sea.pyc > in ellsea(E, p, early_abort) > 45 gp.eval('E = ellinit(%s*Mod(1,%s));'%(E,p)) > 46 N = gp.eval("ellsea(E,%s,0,%s)"%(p,int(early_abort))) > 47 if N.find("*") != -1: > ---> 48 raise RuntimeError, "Error: '%s'"%N > 49 return Integer(N) > > RuntimeError: Error: ' *** vector: length (lg) overflow' I'm almost certain that this is a limitation in the PARI 2.3 series (which is what Sage uses) caused by the limited number of division polynomials. I ran into the same problem when generating curves over large prime fields, and the solution Bill Allombert (a Pari developer) and I came up with was to add David Kohel's database of division polynomials to PARI's SEAdata package. That work had to be done on the 2.4 development branch of PARI, which is somewhat unfortunate since upgrading the PARI version used by Sage would be a monumental task due to the fact that PARI 2.4 breaks backwards compatibility with 2.3. I suppose ideally Sage would have its own Cython version of SEA (Sage already includes David's division polynomial base as the package 'database_kohel-20060803'), but for now I think the only way you'll be able to do point counting over prime finite fields bigger than about 256 bits is to use the development version of PARI. I would be pleased to be proved wrong however! Regards, Hamish. -- 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 unsubscribe from this group, send email to sage-devel+unsubscribegooglegroups.com or reply to this email with the words "REMOVE ME" as the subject. ____________________________________________________________________________________ Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com -- 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 unsubscribe from this group, send email to sage-devel+unsubscribegooglegroups.com or reply to this email with the words "REMOVE ME" as the subject.