О сложности решения уравнений малой степени в кольце целых чисел и кольцах вычетов

Доказано, что для произвольного многочлена $f(x)\in\mathbb{Z}_{p^n}[X]$ степени $d$ битовая сложность вычисления одного корня (если он есть) при фиксированном простом $p$ и растущем $n$ равна $O(dM(n\lambda(p))),$ где $\lambda(p)=\lceil\log_2p\rceil,$ $M(n)$ — битовая сложность умножения двоичных $n$-битных чисел. При известном разложении на простые множители данного числа $n=m_1\ldots m_k,$ $m_i=p_i^{n_i},$ $i=1,\ldots,k,$ фиксированном $k,$ фиксированных простых $p_i,$ $i=1,\ldots,k,$ и растущем $n$ битовая сложность вычисления одного из решений сравнения $f(x)=0\bmod{n}$ равна $O(dM(\lambda(n))).$ В частности, такая же оценка получается для извлечения одного корня любой заданной степени в кольце вычетов $\mathbb{Z}_{m}.$ Как следствие получено, что битовая сложность вычисления целых корней многочлена $f(x)$ равна $O_d(M(n)),$ если $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.$