Steps To Reproduce

In my refactoring of any_root() #37170 I accidentally introduced a performance regression when finding roots over extension fields.

Sage 10.2

sage: %time _ = f.any_root()
CPU times: user 6.89 ms, sys: 321 µs, total: 7.21 ms
Wall time: 6.91 ms
sage: %time _ = f.any_root(L)
CPU times: user 7.34 ms, sys: 316 µs, total: 7.66 ms
Wall time: 7.42 ms
sage: %time _ = f.change_ring(L).any_root()
CPU times: user 3.13 s, sys: 9.92 ms, total: 3.14 s
Wall time: 3.15 s

SageMath version 10.3.beta8

sage: %time _ = f.any_root()
CPU times: user 6.68 ms, sys: 116 µs, total: 6.8 ms
Wall time: 6.75 ms
sage: %time _ = f.any_root(L)
CPU times: user 844 ms, sys: 4.69 ms, total: 849 ms
Wall time: 849 ms
sage: %time _ = f.change_ring(L).any_root()
CPU times: user 819 ms, sys: 3.62 ms, total: 823 ms
Wall time: 823 ms

Expected Behavior

When I refactor code, it should not have worse performance

Actual Behavior

I have refactored code and introduced poor performance

Additional Information

The fix will be to go back to any_root() and complicate the implementation to look for a root in the smallest extension before casting the root to F_ext. Currently, the implementation finds a root in f.change_ring(F_ext).any_root() which is very slow for very large extensions.

The new version should look for some degree degree distinct degree factorisation over various extensions working with the smallest one possible.

Environment

N/A

Checklist

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