Steps To Reproduce

sage: K.<z16> = GF(2^16)
....: R.<x> = K[]
....: u = R.irreducible_element(2)
....: 
....: K_ext = K.extension(modulus=u, names="a")
....: R_ext.<y_ext> = K_ext[]
....: poly = R_ext.random_monic_element(2)
....: print("poly:", poly)
....: 
....: poly.roots()

Expected Behavior

It should take a short time, especially since here u is irreducible, so K_ext is in theory isomorphic to GF(2^32), and over that field it takes no time to find roots, just do hensel lift or whatever:

sage: K.<x> = GF(2^32)[]
....: %timeit K.random_monic_element(2).roots()
1.37 ms ± 55.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Actual Behavior

It's slow... Even changing the base field from 2^16 to 2^8 takes forever. Moreover, the time is spent on this weird self._roots_from_factorization(self.factor(), multiplicities) call. I suspect it is because I specify the modulus in the K_ext construction, so it has to compute some field isomorphism. Still, I don't see how 8-bit computations will take this long.

For more details, here's the timings:

sage: K.<z16> = GF(2^8)
....: R.<x> = K[]
....: u = R.irreducible_element(2)
....: 
....: K_ext = K.extension(modulus=u, names="a")
....: R_ext.<y_ext> = K_ext[]
....: %time R_ext.random_monic_element(2).roots()
....: %time _ = [R_ext.random_monic_element(2).roots() for _ in range(10^3)]
CPU times: user 43.8 s, sys: 163 ms, total: 44 s
Wall time: 44.4 s
[]
CPU times: user 3.91 s, sys: 15 ms, total: 3.93 s
Wall time: 3.94 s

As seen, a ridiculous amount of time is spent on some kind of field isomorphism / data initialisation.

Additional Information

I tried tracing the calls myself, but as mentioned, it goes into some weird call path _roots_from_factorization that I can't understand. Any help with either debugging the above or redirect it to use GF(2^32) like I suggested, would be appreciated.

For more additional information, this behaviour only seem to occur for $K = \mathbb{F}_q$ where $q = 2^k \geq 2^8$. Also once it finishes (which takes several tens of seconds), the root finding itself is very fast. To observe this, run while True: R_ext.random_monic_element(2).roots(). This behaviour also doesn't happen, even for weird fields like $K = \mathbb{F}_{103^{13}}$ the whole process takes < 1s.