A Lower Bound on the Complexity of Division in Finite Extension Fields and Inversion in Quadratic Alternative Algebras

DOI10.1137/0218013MaRDI QIDQ3835017zbMATH OpenOpenAlexFDO

Authors Thomas Lickteig

Publication date 1989

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0218013

zbMATH Keywords

adjunction of intermediate results to the groundfield and approximative complexityarithmetic in finite extension fieldsOstrowski complexitysubstitution method

Mathematics Subject Classification ID

Algebraic field extensions (12F05) Quadratic algebras (but not quadratic Jordan algebras) (17A45) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• The Computational Complexity of Division in Quadratic Extension Fields
• The equivariant complexity of multiplication in finite field extensions
• STACS 2005
• A Lower Bound on the Complexity of Polynomial Multiplication over Finite Fields
• Semi-algebraic complexity of quotients and sign determination of remainders
• Finite-Dimensional Division Algebras over Fields
• Low increasing tower of algebraic function fields and bilinear complexity of multiplication in any extension of F_q
• Complexity bounds for the rational Newton-Puiseux algorithm over finite fields
• On the bounds of the bilinear complexity of multiplication in some finite fields
• On upper bound of the complexity of quasi polynomial representations of functions over finite fields

Cited in

(4)

• On the multiplicative complexity of the inversion and division of Hamiltonian quaternions
• The Computational Complexity of Division in Quadratic Extension Fields
• On the field-based division property: applications to MiMC, Feistel MiMC and GMiMC
• Inversion operations in algebraic structures

This page was built for publication: A Lower Bound on the Complexity of Division in Finite Extension Fields and Inversion in Quadratic Alternative Algebras

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