scientific article; zbMATH DE number 18647

From MaRDI portal
Publication:3976052





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











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976052)