The parallel complexity of exponentiating polynomials over finite fields

DOI10.1145/44483.44496zbMath0652.68032OpenAlexW2062101007MaRDI QIDQ3798223

Martin Tompa, Faith E. Fich

Publication date: 1988

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/44483.44496

zbMATH Keywords

parallel algorithmalgebraic complexitypolynomials over finite field\(NC^ 2\)modular polynomial exponentiation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials over finite fields (11T06) Software, source code, etc. for problems pertaining to field theory (12-04)

Related Items (8)

Equality Testing of Compressed Strings ⋮ Inversion in finite fields using logarithmic depth ⋮ Boolean circuits versus arithmetic circuits ⋮ A generalisation of Brickell's algorithm for fast modular multiplication ⋮ Encroaching lists as a measure of presortedness ⋮ The iterated mod problem ⋮ Parallel Identity Testing for Skew Circuits with Big Powers and Applications ⋮ Efficient and optimal exponentiation in finite fields

This page was built for publication: The parallel complexity of exponentiating polynomials over finite fields