Speeding up the GVW algorithm via a substituting method

DOI10.1007/s11424-019-8345-3zbMath1417.68294OpenAlexW2911637424MaRDI QIDQ1730310

Yao Sun, Ting Li, Ding-Kang Wang, Dong-Dai Lin, Zhen Yu Huang

Publication date: 6 March 2019

Published in: Journal of Systems Science and Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11424-019-8345-3

zbMATH Keywords

Gröbner basissignature-based algorithmtime-memory tradeoffGVW

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

Foreword to the special issue, An involutive GVW algorithm and the computation of Pommaret bases

Uses Software

• M4RI
• Trivium
• PRESENT
• GBLA
• F5C

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On implementing the symbolic preprocessing function over Boolean polynomial rings in Gröbner basis algorithms using linear algebra
• Characteristic set algorithms for equation solving in finite fields
• Differential cryptanalysis of PRESENT-like cipher
• An improvement over the GVW algorithm for inhomogeneous polynomial systems
• Extended \(F_5\) criteria
• F5C: A variant of Faugère's F5 algorithm with reduced Gröbner bases
• Optimising Gröbner bases on Bivium
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Slender-set differential cryptanalysis
• The F5 criterion revised
• On the complexity of the \(F_5\) Gröbner basis algorithm
• An analysis of inhomogeneous signature-based Gröbner basis computations
• Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
• Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases
• A new incremental algorithm for computing Groebner bases
• Signature rewriting in gröbner basis computation
• GBLA
• Attacking Bivium and Trivium with the Characteristic Set Method
• A new framework for computing Gröbner bases
• A New Method for Solving Polynomial Systems with Noise over $\mathbb{F}_2$ and Its Applications in Cold Boot Key Recovery
• Trivium: A Stream Cipher Construction Inspired by Block Cipher Design Principles
• PRESENT: An Ultra-Lightweight Block Cipher
• Practical Gröbner basis computation
• A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras
• A generalized criterion for signature related Gröbner basis algorithms