Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Vestnik Moskov. Univ. Ser. 1. Mat. Mekh.: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

 Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2021, Number 3, Pages 22–31 (Mi vmumm4399)  Mathematics

Fast algorithms for solving fourth order equations in some finite fields

S. B. Gashkov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: 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).$

Key words: solving equations, bit complexity, tower of finite fields, standard and normal bases.

 Funding Agency Grant Number Russian Foundation for Basic Research 19-01-0029418-01-00337 Full text: PDF file (413 kB) First page: PDF file References: PDF file   HTML file
UDC: 511

Citation: S. B. Gashkov, “Fast algorithms for solving fourth order equations in some finite fields”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2021, no. 3, 22–31 Citation in format AMSBIB
\Bibitem{Gas21} \by S.~B.~Gashkov \paper Fast algorithms for solving fourth order equations in some finite fields \jour Vestnik Moskov. Univ. Ser.~1. Mat. Mekh. \yr 2021 \issue 3 \pages 22--31 \mathnet{http://mi.mathnet.ru/vmumm4399} 

 SHARE:       Contact us: math-net2021_11 [at] mi-ras ru Terms of Use Registration to the website Logotypes © Steklov Mathematical Institute RAS, 2021