Fast algorithms for solving equations of degree $\le4$ in some finite fields

It is possible to solve equations of degree $\leq 4$ in some bases of the field $GF(p^s),$ where $p>3,$ $s = 2^kr,$ $k \rightarrow \infty,$ $r=\pm 1 \pmod 6,$ $p,r=O(1)$, with the bit complexity
$$ O_r(M(2^k)kM(r)M(\lceil \log_2p)\rceil)= O_{r,p}(M(s)\log_2s), $$
where $M(n)$ is the complexity of polynomial multiplication. In a normal basis of the fields $GF(3^s),$ $s=\pm 1 \pmod 6,$ all roots may be found with the bit complexity $O(M(GF(3^s))\log_2s),$ where $M(GF(q))$ is the complexity of multiplication in the field $GF(q).$ For normal bases in the fields $GF(2^s),$ where $s = 2r,$ $r \neq 0 \pmod 3,$ the bit complexity is $O(M(GF(2^s))\log_2s).$