It is proved that for an arbitrary polynomial f(x)Zpn[X] of degree d the Boolean complexity of calculation of one its root (if it exists) equals O(dM(n(p))) for a fixed prime p and growing n, where (p) = remvoelog(2)p, and 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)...m(k), mi=pini, i = 1,..., k, with fixed k and primes p(i), i = 1,..., k, and growing n, the Boolean complexity of calculation of one of solutions to the comparison f(x) = 0 mod n equals O(dM((n))). In particular, the same estimate is obtained for calculation of one root of any given degree in the residue ring Z(m). As a corollary, it is proved that the Boolean complexity of calculation of integer roots of a polynomial f(x) is equal to O-d(M(n)), where f(x)=adxd+ad-1xd-1+...+a0,aiZ , |a(i)| < 2(n), i = 0,..., d.