Fast computing the algebraic degree of Boolean functions

DOI10.1007/978-3-030-21363-3_5MaRDI QIDQ2175408zbMATH OpenOpenAlexFDO

Authors Valentin P. Bakoev

Publication date 29 April 2020

Full work available at URL https://arxiv.org/abs/1905.08649

zbMATH Keywords

algebraic degreealgebraic normal formbitwise algorithmBoolean functionbyte-wise algorithmweight-lexicographic orderWLO masks generatingWLO sequence generating

Mathematics Subject Classification ID

Boolean functions (06E30) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Abstract: Here we consider an approach for fast computing the algebraic degree of Boolean functions. It combines fast computing the ANF (known as ANF transform) and thereafter the algebraic degree by using the weight-lexicographic order (WLO) of the vectors of the $n$-dimensional Boolean cube. Byte-wise and bitwise versions of a search based on the WLO and their implementations are discussed. They are compared with the usual exhaustive search applied in computing the algebraic degree. For Boolean functions of $n$ variables, the bitwise implementation of the search by WLO has total time complexity $O(n.2^n)$. When such a function is given by its truth table vector and its algebraic degree is computed by the bitwise versions of the algorithms discussed, the total time complexity is $Theta((9n-2).2^{n-7})=Theta(n.2^n)$. All algorithms discussed have time complexities of the same type, but with big differences in the constants hidden in the $Theta$-notation. The experimental results after numerous tests confirm the theoretical results - the running times of the bitwise implementation are dozens of times better than the running times of the byte-wise algorithms.

Recommendations

• Fast bitwise implementation of the algebraic normal form transform
• Boolean functions: degree and support
• Algorithms for computing the linearity and degree of vectorial Boolean functions
• Computing Walsh coefficients from the algebraic normal form of a Boolean function
• scientific article; zbMATH DE number 7267634

Cited in

(13)

• An efficient algorithm for calculating Boolean difference
• Boolean functions: degree and support
• Efficient probabilistic algorithm for estimating the algebraic properties of Boolean functions for large n
• Computing the Weight of a Boolean Function from Its Algebraic Normal Form
• scientific article; zbMATH DE number 4133979 (Why is no real title available?)
• Computing Walsh Transform from the Algebraic Normal Form of a Boolean Function
• Algorithms for Boolean Function Query Properties
• Computing Walsh coefficients from the algebraic normal form of a Boolean function
• Algorithms for computing the linearity and degree of vectorial Boolean functions
• Fast bitwise implementation of the algebraic normal form transform
• Some problems and algorithms related to the weight order relation on the n-dimensional Boolean cube
• scientific article; zbMATH DE number 7267634 (Why is no real title available?)
• Probabilistic estimation of the algebraic degree of Boolean functions

This page was built for publication: Fast computing the algebraic degree of Boolean functions

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