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., 2019, Number 1, Pages 7–15 (Mi vmumm593)  

Mathematics

The complexity of solving low degree equations over ring of integers and residue rings

S. B. Gashkova, I. B. Gashkovb, A. B. Frolovc

a Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
b Karlstads University, Sweden
c National Research University "Moscow Power Engineering Institute"

Abstract: It is proved that for an arbitrary polynomial $f(x)\in\mathbb{Z}_{p^n}[X]$ of degree $d$ the Boolean complexity of calculation of one its root (if it exists) equals $O(dM(n\lambda(p)))$ for fixed prime $p$ and growing $n$, where $\lambda(p)=\lceil\log_2p\rceil,$ $M(n)$ is the Boolean complexity of multiplication of two binary $n$-bit numbers. Given the known decomposition of this number into prime factors $n=m_1\ldots m_k,$ $m_i=p_i^{n_i},$ $i=1,\ldots,k,$ fixed $k,$ fixed prime $p_i,$ $i=1,\ldots,k,$ and growing $n$, the Boolean complexity of calculation of one of solutions to the comparison $f(x)=0\bmod{n}$ equals $O(dM(\lambda(n))).$ In particular, the same estimate is obtained for calculation of one root of any given degree in the residue ring $\mathbb{Z}_{m}.$ As a corollary, we obtained that the Boolean complexity of calculation of integer roots of the polynomial $f(x)$ is equal to $O_d(M(n))$ if $f(x)=a_dx^d+a_{d-1}x^{d-1}+ \ldots+a_0,$ $a_i\in{\mathbb Z},$ $\vert a_i\vert< 2^n,$ $i=0,\ldots, d.$

Key words: polynomial equations over ring of integer numbers and finite rings, Boolean complexity.

Funding Agency Grant Number
Russian Foundation for Basic Research 19-01-00294
18-01-00337


Full text: PDF file (274 kB)
References: PDF file   HTML file

English version:
Moscow University Mathematics Bulletin, 2019, 74:1, 5–13

Bibliographic databases:

UDC: 519.95
Received: 14.03.2018

Citation: S. B. Gashkov, I. B. Gashkov, A. B. Frolov, “The complexity of solving low degree equations over ring of integers and residue rings”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2019, no. 1, 7–15; Moscow University Mathematics Bulletin, 74:1 (2019), 5–13

Citation in format AMSBIB
\Bibitem{GasGasFro19}
\by S.~B.~Gashkov, I.~B.~Gashkov, A.~B.~Frolov
\paper The complexity of solving low degree equations over ring of integers and residue rings
\jour Vestnik Moskov. Univ. Ser.~1. Mat. Mekh.
\yr 2019
\issue 1
\pages 7--15
\mathnet{http://mi.mathnet.ru/vmumm593}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3943129}
\zmath{https://zbmath.org/?q=an:07096704}
\transl
\jour Moscow University Mathematics Bulletin
\yr 2019
\vol 74
\issue 1
\pages 5--13
\crossref{https://doi.org/10.3103/S0027132219010029}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000465628800002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85064927394}


Linking options:
  • http://mi.mathnet.ru/eng/vmumm593
  • http://mi.mathnet.ru/eng/vmumm/y2019/i1/p7

    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:91
    Full text:4
    References:8
    First page:9

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