Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
DOI10.1016/j.dam.2021.11.014OpenAlexW3216715219MaRDI QIDQ2065761
Carlo Sanna, Stefano Barbero, Emanuele Bellini, Javier A. Verbel
Publication date: 13 January 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2021.11.014
probabilistic algorithmimplementationpolynomial methodpractical complexityBoolean quadratic polynomial systems
Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06) Boolean functions (94D10)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On miniaturized problems in parameterized complexity theory
- Matrix multiplication via arithmetic progressions
- NP is as easy as detecting unique solutions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Complexity of problems in games, graphs and algebraic equations
- A new efficient algorithm for computing Gröbner bases \((F_4)\)
- Implementing Joux-Vitse's crossbred algorithm for solving \(\mathcal M\mathcal Q\) systems over \(\mathbb F_2\) on GPUs
- Solving polynomial equations. Foundations, algorithms, and applications
- On the complexity of solving quadratic Boolean systems
- Cryptanalytic applications of the polynomial method for solving multivariate equation systems over \(\mathrm{GF}(2)\)
- Gaussian elimination is not optimal
- A crossbred algorithm for solving Boolean polynomial systems
- Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms
- Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
- Hybrid approach for solving multivariate systems over finite fields
- Fast Exhaustive Search for Polynomial Systems in ${\mathbb{F}_2}$
- Unbalanced Oil and Vinegar Signature Schemes
- Beating Brute Force for Systems of Polynomial Equations over Finite Fields
- Membership in polynomial ideals over Q is exponential space complete
- Information Security and Privacy
- On the complexity of \(k\)-SAT
This page was built for publication: Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
