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

S. B. Gashkov ; I. B. Gashkov ; A. B. Frolov

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2019), pp. 7-15

Résumé

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