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.
