Complexity of computation in finite fields

DOI10.1007/S10958-013-1350-5zbMATH Open1310.94241OpenAlexW2093712108MaRDI QIDQ378003FDOQ378003

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

Publication date: 20 November 2013

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-013-1350-5

Recommendations

• On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic 2
• The computational efficacy of finite-field arithmetic
• Inversion in finite fields using logarithmic depth
• An application of the method of additive chains to inversion in finite fields
• The complexity and depth of Boolean circuits for multiplication and inversion in some fields \(\mathrm{GF}(2^{n})\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Finite fields (field-theoretic aspects) (12E20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A fast algorithm for computing multiplicative inverses in \(\text{GF}(2^ m)\) using normal bases
• On fast multiplication of polynomials over arbitrary algebras
• Fast multiplication of polynomials over fields of characteristic 2
• Shallow circuits and concise formulae for multiple addition and multiplication
• Fast multiplication of large numbers
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Title not available (Why is that?)
• New upper bounds on the Boolean circuit complexity of symmetric functions
• Title not available (Why is that?)
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Fast Algorithms for Manipulating Formal Power Series
• On addition chains
• Efficient pairing computation on supersingular abelian varieties
• Advances in Elliptic Curve Cryptography
• The Computational Complexity of Continued Fractions
• Title not available (Why is that?)
• An implementation for a fast public-key cryptosystem
• Faster integer multiplication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Advances in Cryptology - ASIACRYPT 2003
• A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast rectangular matrix multiplication and applications
• Title not available (Why is that?)
• Optimal normal bases in \(GF(p^ n)\)
• Arithmetic operations in \(GF(2^ m)\)
• Finite field towers: Iterated presentation and complexity of arithmetic.
• On the number of trace-one elements in polynomial bases for \({\mathbb F}_{2^n}\)
• The complexity and depth of Boolean circuits for multiplication and inversion in some fields \(\mathrm{GF}(2^{n})\)
• Fast computation of continued fraction expansions.
• Inversion in finite fields using logarithmic depth
• Title not available (Why is that?)
• On fast multiplication of polynomials, the Fourier and Hartley transforms
• Shimura modular curves and asymptotic symmetric tensor rank of multiplication in any finite field
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sharpening an upper bound on the adder and comparator depths
• On design of circuits of logarithmic depth for inversion in finite fields
• Title not available (Why is that?)
• Optimal tower fields
• Number-theoretic algorithms in cryptography. Transl. from the Russian by A. Martsinkovsky
• Very Fast Parallel Polynomial Arithmetic
• Optimal Size Integer Division Circuits
• Complexity of Boolean schemes for arithmetic in some towers of finite fields
• Efficient Modular Arithmetic in Adapted Modular Number System Using Lagrange Representation
• Efficient Hardware for the Tate Pairing Calculation in Characteristic Three
• Type-II optimal polynomial bases
• Title not available (Why is that?)
• Log Depth Circuits for Division and Related Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast computation of GCDs
• On the Evaluation of Powers
• Normal bases via general Gauss periods
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Subquadratic-time factoring of polynomials over finite fields
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a quick multiplication in normal bases of finite fields
• Title not available (Why is that?)
• An application of the method of additive chains to inversion in finite fields
• On Schönhage's algorithm and subquadratic integer gcd computation
• Algorithmic Number Theory
• On the depth of logic circuits for operations in the fields \(\text{GF}(2^n)\)
• Information Security and Privacy
• Selected Areas in Cryptography
• Title not available (Why is that?)
• The Solvability of the Derivability Problem for One-Normal Systems
• Remarks on number theory III. On addition chains
• Majority Gate Networks
• An improved parallel algorithm for integer GCD
• Algebraic complexities and algebraic curves over finite fields
• Efficient arithmetic in finite field extensions with application in elliptic curve cryptography.
• Fast arithmetic with general Gauß periods
• An extension of TYT algorithm for \(GF((2^n)^m)\) using precomputation
• Polynomial basis multiplication over \(\text{GF}(2^m)\)
• Efficient hardware implementation of finite fields with applications to cryptography
• On arithmetical algorithms over finite fields
• Low complexity normal bases for \(F_{2^{mn}}\)
• Low complexity normal bases

Cited In (16)

• Complexity of Boolean schemes for arithmetic in some towers of finite fields
• On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic 2
• Title not available (Why is that?)
• The computational efficacy of finite-field arithmetic
• Cryptanalysis of schemes based on pseudoinverse matrix
• Cryptanalysis of Cramer-Shoup like cryptosystems based on index exchangeable family
• One-tape Turing machine and branching program lower bounds for MCSP
• The complexity of computing all subfields of an algebraic number field
• Title not available (Why is that?)
• Boolean circuits versus arithmetic circuits
• Can a light typing discipline be compatible with an efficient implementation of finite fields inversion?
• A redundant representation of GF(qⁿ) for designing arithmetic circuits
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nearly optimal pseudorandomness from hardness
• A linear algebra attack on the non-commuting cryptography class based on matrix power function

This page was built for publication: Complexity of computation in finite fields

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