Solving non-linear Boolean equation systems by variable elimination

DOI10.1007/S00200-019-00399-7MaRDI QIDQ2032298zbMATH OpenOpenAlexFDO

Authors Øyvind Ytrehus, Håvard Raddum, Gunnar Fløystad, Bjørn Møller Greve

Publication date 11 June 2021

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00200-019-00399-7

zbMATH Keywords

syzygieselimination of variablessystems of Boolean equationssolving algorithmGröbner bases

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) Syzygies, resolutions, complexes and commutative rings (13D02) Boolean functions (06E30)

Recommendations

• On construction of efficient algorithms for solving systems of polynomial Boolean equations by testing a part of variables
• Boolean ring cryptographic equation solving
• On the suppression of variables in Boolean equations
• A crossbred algorithm for solving Boolean polynomial systems
• On the efficiency of solving Boolean polynomial systems with the characteristic set method

Cites work

• scientific article; zbMATH DE number 3857249 (Why is no real title available?)
• scientific article; zbMATH DE number 3930347 (Why is no real title available?)
• scientific article; zbMATH DE number 3937298 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• A crossbred algorithm for solving Boolean polynomial systems
• A new efficient algorithm for computing Gröbner bases (F₄)
• Beating brute force for systems of polynomial equations over finite fields
• Boolean Gröbner bases
• Cryptanalysis of Block Ciphers with Overdefined Systems of Equations
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• Fast exhaustive search for polynomial systems in \({\mathbb{F}_2}\)
• Gröbner Bases, Coding, and Cryptography
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Information Security and Privacy
• On the Number of Linearly Independent Equations Generated by XL
• On the complexity of solving quadratic Boolean systems
• Polybori: A framework for Gröbner-basis computations with Boolean polynomials
• Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity
• Using Algebraic Geometry

Cited in

(5)

• Solving equation systems by agreeing and learning
• Tools and Algorithms for the Construction and Analysis of Systems
• Using variable-entered karnaugh maps to solve boolean equations
• Solving systems of linear equations with Boolean variables
• On the suppression of variables in Boolean equations

Describes a project that uses

Uses Software

• SINGULAR

This page was built for publication: Solving non-linear Boolean equation systems by variable elimination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2032298)