Geodesic
The complexity of solving low degree equations over ring of integers and residue rings
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2019), pp. 7-15 
S. B. Gashkov; I. B. Gashkov; A. B. Frolov. The complexity of solving low degree equations over ring of integers and residue rings. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2019), pp. 7-15. http://geodesic.mathdoc.fr/item/VMUMM_2019_1_a1/
@article{VMUMM_2019_1_a1,
     author = {S. B. Gashkov and I. B. Gashkov and A. B. Frolov},
     title = {The complexity of solving low degree equations over ring of integers and residue rings},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {7--15},
     year = {2019},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2019_1_a1/}
}
TY  - JOUR
AU  - S. B. Gashkov
AU  - I. B. Gashkov
AU  - A. B. Frolov
TI  - The complexity of solving low degree equations over ring of integers and residue rings
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2019
SP  - 7
EP  - 15
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2019_1_a1/
LA  - ru
ID  - VMUMM_2019_1_a1
ER  - 
%0 Journal Article
%A S. B. Gashkov
%A I. B. Gashkov
%A A. B. Frolov
%T The complexity of solving low degree equations over ring of integers and residue rings
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2019
%P 7-15
%N 1
%U http://geodesic.mathdoc.fr/item/VMUMM_2019_1_a1/
%G ru
%F VMUMM_2019_1_a1

Voir la notice de l'article provenant de la source Math-Net.Ru

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.$

[1] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. A., Elementarnoe vvedenie v ellipticheskuyu kriptografiyu. Algebraicheskie i algoritmicheskie osnovy, URSS Lenand, M., 2018

[2] Vasilenko O. N., Teoretiko-chislovye algoritmy v kriptografii, MTsNMO, M., 2003

[3] Glukhov M. M., Kruglov I. A., Pichkur A. B., Cheremushkin A. V., Vvedenie v teoretiko-chislovye metody kriptografii, Lan, SPb., 2011

[4] Bach E., “Explicit bounds for primality testing and related problems”, Math. Comput., 22 (1989), 355–380 | MR

[5] Fuerer M., “Faster integer multiplication”, SIAM J. Comput., 39:3 (2009), 979–1005 | DOI | MR | Zbl

[6] Harvey D., van der Hoeven J., Lecerf G., Faster polynomial multiplication over finite fields, 12 Jul 2014, arXiv: 1407.3361 | MR

[7] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979

[8] Gashkov S. B., Chubarikov V. H., Arifmetika. Algoritmy. Slozhnost vychislenii, Nauka, M., 1996

[9] Gashkov S. B., “O slozhnosti integrirovaniya ratsionalnykh drobei”, Tr. Matem. in-ta RAN, 218, 1997, 122–133 | Zbl

[10] Zassenhaus H., “A remark on the Hensel factorization method”, Math. Comput., 32:141 (1978), 287–292 | DOI | MR | Zbl

[11] Lenstra A., Lenstra H., Lovasz L., “Factoring polynomials with rational coefficients”, Math. Ann., 261 (1982), 515–534 | DOI | MR | Zbl

[12] Vinogradov I. M., Osnovy teorii chisel, GITTL, M., 1952 | MR