Test for `elliptic_curves/hom.py` times out

S17A05 commented 8 months ago

Steps To Reproduce

sage -t --random-seed=212256703328484530299262546120222329602 src/sage/schemes/elliptic_curves/hom.py

Expected Behavior

The test should complete successfully.

Actual Behavior

The test times out.

Additional Information

No response

Environment

- **OS**: Windows 11 (WSL Ubuntu 22.04)
- **Sage Version**: 10.3beta8

Checklist

[X] I have searched the existing issues for a bug report that matches the one I want to file, without success.
[X] I have read the documentation and troubleshoot guide

grhkm21 commented 8 months ago

Hanging test:

p, e = 29, 3
F.<t> = GF((p, e))
E = EllipticCurve([13*t^2 + 19*t + 12, 12*t^2 + 18*t])
pi = E.frobenius_endomorphism()
compute_trace_generic(pi) == E.trace_of_frobenius() # hangs

Reduced:

sage: from sage.schemes.elliptic_curves.ell_field import point_of_order
sage: F.<t> = GF((29, 3))
....: E = EllipticCurve([13*t^2 + 19*t + 12, 12*t^2 + 18*t])
....: point_of_order(E, 11)

grhkm21 commented 8 months ago

The code hangs because it's trying to find a point of order $11$ on the curve $E$ possibly extended to a larger field. So it tries to factor the division polynomial (of degree $60$ over $\mathbb{F}_{29^{3}}$) in its splitting field $\mathbb{F}_{29^{180}}$, which is slow.

Not sure what the correct fix is. Should the point_of_order function take in a max_extension_degree argument that limits the $180 / 3$ ratio above?

@yyyyx4

yyyyx4 commented 8 months ago

Easy fix for the doctest failure: Restrict the random sampling to smaller fields.
Real fix for the underlying issue: Wait for extension towers to work properly.
An intermediate workaround would be what you suggested. However, such cutoffs are annoying to optimize because the relative costs of point order and extension degree depend on a lot of things...

grhkm21 commented 8 months ago

After looking around even more, it seems that it's not actually about roots in extension towers, but rather the inefficiency of .any_root. See this:

sage: K.<x> = GF((29, 3), names="a")[]
....: f = K.random_element(12).monic()
....: L.<a> = f.splitting_field()
....: %time _ = f.roots(L)
....: %time _ = f.any_root(L)
CPU times: user 49.9 ms, sys: 236 µs, total: 50.1 ms
Wall time: 50.8 ms
CPU times: user 818 ms, sys: 2.66 ms, total: 821 ms
Wall time: 824 ms

sage: K.<x> = GF((29, 3), names="a")[]
....: f = K.random_element(15).monic()
....: L.<a> = f.splitting_field()
....: %time _ = f.roots(L)
....: %time _ = f.any_root(L)
CPU times: user 223 ms, sys: 1.14 ms, total: 224 ms
Wall time: 226 ms
CPU times: user 13.3 s, sys: 147 ms, total: 13.4 s
Wall time: 13.8 s

@GiacomoPope In your issue #37170 you only dealt with the slowness of .any_root in the char 2 case right? Did you also look at the other cases?

GiacomoPope commented 8 months ago

The char 2 wasn't "slow" it was just broken. The root was found by literally guessing random polynomials!

Remy's code replaces the CZ step by trying to make these parts more efficient but my code is very much the naive idea as taken from Cohen's textbook.

grhkm21 commented 8 months ago

Oh lmao. I'll see if I can do anything with Remy's code then. If it doesn't work the entire method should just be replaced with choice(factor(f))[0] or something...

GiacomoPope commented 8 months ago

Using the new code in https://github.com/sagemath/sage/issues/37442 I get

sage: K.<x> = GF((29, 3), names="a")[]
....: f = K.random_element(15).monic()
....: L.<a> = f.splitting_field()
....: %time _ = f.roots(L)
....: %time _ = f.any_root(L)
CPU times: user 682 ms, sys: 2.5 ms, total: 684 ms
Wall time: 687 ms
CPU times: user 95 ms, sys: 257 µs, total: 95.3 ms
Wall time: 95.4 ms

Just to confirm, I also can do

sage: from sage.schemes.elliptic_curves.ell_field import point_of_order
sage: F.<t> = GF((29, 3))
....: E = EllipticCurve([13*t^2 + 19*t + 12, 12*t^2 + 18*t])
....: %time _ = point_of_order(E, 11)
CPU times: user 9.29 s, sys: 20.5 ms, total: 9.31 s
Wall time: 9.32 s

GiacomoPope commented 8 months ago

Comparison with 10.2

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 10.2, Release Date: 2023-12-03                    │
│ Using Python 3.11.4. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
sage: set_random_seed(0)
....: from sage.schemes.elliptic_curves.ell_field import point_of_order
....: F.<t> = GF((29, 3))
....: E = EllipticCurve([13*t^2 + 19*t + 12, 12*t^2 + 18*t])
....: %time _ = point_of_order(E, 11)
CPU times: user 10.9 s, sys: 29.2 ms, total: 10.9 s
Wall time: 10.9 s

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 10.3.beta8, Release Date: 2024-02-13              │
│ Using Python 3.11.4. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: set_random_seed(0)
....: from sage.schemes.elliptic_curves.ell_field import point_of_order
....: F.<t> = GF((29, 3))
....: E = EllipticCurve([13*t^2 + 19*t + 12, 12*t^2 + 18*t])
....: %time _ = point_of_order(E, 11)
CPU times: user 9.23 s, sys: 31.7 ms, total: 9.27 s
Wall time: 9.28 s

sagemath / sage