Circuit complexity of powering in fields of odd characteristic

DOI10.4086/CJTCS.2016.010MaRDI QIDQ3187179zbMATH OpenOpenAlexFDO

Authors Arkadev Chattopadhyay, Frederic Green, Howard Straubing

Publication date 16 August 2016

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/cjtcs.2016.010

zbMATH Keywords

circuit complexityexponential sumsfinite fieldslower bounds

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the complexity of powering in finite fields
• Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
• Powering requires threshold depth 3
• Estimation of certain exponential sums arising in complexity theory
• Efficient and optimal exponentiation in finite fields

Cites work

• scientific article; zbMATH DE number 2121181 (Why is no real title available?)
• On the complexity of powering in finite fields

Cited in

(1)

• On the complexity of powering in finite fields

This page was built for publication: Circuit complexity of powering in fields of odd characteristic

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