sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.33k stars 453 forks source link

hardcode that curves have dimension 1 #34284

Closed yyyyx4 closed 2 years ago

yyyyx4 commented 2 years ago

Example:

sage: proof.all(False)
sage: R.<x> = GF((2^521-1,2))[]
sage: C = HyperellipticCurve(R.random_element(degree=999))
sage: %time _ = C.jacobian()
verbose 0 (3879: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
verbose 0 (1082: multi_polynomial_ideal.py, dimension) Warning: falling back to very slow toy implementation.
CPU times: user 2.67 s, sys: 9.99 ms, total: 2.68 s
Wall time: 2.72 s

All the time is spent on computing the dimension of the curve, and since the base field is not suitable for Singular this is done using Sage's own implementation.

By definition, curves have dimension one, so this is totally redundant and can be avoided by adding an implementation of .dimension() to Curve_generic that simply returns 1.

This was pointed out here:

https://github.com/jack4818/Castryck-Decru-SageMath#additional-monkey-patch-for-fixing-the-dimension

With the patch, there is no more "toy implementation" warning and it's fast:

CPU times: user 119 µs, sys: 2 µs, total: 121 µs
Wall time: 124 µs

CC: @k3w1k0d3r

Component: algebraic geometry

Author: Lorenz Panny

Branch/Commit: cbd8040

Reviewer: Julien Grijalva

Issue created by migration from https://trac.sagemath.org/ticket/34284

k3w1k0d3r commented 2 years ago

Reviewer: Julien Grijalva

vbraun commented 2 years ago

Changed branch from public/hardcode_that_curves_have_dimension_1 to cbd8040