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






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-00294
18-01-00337


Full text: PDF file (413 kB)
First page: PDF file
References: PDF file   HTML file
UDC: 511
Received: 11.09.2020

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}


Linking options:
  • http://mi.mathnet.ru/eng/vmumm4399
  • http://mi.mathnet.ru/eng/vmumm/y2021/i3/p22

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:16
    References:1
    First page:2

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021