On the complexity of the \(F_5\) Gröbner basis algorithm
From MaRDI portal
Publication:2343240
DOI10.1016/j.jsc.2014.09.025zbMath1328.68319arXiv1312.1655OpenAlexW2963833429MaRDI QIDQ2343240
Bruno Salvy, Magali Bardet, Jean-Charles Faugère
Publication date: 4 May 2015
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.1655
Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)
Related Items (38)
Stream/block ciphers, difference equations and algebraic attacks ⋮ Security analysis of a cryptosystem based on subspace subcodes ⋮ On probabilistic algorithm for solving almost all instances of the set partition problem ⋮ On the complexity exponent of polynomial system solving ⋮ Finding multiple Nash equilibria via machine learning-supported Gröbner bases ⋮ Tensor product of evolution algebras ⋮ Moderate classical McEliece keys from quasi-centrosymmetric Goppa codes ⋮ A Direttissimo Algorithm for Equidimensional Decomposition ⋮ Conormal spaces and Whitney stratifications ⋮ From 5-Pass $$\mathcal {MQ}$$-Based Identification to $$\mathcal {MQ}$$-Based Signatures ⋮ Refined F5 Algorithms for Ideals of Minors of Square Matrices ⋮ An estimator for the hardness of the MQ problem ⋮ Gröbner bases of reaction networks with intermediate species ⋮ MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity ⋮ Worst-case subexponential attacks on PRGs of constant degree or constant locality ⋮ On the computation of rational solutions of underdetermined systems over a finite field ⋮ Axioms for a theory of signature bases ⋮ Distance to the loss of structural properties for linear systems under parametric uncertainties ⋮ The complexity of solving Weil restriction systems ⋮ Spectral norm of a symmetric tensor and its computation ⋮ Learning with physical rounding for linear and quadratic leakage functions ⋮ Dimension results for extremal-generic polynomial systems over complete toric varieties ⋮ Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases ⋮ Sparse FGLM algorithms ⋮ PLS-based adaptation for efficient PCE representation in high dimensions ⋮ EFLASH: a new multivariate encryption scheme ⋮ Speeding up the GVW algorithm via a substituting method ⋮ Solving multivariate polynomial systems and an invariant from commutative algebra ⋮ Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals ⋮ Block-Krylov techniques in the context of sparse-FGLM algorithms ⋮ Cryptanalysis of the extension field cancellation cryptosystem ⋮ Indistinguishability obfuscation without maps: attacks and fixes for noisy linear FE ⋮ An algebraic attack on rank metric code-based cryptosystems ⋮ \textsc{Ciminion}: symmetric encryption based on Toffoli-gates over large finite fields ⋮ A signature-based algorithm for computing Gröbner bases over principal ideal domains ⋮ Nœther bases and their applications ⋮ Algorithm for studying polynomial maps and reductions modulo prime number ⋮ Solving parametric systems of polynomial equations over the reals through Hermite matrices
Uses Software
Cites Work
- 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
- Combinatorial dimension theory of algebraic varieties
- Matrix multiplication via arithmetic progressions
- EUROCAL '85. European Conference on Computer Algebra, Linz, Austria, April 1-3, 1985. Proceedings. Vol. 2: Research contributions
- A new efficient algorithm for computing Gröbner bases \((F_4)\)
- Efficient computation of zero-dimensional Gröbner bases by change of ordering
- The Projective Noether Maple Package: Computing the dimension of a projective variety
- The complexity of the word problems for commutative semigroups and polynomial ideals
- Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases
- SHARPER COMPLEXITY BOUNDS FOR ZERO-DIMENSIONAL GRÖBNER BASES AND POLYNOMIAL SYSTEM SOLVING
- Powers of tensors and fast matrix multiplication
- The Structure of Polynomial Ideals and Gröbner Bases
- A superexponential lower bound for Gröbner bases and Church-Rosser commutative thue systems
- Using Algebraic Geometry
- Modifying Faugère's F5 algorithm to ensure termination
- Multiplying matrices faster than coppersmith-winograd
- Advances in Cryptology - CRYPTO 2003
- FGb: A Library for Computing Gröbner Bases
- A Gröbner free alternative for polynomial system solving
This page was built for publication: On the complexity of the \(F_5\) Gröbner basis algorithm
