Inversion in finite fields using logarithmic depth

DOI10.1016/S0747-7171(08)80028-4zbMath0717.68040MaRDI QIDQ2638778

Joachim von zur Gathen

Publication date: 1990

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

reductions; Boolean circuits; Boolean theory; arithmetic theory; complexity classes \(NC^ 1\); complexity classes \(NC^ k_ F\)

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Complexity of computation in finite fields, Efficient and optimal exponentiation in finite fields, Boolean circuits versus arithmetic circuits, On design of circuits of logarithmic depth for inversion in finite fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial division and its computational complexity
• Boolean circuits versus arithmetic circuits
• Parallel Algorithms for Algebraic Problems
• Parallel Solution of Certain Toeplitz Linear Systems
• Very Fast Parallel Polynomial Arithmetic
• Factoring Polynomials over Algebraic Number Fields
• A taxonomy of problems with fast parallel algorithms
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Logarithmic Depth Circuits for Algebraic Functions
• Log Depth Circuits for Division and Related Problems
• Computing Powers in Parallel
• The parallel complexity of exponentiating polynomials over finite fields
• Fast parallel matrix and GCD computations