No label defined (Q3976052)

[For the entire collection see Zbl 0731.00026.] Very fast parallel algorithms involved in polynomial computations over finite fields are presented. The author discusses the connection between the computation of the inverse and the Chinese Remainder Theorem. He emphasizes on the improved modular exponentiation of \textit{J. von zur Gathen} [SIAM J. Comput. 16, 930-945 (1987; Zbl 0636.68034)] and \textit{F. E. Fich} and \textit{M. Tompa} [J. Assoc. Comput. Math. 35, 651-667 (1988; Zbl 0652.68032)]. A log-space uniform family of Boolean circuits is obtained having simultaneously depth \(O(\log n \log\log n)\) and size \(O(n^{o(1)})\) that computes large polynomial powers in case that the modulus has only small prime factors. All the algorithms considered yield \(P\)-uniform families of Boolean circuits having the optimal depth \(O(\log n)\) and polynomial size.