Paper 2022/1412
Algorithm xxx: Evaluating a Boolean Polynomial on All Possible Inputs
, Sorbonne Université, Paris, France, LIP6 laboratory, Paris, FranceAbstract
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 $O(d 2^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.
Note: Software available at https://gitlab.lip6.fr/almasty/BeanPolE
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. Major revision. Transactions on Mathematical Software
- DOI
- 10.1145/3699957
- Keywords
- Boolean polynomialsexhaustive searchsoftware implementationMoebius transform
- Contact author(s)
- charles bouillaguet @ lip6 fr
- History
- 2024-10-12: last of 3 revisions
- 2022-10-18: received
- See all versions
- Short URL
- https://ia.cr/2022/1412
- License
-
CC0
BibTeX
@misc{cryptoeprint:2022/1412,
author = {Charles Bouillaguet},
title = {Algorithm xxx: Evaluating a Boolean Polynomial on All Possible Inputs},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/1412},
year = {2022},
doi = {10.1145/3699957},
url = {https://eprint.iacr.org/2022/1412}
}
