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.

It was proved that the complexity of square root computation in the Galois field GF(3 (s) ), s = 2 (k) r, is equal to O(M(2 (k) )M(r)k + M(r) log(2) r) + 2 (k) kr (1+o(1)), where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3 (s) ) is equal to O(M(2 (k) )M(r)) and O(M(2 (k) )M(r)) + r (1+o(1)), respectively. If the basis in the field GF(3 (r) ) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2 (k) kr (1+o(1)) and r (1+o(1)) can be omitted. For M(n) one may take n log(2) n psi(n) where psi(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O (r) (M (s) log (2) s) = s (log (2) s)(2) psi(s).