A new efficient algorithm for computing Gröbner bases \((F_4)\)

From MaRDI portal

Publication:1295781

Jump to:navigation, search

DOI10.1016/S0022-4049(99)00005-5zbMath0930.68174OpenAlexW2128687423WikidataQ29392345 ScholiaQ29392345MaRDI QIDQ1295781

Jean-Charles Faugère

Publication date: 10 January 2000

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-4049(99)00005-5

zbMATH Keywords

Buchberger algorithm computation of Gröbner bases of polynomial ideals

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Related Items

Structural cryptanalysis of McEliece schemes with compact keys, Computing border bases, On multivariable encryption schemes based on simultaneous algebraic Riccati equations over finite fields, Stream/block ciphers, difference equations and algebraic attacks, Stronger bounds on the cost of computing Gröbner bases for HFE systems, Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields, Polly cracker, revisited, MaxMinMax problem and sparse equations over finite fields, Testing binomiality of chemical reaction networks using comprehensive Gröbner systems, On index calculus algorithms for subfield curves, Boolean polynomials, BDDs and CRHS equations -- connecting the dots with CryptaPath, The F5 algorithm in Buchberger's style, Involutive method for computing Gröbner bases over \(\mathbb F_2\), Role of involutive criteria in computing Boolean Gröbner bases, Exploring the potential energy landscape over a large parameter-space, Matrix-F5 algorithms and tropical Gröbner bases computation, A stabilized normal form algorithm for generic systems of polynomial equations, Fast and stable polynomial equation solving and its application to computer vision, A signature-based algorithm for computing Gröbner-Shirshov bases in skew solvable polynomial rings., Competitive equilibria in semi-algebraic economies, On implementing the symbolic preprocessing function over Boolean polynomial rings in Gröbner basis algorithms using linear algebra, Computing comprehensive Gröbner systems: a comparison of two methods, Resolution of a system of fuzzy polynomial equations using eigenvalue method, Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic, Stability analysis for discrete biological models using algebraic methods, Representing and solving finite-domain constraint problems using systems of polynomials, Gröbner bases and wavelet design, A new proof for the correctness of the F5 algorithm, The point decomposition problem over hyperelliptic curves, Toward efficient computation of discrete logarithms in even characteristic, Extended \(F_5\) criteria, F5C: A variant of Faugère's F5 algorithm with reduced Gröbner bases, Invariant \(\mathrm G^2\mathrm V\) algorithm for computing SAGBI-Gröbner bases, On the complexity of the generalized MinRank problem, On the determination of cusp points of 3-RPR parallel manipulators, Projective interpolation of polynomial vectors and improved key recovery attack on SFLASH, First fall degree and Weil descent, Index calculus in the trace zero variety, On the last fall degree of zero-dimensional Weil descent systems, Resultant elimination via implicit equation interpolation, Characteristic set algorithms for equation solving in finite fields, Real root finding for determinants of linear matrices, On the relation between the MXL family of algorithms and Gröbner basis algorithms, Optimising Gröbner bases on Bivium, Obtaining and solving systems of equations in key variables only for the small variants of AES, On the topology of real algebraic plane curves, Cryptanalysis of matrix-based UOV, Variant quantifier elimination, Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity, Artificial discontinuities of single-parametric Gröbner bases, Isochronicity conditions for some planar polynomial systems. II., Key recovery attack on the cubic ABC Simple Matrix Multivariate Encryption Scheme, Generating invariants for non-linear loops by linear algebraic methods, Triangularizing kinematic constraint equations using Gröbner bases for real-time dynamic simulation, The F\(_{4}\)-algorithm for Euclidean rings, Computing inhomogeneous Gröbner bases, Solving a binary puzzle, Applying IsRewritten criterion on Buchberger algorithm, Sparse FGLM algorithms, A survey on signature-based algorithms for computing Gröbner bases, On selection of nonmultiplicative prolongations in computation of Janet 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, Computing modular correspondences for abelian varieties, Delsarte method in the problem on kissing numbers in high-dimensional spaces, Using symmetries in the index calculus for elliptic curves discrete logarithm, Distortion varieties, SimpleMatrix -- a multivariate public key cryptosystem (MPKC) for encryption, Analysis of codimension 2 bifurcations for high-dimensional discrete systems using symbolic computation methods, Algebraic cryptanalysis of stream ciphers using decomposition of Boolean function, Parametric FGLM algorithm, Algebraic geometry and Bethe ansatz. I: The quotient ring for BAE, Solving polynomial systems with noise over \(\mathbb{F}_2\): revisited, Pivoting in extended rings for computing approximate Gröbner bases, Solving the 100 swiss francs problem, A quadratic clipping step with superquadratic convergence for bivariate polynomial systems, An improvement over the GVW algorithm for inhomogeneous polynomial systems, Complexity of Gröbner basis detection and border basis detection, A logic-algebraic approach to decision taking in a railway interlocking system, Relations between roots and coefficients, interpolation and application to system solving, Controlled non-uniform random generation of decomposable structures, Recovering an algebraic curve using its projections from different points. Applications to static and dynamic computational vision, Determining the global minimum of Higgs potentials via Groebner bases - applied to the NMSSM, A generalization of Castelnuovo-Mumford regularity for representations of noncommutative algebras., Syzygies among reduction operators, On the decoding of binary cyclic codes with the Newton identities, Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem, QUAD: A multivariate stream cipher with provable security, Numerical elimination and moduli space of vacua, Thirty years of polynomial system solving, and now?, Improvement of FPPR method to solve ECDLP, Solving multiple right hand sides linear equations, Reducing the size and number of linear programs in a dynamic Gröbner basis algorithm, Certifying properties of an efficient functional program for computing Gröbner bases, Detecting binomiality, Polybori: A framework for Gröbner-basis computations with Boolean polynomials, Optimized Lie-Trotter-Suzuki decompositions for two and three non-commuting terms, Why you cannot even hope to use Gröbner bases in cryptography: an eternal golden braid of failures, Cylinder partition function of the 6-vertex model from algebraic geometry, Numerical homotopies to compute generic points on positive dimensional algebraic sets, Efficient key recovery for all HFE signature variants, Computing all nonsingular solutions of cyclic-\(n\) polynomial using polyhedral homotopy continuation methods, 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, Linear algebraic approach to Gröbner-Shirshov basis theory, Signature Gröbner bases, bases of syzygies and cofactor reconstruction in the free algebra, Threaded Gröbner bases: a Macaulay2 package, On the security of biquadratic \(C^\ast\) public-key cryptosystems and its generalizations, Stable normal forms for polynomial system solving, A Groebner bases-based approach to backward reasoning in rule based expert systems, Solving degree, last fall degree, and related invariants, Local reduction and the algebraic cryptanalysis of the block cipher GOST, Superspecial curves of genus 4 in small characteristic, Sufficient set of integrability conditions of an orthonomic system, Gröbner bases techniques for an \(S\)-packing \(k\)-coloring of a graph, New complexity estimation on the rainbow-band-separation attack, Finding multiple Nash equilibria via machine learning-supported Gröbner bases, Improved filter permutators for efficient FHE: better instances and implementations, Semi-regularity of pairs of Boolean polynomials, Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics, Torus partition function of the six-vertex model from algebraic geometry, Multivariate public key cryptosystems from Diophantine equations, Quasi-subfield polynomials and the elliptic curve discrete logarithm problem, Gröbner bases of reaction networks with intermediate species, Macaulay matrix for Feynman integrals: linear relations and intersection numbers, Normal forms of planar polynomial differential systems, Pushforwards via scattering equations with applications to positive geometries, On the computation of rational solutions of underdetermined systems over a finite field, Quantum security of grain-128/grain-128a stream cipher against HHL algorithm, The complexity of solving Weil restriction systems, Standard bases over Euclidean domains, Chordal graphs in triangular decomposition in top-down style, On affine tropical F5 algorithms, Elliptic curve discrete logarithm problem over small degree extension fields, Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases, Cryptanalysis of \textsf{LRainbow}: the lifted rainbow signature scheme, Rank-profile revealing Gaussian elimination and the CUP matrix decomposition, Involutive bases algorithm incorporating F\(_5\) criterion, GVW algorithm over principal ideal domains, Efficient Gröbner bases computation over principal ideal rings, On the efficiency of solving Boolean polynomial systems with the characteristic set method, Slimgb: Gröbner bases with slim polynomials, A subresultant-like theory for Buchberger's procedure, Parallelization of matrix algorithms for Gröbner basis computation, 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, Usage of modular techniques for efficient computation of ideal operations, Algebraic analysis of stability and bifurcation of a self-assembling micelle system, Counting points on hyperelliptic curves of type \(y^2=x^{2g+1}+ax^{g+1}+bx\), Improved agreeing-gluing algorithm, Certified non-conservative tests for the structural stability of discrete multidimensional systems, \(\mathrm{F}_4\)-invariant algorithm for computing SAGBI-Gröbner bases, The membrane inclusions curvature equations, 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, The F5 criterion revised, 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, Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals, 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, Weakness of \(\mathbb{F}_{3^{6 \cdot 1429}}\) and \(\mathbb{F}_{2^{4 \cdot 3041}}\) for discrete logarithm cryptography, Numerical algebraic geometry: a new perspective on gauge and string theories, A new encryption scheme for multivariate quadratic systems, Representations of fundamental groups of 3-manifolds into \(\mathrm{PGL}(3,\mathbb C)\): exact computations in low complexity, Fast computation of Gröbner basis of homogeneous ideals of \(\mathbb{F}[x, y\)], 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, Characterizations of solutions in geochemistry: existence, uniqueness, and precipitation diagram, 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, Determining whether a given cryptographic function is a permutation of another given cryptographic function -- a problem in intellectual property, 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, A new signature-based algorithms for computing Gröbner bases, On the complexity of the \(F_5\) Gröbner basis algorithm, Cryptanalysis of the lifted unbalanced oil vinegar signature scheme, Cryptanalysis of a noncommutative key exchange protocol, An eigen-representation of the Navier-Stokes equations, Cyclic codes and minimal strong Gröbner bases over a principal ideal ring., 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, Worst-case subexponential attacks on PRGs of constant degree or constant locality, An improvement of algorithms to solve under-defined systems of multivariate quadratic equations, Development of hybrid approach for solving MQ problem: Intermediate hybrid approach, Cryptanalysis of symmetric primitives over rings and a key recovery attack on \textsf{Rubato}, Axioms for a theory of signature bases, Two-step Newton's method for deflation-one singular zeros of analytic systems, Algebraic attacks on Rasta and Dasta using low-degree equations, \textsc{Rings}: an efficient Java/Scala library for polynomial rings, Acceleration of Index Calculus for Solving ECDLP over Prime Fields and Its Limitation, On the complexity of solving generic overdetermined bilinear systems, Further perspectives on elimination, A new fault attack on UOV multivariate signature scheme, 2F -- a new method for constructing efficient multivariate encryption schemes, Algebraic relation of three MinRank algebraic modelings, Efficient IBS from a new assumption in the multivariate-quadratic setting, Learning with physical rounding for linear and quadratic leakage functions, New design techniques for efficient arithmetization-oriented hash functions: \texttt{Anemoi} permutations and \texttt{Jive} compression mode, Lower bounds on the Lyapunov exponents of stochastic differential equations, On construction of efficient algorithms for solving systems of polynomial Boolean equations by testing a part of variables, A Structural Attack on Block-Anti-Circulant UOV at SAC 2019, Multivariate Encryption Schemes Based on Polynomial Equations over Real Numbers, An improvement of a key exchange protocol relying on polynomial maps, Polynomial selection for computing Gröbner bases, A SAT-Based Approach for Index Calculus on Binary Elliptic Curves, A new framework for computing Gröbner bases, The Big Mother of all Dualities: Möller Algorithm, A Secure Variant of the SRP Encryption Scheme with Shorter Private Key, A New Method for Solving Polynomial Systems with Noise over $\mathbb{F}_2$ and Its Applications in Cold Boot Key Recovery, The Shortest Signatures Ever, Last Fall Degree, HFE, and Weil Descent Attacks on ECDLP, الگوریتمی برای محاسبه ی ایده آل های مرتب نقاط و کاربردهای آن در مدل های زیست شناسی, Computing border bases using mutant strategies, A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV, A multivariate identity-based broadcast encryption with applications to the Internet of Things, A family of weak keys in HFE and the corresponding practical key-recovery, An algorithm for solving over-determined multivariate quadratic systems over finite fields, 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, From Farfalle to \textsc{Megafono} via Ciminion: the PRF \textsc{Hydra} for MPC applications, Using dynamic memory reallocation in GInv, An estimator for the hardness of the MQ problem, A signature-based algorithm for computing the nondegenerate locus of a polynomial system, Improving support-minors rank attacks: applications to G\textit{e}MSS and Rainbow, Cryptanalysis of the TRMS Signature Scheme of PKC’05, New Differential-Algebraic Attacks and Reparametrization of Rainbow, Towards case-optimized hybrid homomorphic encryption. Featuring the \textsf{Elisabeth} stream cipher, Algebraic Attacks against Random Local Functions and Their Countermeasures, A geometric view of cryptographic equation solving, Symbolic Methods for Solving Algebraic Systems of Equations and Applications for Testing the Structural Stability, Algebraic Modelling of Covering Arrays, Dixon-EDF: The Premier Method for Solution of Parametric Polynomial Systems, Algebraic and Slide Attacks on KeeLoq, Guess-and-Determine Algebraic Attack on the Self-Shrinking Generator, Resolvability of Hamming Graphs, Matrix-F5 algorithms over finite-precision complete discrete valuation fields, Square-Vinegar Signature Scheme, Practical-Sized Instances of Multivariate PKCs: Rainbow, TTS, and ℓIC-Derivatives, Secure PRNGs from Specialized Polynomial Maps over Any $\mathbb{F}_{q}$, Revisiting the Cubic UOV Signature Scheme, Analysis of Multivariate Hash Functions, A lattice formulation of the noncommutative F4 procedure, Normal Form Analysis of ℤ2-Equivariant Singularities, From Analytical Mechanics Problems to Rewriting Theory Through M. Janet’s Work, Analysis of Snapback Repellers Using Methods of Symbolic Computation, Poly-Dragon: an efficient multivariate public key cryptosystem, Finding Fuzzy Inverse Matrix Using Wu’s Method, Cyclotomic difference sets in finite fields, GENERALIZED REDUCTION TO COMPUTE TORIC IDEALS, On the construction of staggered linear bases, Using Galois ideals for computing relative resolvents, Computation of invariants of finite abelian groups, THE NEXT-TO-MINIMAL SUPERSYMMETRIC EXTENSION OF THE STANDARD MODEL REVIEWED, Strong Gröbner bases for polynomials over a principal ideal ring, Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects, Algebraic Attacks Galore!, Algebraic Analysis of Bifurcation and Limit Cycles for Biological Systems, Kipnis-Shamir Attack on HFE Revisited, Weil sum for birthday attack in multivariate quadratic cryptosystem, Image analysis: identification of objects via polynomial systems, Solving Polynomial Systems via Truncated Normal Forms, Real Root Isolation of Regular Chains, A Practical Method for Floating-Point Gröbner Basis Computation, The Implementation and Complexity Analysis of the Branch Gröbner Bases Algorithm Over Boolean Polynomial Rings, On the complexity of computing Gröbner bases for weighted homogeneous systems, A Multivariate Encryption Scheme with Rainbow, A Variant of the F4 Algorithm, Decomposition of polynomial sets into characteristic pairs, Giac and GeoGebra – Improved Gröbner Basis Computations, Square, a New Multivariate Encryption Scheme, Recent Developments in Multivariate Public Key Cryptosystems, Computing H-bases via minimal bases for syzygy modules, Cube Attacks on Tweakable Black Box Polynomials, On the security properties of Russian standardized elliptic curves, A Study on Gröbner Basis with Inexact Input, Computing Gröbner Bases within Linear Algebra, Analysis of the Collision Resistance of RadioGatúnUsing Algebraic Techniques, Improved Computation of Involutive Bases, A Note on Dynamic Gröbner Bases Computation, Practical Algebraic Attacks on the Hitag2 Stream Cipher, A computational algebraic geometry approach to enumerate Malcev magma algebras over finite fields, Hybrid approach for solving multivariate systems over finite fields, Algebraic attack on NTRU using Witt vectors and Gröbner bases, General Fault Attacks on Multivariate Public Key Cryptosystems, Breaking an Identity-Based Encryption Scheme Based on DHIES, A linear algebra method to decompose forms whose length is lower than the number of variables into weighted sum of squares, Chosen ciphertext attack on ZHFE, Specific S-Box Criteria in Algebraic Attacks on Block Ciphers with Several Known Plaintexts, A Practical Multivariate Blind Signature Scheme, Cryptanalysis of Cramer-Shoup Like Cryptosystems Based on Index Exchangeable Family, Computing canonical heights using arithmetic intersection theory, On the Chordality of Simple Decomposition in Top-Down Style, Algebraic Analysis of Bifurcations and Chaos for Discrete Dynamical Systems, Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology, Superspecial Trigonal Curves of Genus 5, Polynomial selection of <i>F</i><sub>4</sub> for solving the MQ problem, Solving fuzzy complex system of linear equations using eigenvalue method

Uses Software

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1295781&oldid=13410511"