Algorithm xxx: Evaluating a Boolean Polynomial on All Possible Inputs - Sorbonne Université
Article Dans Une Revue ACM Transactions on Mathematical Software Année : 2024

Algorithm xxx: Evaluating a Boolean Polynomial on All Possible Inputs

Résumé

Evaluating a Boolean polynomial on all possible inputs (i.e. building the truth table of the corresponding Boolean function) is a simple computational problem that sometimes appears inside broader applications, for instance in cryptanalysis or in the implementation of more sophisticated algorithms to solve Boolean polynomial systems. Two techniques share the crown to perform this task: the “Fast Exhaustive Search” (FES) algorithm from 2010 (which is based on Gray Codes) and the space-efficient Moebius transform from 2021 (which is reminiscent of the FFT). Both require \(\mathcal{O}(d2^{n})\) operations for a degree- \(d\) Boolean polynomial on \(n\) variables and operate mostly in-place, but have other slightly different characteristics. They both provide an efficient iterator over the full truth table. This article describes BeanPolE (BoolEAN POLynomial Evaluation), a concise and flexible C library that implements both algorithms, as well as many other functions to deal with Boolean multivariate polynomials in dense representation.
Fichier principal
Vignette du fichier
toms (1).pdf (818.57 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04418528 , version 1 (26-01-2024)
hal-04418528 , version 2 (06-10-2024)

Licence

Identifiants

Citer

Charles Bouillaguet. Algorithm xxx: Evaluating a Boolean Polynomial on All Possible Inputs. ACM Transactions on Mathematical Software, In press, ⟨10.1145/3699957⟩. ⟨hal-04418528v2⟩
153 Consultations
217 Téléchargements

Altmetric

Partager

More