#6218: small changes to jacobian_morphism to make hyperelliptic curve arithmetic
faster
--------------------------------+-------------------------------------------
Reporter: ncalexan | Owner: was
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.0.1
Component: algebraic geometry | Keywords: jacobian morphism hyperelliptic
curve speed profile time
--------------------------------+-------------------------------------------
The attached patch uses % instead of the generic mod and avoids creating
polynomial rings. The savings are significant:
{{{
sage: F = GF(next_prime(10^30))
sage: x = F['x'].gen()
sage: f = x^7 + x^2 + 1
sage: H = HyperellipticCurve(f, 2*x); H
Hyperelliptic Curve over Finite Field of size
1000000000000000000000000000057 defined by y^2 + 2*x*y = x^7 + x^2 + 1
sage: J = H.jacobian()(F); J
verbose 0 (902: multi_polynomial_ideal.py, dimension) Warning: falling
back to very slow toy implementation.
Set of points of Jacobian of Hyperelliptic Curve over Finite Field of size
1000000000000000000000000000057 defined by y^2 + 2*x*y = x^7 + x^2 + 1
defined over Finite Field of size 1000000000000000000000000000057
sage: Q = J(H.lift_x(F(1))); Q
(x + 1000000000000000000000000000056, y + 1000000000000000000000000000056)
}}}
Before:
{{{
sage: %time ZZ.random_element(10**10) * Q
CPU times: user 0.91 s, sys: 0.02 s, total: 0.93 s
Wall time: 0.93 s
(x^3 + 402198643461859040647192719684*x^2 +
601836335767969290835741174254*x + 16518729356967251698882316239, y +
473734498489001855322294293716*x^2 + 971294794490578173226993121181*x +
205331062061696832607472618253)
sage: %timeit ZZ.random_element(10**10) * Q
10 loops, best of 3: 980 ms per loop
}}}
After:
{{{
sage: %time ZZ.random_element(10^10) * Q
CPU times: user 0.22 s, sys: 0.01 s, total: 0.23 s
Wall time: 0.25 s
(x^3 + 275125861943108889646384133572*x^2 +
753495481691507497462095614898*x + 60041420316935318537784907957, y +
904016250260250717251913633712*x^2 + 297807486916138001851276656278*x +
514899226321704405985204664612)
sage: %timeit ZZ.random_element(10**10) * Q
10 loops, best of 3: 207 ms per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6218>
Sage <http://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
-~----------~----~----~----~------~----~------~--~---
