#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):
Replying to [comment:10 ghahn@…]:
> Hi,
>
> thanks for your helpful comment! I didn't know about the is_prime() call
within the EllipticCurve constructor. Up to now, I haven't noticed any
slowdown due to EllipticCurve() (although I haven't paid attention
either...).
>
I only perform verification of certificates obtained by other means. My
code spends more than 90% of its running time in is_prime, which is called
several times from `EllipticCurve` constructor. The behaviour of this
constructor has an huge impact on the performance.
> Isn't it the case that is_prime() switches over to a pseudoprimality
test as soon as the input number exceeds a certain bound (which will be
probably the case for numbers tested via ECPP) and is thus very fast
again? If not, it would indeed make the code pointless somehow
is_prime doesn't perform the switch from proven behaviour to probable
behaviour unless asked for. (cf sage: ?is_prime )
> (as computations on elliptic curves are vital for ECPP and it wouldn't
make that much sense to me to re-implement EllipticCurve, Schoof-Elkies-
Atkin etc just for this single file ecpp.pyx)
I think the best option would be to add a flag to the `EllipticCurve` and
`EllipticCurve_generic` constructors determining whether primality tests
are performed or not. This should enable to continue using the existing
codebase on elliptic curves.
Finally, I have been working on an old version of Sage (4.0.2), my claims
may be false in the latest versions, although reading the elliptic curve
constructor code in the sage repository leads me to believe that the issue
is still there.
> Best,
> Georg
Best wishes,
Jean-René
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10562#comment:11>
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.
