Complexity of computation in finite fields

DOI10.1007/s10958-013-1350-5zbMath1310.94241MaRDI QIDQ378003

Sergey B. Gashkov, Igor 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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

11T71: Algebraic coding theory; cryptography (number-theoretic aspects)

12E20: Finite fields (field-theoretic aspects)

Related Items

Cryptanalysis of Cramer-Shoup Like Cryptosystems Based on Index Exchangeable Family, Cryptanalysis of schemes based on pseudoinverse matrix, A Linear Algebra Attack on the Non-commuting Cryptography Class Based on Matrix Power Function

Cites Work

• An improved parallel algorithm for integer GCD
• 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
• New upper bounds on the Boolean circuit complexity of symmetric functions
• Optimal normal bases in \(GF(p^ n)\)
• A fast algorithm for computing multiplicative inverses in \(\text{GF}(2^ m)\) using normal bases
• On fast multiplication of polynomials over arbitrary algebras
• Arithmetic operations in \(GF(2^ m)\)
• Fast multiplication of polynomials over fields of characteristic 2
• Fast rectangular matrix multiplication and applications
• Shallow circuits and concise formulae for multiple addition and multiplication
• Finite field towers: Iterated presentation and complexity of arithmetic.
• An implementation for a fast public-key cryptosystem
• Efficient pairing computation on supersingular abelian varieties
• 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 multiplication of large numbers
• Fast computation of continued fraction expansions.
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Inversion in finite fields using logarithmic depth
• On fast multiplication of polynomials, the Fourier and Hartley transforms
• Shimura Modular Curves and Asymptotic Symmetric Tensor Rank of Multiplication in any Finite Field
• On design of circuits of logarithmic depth for inversion in finite fields
• The Computational Complexity of Continued Fractions
• Optimal tower fields
• Very Fast Parallel Polynomial Arithmetic
• Optimal Size Integer Division Circuits
• 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
• Log Depth Circuits for Division and Related Problems
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Fast computation of GCDs
• On the Evaluation of Powers
• Fast Algorithms for Manipulating Formal Power Series
• Normal bases via general Gauss periods
• Subquadratic-time factoring of polynomials over finite fields
• On a quick multiplication in normal bases of finite fields
• An application of the method of additive chains to inversion in finite fields
• On Schönhage's algorithm and subquadratic integer gcd computation
• Advances in Elliptic Curve Cryptography
• Algorithmic Number Theory
• Information Security and Privacy
• Selected Areas in Cryptography
• The Solvability of the Derivability Problem for One-Normal Systems
• Remarks on number theory III. On addition chains
• Majority Gate Networks
• On addition chains
• Advances in Cryptology - ASIACRYPT 2003
• Algebraic complexities and algebraic curves over finite fields
• Efficient arithmetic in finite field extensions with application in elliptic curve cryptography.
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item