any_root is broken in characteristic 2

[roed314]

The following example will hang:

sage: k = GF(2^60)
sage: R.<x> = k[]
sage: f = (x - k.random_element()) * (x - k.random_element())
sage: f.any_root()

while this will quickly succeed:

sage: f.roots(multiplicities=False)[0]

The core of the any_root implementation is the following (from poylnomial_element.pyx):

if q % 2 == 0:
    while True:
        T = R.random_element(2*degree-1)
        if T == 0:
            continue
        T = T.monic()
        C = T
        for i in range(degree-1):
            C = T + pow(C,q,self)
        h = self.gcd(C)
        hd = h.degree()
        if hd != 0 and hd != self.degree():
            if 2*hd <= self.degree():
                return h.any_root(ring, -degree, True)
            else:
                return (self//h).any_root(ring, -degree, True)

In the example above, degree=1 (since we're looking for roots in the base ring), and thus we're just randomly choosing a T and seeing if it has nontrivial gcd with the input. So we're just randomly guessing in large characteristic 2 fields, which of course takes a long time.

Sage's implementation follows the description of the Cantor-Zassenhaus algorithm in Cohen's Intro to Computational Algebraic Number Theory (Alg. 3.4.8) for example, but that exposition is focused on the case that the base ring is a prime field (GF(2) here). In order to handle other characteristic 2 finite fields you need to do more work: see the original paper or this preprint.

Two possible solutions: either implement the algorithm properly, or fall back to just using f.roots(multiplicities=False)[0] in this case.

Component: finite rings

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

[grhkm21]

Fixed in #37170.