#10562: class ECPP added to sage: provides primality proving via
Goldwasser-Kilian
and Atkin-Morain (ECPP)
--------------------------------+-------------------------------------------
Reporter: ghahn@… | Owner: was
Type: enhancement | Status: needs_review
Priority: major | Milestone:
Component: number theory | Keywords: ecpp, goldwasser, kilian,
primality, proving
Author: Georg Hahn | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Comment(by jrreinhard):
Hi,
I have been implementing an ECPP certificate verification sage script in
the latest days as well. I am pleased to see that such a procedure is
being incorporated in Sage.
During my work I noticed an issue that seems to be still present in the
current code base. (I have been using an older sage install...) When
creating an elliptic curve over Z_N using the Elliptic Curve constructor,
the primality of N is proven through calls to the is_prime function.
Several such calls are performed in the `EllipticCurve` constructor, the
`EllipticCurve_generic` constructor...
In Sage, it doesn't seem possible for the time being to build an
`EllipticCurve` object without proving/disproving the primality of the
characteristic of the underlying Ring. This slows down the ECPP
certificate verification, and makes it pointless since another proven
method is used behind the scenes on the integer we want to prove the
primality of.
Is this an issue for your code? When profiling your (verification) code,
does the computation spend a significant amount of its running time in
method 'is_prime' of 'sage.rings.integer.Integer'. (profile with %prun
e.verify_certificate())
As a side comment, the is_prime method of the Integer class is probably
also a good place to call your code from.
I apologize for not being able to perform more in depth tests before
reporting this potential issue (I am not able to set up a sage development
environment at short notice).
Best wishes,
Jean-René
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10562#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
