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
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
- 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
- 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
