A new efficient algorithm for computing Gröbner bases (F₄)
From MaRDI portal
A new efficient algorithm for computing Gröbner bases \((F 4)\)
The first part of the paper contains the description and theoretical foundations of a new, implementation oriented algorithmic method for the computation of Gröbner bases of polynomial ideals. Degree-truncated Gröbner basis computations, sparse linear algebra routines and parallel computing are used in order to speed up the classical Buchberger algorithm (in the past these tools were only applied to the theoretical worst case complexity analysis of this algorithm). The new procedure combines term rewriting with linear algebra. Its main feature consists in the simultaneous reduction of several polynomials modulo a precomputed list of them. This is done in a parallel way, using sparse linear algebra routines. This aspect of massive parallel computation distinguishes the new procedure from the classical Buchberger algorithm. The paper ends with a comparison of the implemented version of the new algorithm (the program FGb) with its forerunner Gb and some of its competitors. The author claims that the program FGb behaves almost optimally with respect to time complexity. Time seems to be almost proportional to the (objective) output size.
Recommendations
Cites work
- An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
- Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems
- Exact solution of linear equations using p-adic expansions
- Graph theory and sparse matrix computation. Proceedings of a workshop that was an integral part of the 1991-92 IMA program on Applied linear algebra, Minneapolis, MN (USA)
- scientific article; zbMATH DE number 1676636 (Why is no real title available?)
- scientific article; zbMATH DE number 3649988 (Why is no real title available?)
- scientific article; zbMATH DE number 3857249 (Why is no real title available?)
- scientific article; zbMATH DE number 3816913 (Why is no real title available?)
- scientific article; zbMATH DE number 3941661 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 52062 (Why is no real title available?)
- scientific article; zbMATH DE number 177858 (Why is no real title available?)
- scientific article; zbMATH DE number 3639058 (Why is no real title available?)
- scientific article; zbMATH DE number 1263402 (Why is no real title available?)
- scientific article; zbMATH DE number 1273640 (Why is no real title available?)
- scientific article; zbMATH DE number 1304276 (Why is no real title available?)
- scientific article; zbMATH DE number 503245 (Why is no real title available?)
- scientific article; zbMATH DE number 554768 (Why is no real title available?)
- scientific article; zbMATH DE number 691245 (Why is no real title available?)
- scientific article; zbMATH DE number 217454 (Why is no real title available?)
- scientific article; zbMATH DE number 3368076 (Why is no real title available?)
- On an installation of Buchberger's algorithm
- Parallel Sparse LU Decomposition on a Mesh Network of Transputers
- Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution
- Résolution des systèmes d'équations algébriques
- Shift-register synthesis and BCH decoding
- Solving sparse linear equations over finite fields
- Strategy-accurate parallel Buchberger algorithms
- The Multifrontal Solution of Unsymmetric Sets of Linear Equations
Cited in
(only showing first 100 items - show all)- Thirty years of polynomial system solving, and now?
- Solving multiple right hand sides linear equations
- Certifying properties of an efficient functional program for computing Gröbner bases
- Polybori: A framework for Gröbner-basis computations with Boolean polynomials
- On an installation of Buchberger's algorithm
- Numerical homotopies to compute generic points on positive dimensional algebraic sets
- Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields
- A stabilized normal form algorithm for generic systems of polynomial equations
- Computing comprehensive Gröbner systems: a comparison of two methods
- The point decomposition problem over hyperelliptic curves, Toward efficient computation of discrete logarithms in even characteristic
- On the last fall degree of zero-dimensional Weil descent systems
- Resultant elimination via implicit equation interpolation
- Cryptanalysis of matrix-based UOV
- Key recovery attack on the cubic ABC Simple Matrix Multivariate Encryption Scheme
- Solving a binary puzzle
- Sparse FGLM algorithms
- A survey on signature-based algorithms for computing Gröbner bases
- A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over \(\mathbb{Z} [x]\)
- Characteristic decomposition: from regular sets to normal sets
- Speeding up the GVW algorithm via a substituting method
- Algebraic geometry and Bethe ansatz. I: The quotient ring for BAE
- Complexity of Gröbner basis detection and border basis detection
- Recovering an algebraic curve using its projections from different points. Applications to static and dynamic computational vision
- Syzygies among reduction operators
- Numerical algebraic geometry: a new perspective on gauge and string theories
- Cyclic codes and minimal strong Gröbner bases over a principal ideal ring.
- Computing all nonsingular solutions of cyclic-n polynomial using polyhedral homotopy continuation methods
- Multivariate public key cryptosystems from Diophantine equations
- Elliptic curve discrete logarithm problem over small degree extension fields
- Slimgb: Gröbner bases with slim polynomials
- Usage of modular techniques for efficient computation of ideal operations
- Counting points on hyperelliptic curves of type \(y^2=x^{2g+1}+ax^{g+1}+bx\)
- Certified non-conservative tests for the structural stability of discrete multidimensional systems
- On the first fall degree of summation polynomials
- On the use of Buchberger criteria in \(\mathrm G^2\mathrm V\) algorithm for calculating Gröbner bases
- Complexity bounds on Semaev's naive index calculus method for ECDLP
- A comparison of unrestricted dynamic Gröbner basis algorithms
- A dynamic F4 algorithm to compute Gröbner bases
- A generic and executable formalization of signature-based Gröbner basis algorithms
- Solving non-linear Boolean equation systems by variable elimination
- Cryptanalysis of the extension field cancellation cryptosystem
- Efficiently and effectively recognizing toricity of steady state varieties
- Relative Gröbner and involutive bases for ideals in quotient rings
- An algebraic attack on rank metric code-based cryptosystems
- The nested subset differential attack. A practical direct attack against LUOV which forges a signature within 210 minutes
- Cryptanalytic applications of the polynomial method for solving multivariate equation systems over \(\mathrm{GF}(2)\)
- A public key cryptosystem using a group of permutation polynomials
- Analysis of multivariate encryption schemes: application to Dob
- Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
- Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one
- Guessing Gröbner bases of structured ideals of relations of sequences
- Security analysis via algebraic attack against ``a new encryption scheme for multivariate quadratic system
- A study on randomness used in signature generation of UOV
- Symbolic computation for the qualitative theory of differential equations
- The inverse of \(\chi\) and its applications to Rasta-like ciphers
- Geometric algebra and algebraic geometry of loop and Potts models
- Exact solution of a fully general non-local-thermodynamic-equilibrium two-level atom
- Cryptanalysis of the lifted unbalanced oil vinegar signature scheme
- An eigen-representation of the Navier-Stokes equations
- Solving parametric systems of polynomial equations over the reals through Hermite matrices
- Logical cryptanalysis with WDSat
- Improving Thomae-Wolf algorithm for solving underdetermined multivariate quadratic polynomial problem
- New practical multivariate signatures from a nonlinear modifier
- On the effect of projection on rank attacks in multivariate cryptography
- Efficient key recovery for all HFE signature variants
- A Gröbner basis algorithm for ideals over zero-dimensional valuation rings
- Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems
- An improvement for GVW
- (Short paper) Simple matrix signature scheme
- Signature Gröbner bases, bases of syzygies and cofactor reconstruction in the free algebra
- Threaded Gröbner bases: a Macaulay2 package
- Solving degree, last fall degree, and related invariants
- Finding multiple Nash equilibria via machine learning-supported Gröbner bases
- Improved filter permutators for efficient FHE: better instances and implementations
- Quasi-subfield polynomials and the elliptic curve discrete logarithm problem
- Standard bases over Euclidean domains
- Chordal graphs in triangular decomposition in top-down style
- On affine tropical F5 algorithms
- Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases
- Efficient Gröbner bases computation over principal ideal rings
- On the efficiency of solving Boolean polynomial systems with the characteristic set method
- Counting and enumerating feasible rotating schedules by means of Gröbner bases
- On the termination of the general XL algorithm and ordinary multinomials
- Solving multivariate polynomial systems and an invariant from commutative algebra
- Algebraic analysis of stability and bifurcation of a self-assembling micelle system
- Improved agreeing-gluing algorithm
- \(\mathrm{F}_4\)-invariant algorithm for computing SAGBI-Gröbner bases
- The F5 criterion revised
- Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals
- A new encryption scheme for multivariate quadratic systems
- Characterizations of solutions in geochemistry: existence, uniqueness, and precipitation diagram
- Determining whether a given cryptographic function is a permutation of another given cryptographic function -- a problem in intellectual property
- A new signature-based algorithms for computing Gröbner bases
- On the complexity of the \(F_5\) Gröbner basis algorithm
- Cryptanalysis of a noncommutative key exchange protocol
- Linear algebraic approach to Gröbner-Shirshov basis theory
- Stable normal forms for polynomial system solving
- A Groebner bases-based approach to backward reasoning in rule based expert systems
- Local reduction and the algebraic cryptanalysis of the block cipher GOST
- Superspecial curves of genus 4 in small characteristic
This page was built for publication: A new efficient algorithm for computing Gröbner bases \((F_4)\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1295781)
