scientific article; zbMATH DE number 18647
[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.
- Massively parallel computations on many-variable polynomials
- Modular exponentiation via the explicit Chinese remainder theorem
- Very Fast Parallel Polynomial Arithmetic
- scientific article; zbMATH DE number 5627530 (Why is no real title available?)
- Computing Powers in Parallel
- scientific article; zbMATH DE number 4062581 (Why is no real title available?)
- The parallel complexity of exponentiating polynomials over finite fields
- scientific article; zbMATH DE number 4128395 (Why is no real title available?)
- scientific article; zbMATH DE number 3999284 (Why is no real title available?)
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)