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., 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
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-0029418-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

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}