The complexity and depth of Boolean circuits for multiplication and inversion in some fields GF(2ⁿ)

DOI10.3103/S0027132209040019MaRDI QIDQ2513076zbMATH OpenOpenAlexFDO

Authors S. B. Gashkov, I. S. Sergeev

Publication date 2 February 2015

Published in Moscow University Mathematics Bulletin (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/s0027132209040019

Mathematics Subject Classification ID

Continued fractions (11A55) Finite fields (field-theoretic aspects) (12E20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic 2
• On the depth of logic circuits for operations in the fields \(\text{GF}(2^n)\)
• Circuit complexity and multiplicative complexity of Boolean functions
• On the multiplicative complexity of some Boolean functions
• Complexity of Boolean schemes for arithmetic in some towers of finite fields
• scientific article; zbMATH DE number 4108153
• On the multiplicative complexity of Boolean functions
• On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).
• On the complexity of circuit realization of Boolean functions in an infinite basis
• On design of circuits of logarithmic depth for inversion in finite fields

Cites work

• An application of the method of additive chains to inversion in finite fields
• Complexity of Boolean schemes for arithmetic in some towers of finite fields
• Fast computation of continued fraction expansions.
• Fast multiplication of polynomials over fields of characteristic 2
• Finite field towers: Iterated presentation and complexity of arithmetic.
• Modern computer algebra
• Optimal tower fields
• The Computational Complexity of Continued Fractions

Cited in

(6)

• Fast algorithms for solving equations of degree \(\le 4\) in some finite fields
• On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic 2
• Complexity of Boolean schemes for arithmetic in some towers of finite fields
• Complexity of computation in finite fields
• On the depth of logic circuits for operations in the fields \(\text{GF}(2^n)\)
• On the complexity of parallel algorithms for computing inverses in \(\text{GF}(2^m)\) with \(m\) prime

This page was built for publication: The complexity and depth of Boolean circuits for multiplication and inversion in some fields \(\mathrm{GF}(2^{n})\)

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