Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 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

 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}