Geodesic
Fast algorithms for solving equations of degree $\le4$ in some finite fields
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2021), pp. 22-31

Voir la notice de l'article provenant de la source Math-Net.Ru

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).$ 
@article{VMUMM_2021_3_a2,
     author = {S. B. Gashkov},
     title = {Fast algorithms for solving equations of degree $\le4$  in some finite fields},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {22--31},
     publisher = {mathdoc},
     number = {3},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2021_3_a2/}
}
TY  - JOUR
AU  - S. B. Gashkov
TI  - Fast algorithms for solving equations of degree $\le4$  in some finite fields
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2021
SP  - 22
EP  - 31
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2021_3_a2/
LA  - ru
ID  - VMUMM_2021_3_a2
ER  - 
%0 Journal Article
%A S. B. Gashkov
%T Fast algorithms for solving equations of degree $\le4$  in some finite fields
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2021
%P 22-31
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMUMM_2021_3_a2/
%G ru
%F VMUMM_2021_3_a2
S. B. Gashkov. Fast algorithms for solving equations of degree $\le4$  in some finite fields. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2021), pp. 22-31. http://geodesic.mathdoc.fr/item/VMUMM_2021_3_a2/