Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
type: Item
instance of: scholarly article
title: Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
author: Stefano Barbero
author: Carlo Sanna
author: Emanuele Bellini
author: Javier A. Verbel
published in: Discrete Applied Mathematics
publication date: 2022-01-13T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 94D10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7456377
zbMATH Keywords: implementation
zbMATH Keywords: practical complexity
zbMATH Keywords: Boolean quadratic polynomial systems
zbMATH Keywords: polynomial method
zbMATH Keywords: probabilistic algorithm
MaRDI profile type: Publication
full work available at URL: j.dam.2021.11.014
OpenAlex ID: W3216715219
cites work: On the complexity of solving quadratic Boolean systems
cites work: Hybrid approach for solving multivariate systems over finite fields
cites work: Q5091175
cites work: Fast Exhaustive Search for Polynomial Systems in ${\mathbb{F}_2}$
cites work: Matrix multiplication via arithmetic progressions
cites work: Q3374924
cites work: Solving polynomial equations. Foundations, algorithms, and applications
cites work: Cryptanalytic applications of the polynomial method for solving multivariate equation systems over \(\mathrm{GF}(2)\)
cites work: Q4660688
cites work: A new efficient algorithm for computing Gröbner bases \((F_4)\)
cites work: Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
cites work: On miniaturized problems in parameterized complexity theory
cites work: Complexity of problems in games, graphs and algebraic equations
cites work: On the complexity of \(k\)-SAT
cites work: A crossbred algorithm for solving Boolean polynomial systems
cites work: Unbalanced Oil and Vinegar Signature Schemes
cites work: Beating Brute Force for Systems of Polynomial Equations over Finite Fields
cites work: Q3992465
cites work: Membership in polynomial ideals over Q is exponential space complete
cites work: Implementing Joux-Vitse's crossbred algorithm for solving \(\mathcal M\mathcal Q\) systems over \(\mathbb F_2\) on GPUs
cites work: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Gaussian elimination is not optimal
cites work: Q4781203
cites work: NP is as easy as detecting unique solutions
cites work: Information Security and Privacy
DOI: 10.1016/J.DAM.2021.11.014
describes a project that uses: GitHub
description: scientific article; zbMATH DE number 7456377