Fast computing the algebraic degree of Boolean functions

DOI10.1007/978-3-030-21363-3_5zbMATH Open1434.68666arXiv1905.08649OpenAlexW2945121392MaRDI QIDQ2175408FDOQ2175408

Authors: Valentin P. Bakoev 

Publication date: 29 April 2020

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.

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

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

zbMATH Keywords

Boolean functionalgebraic degreealgebraic normal formbitwise algorithmbyte-wise algorithmweight-lexicographic orderWLO masks generatingWLO sequence generating

Mathematics Subject Classification ID

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

Cited In (8)

• Title not available (Why is that?)
• Computing the Weight of a Boolean Function from Its Algebraic Normal Form
• Computing Walsh Transform from the Algebraic Normal Form of a Boolean Function
• Title not available (Why is that?)
• Some problems and algorithms related to the weight order relation on the n-dimensional Boolean cube
• Algorithms for Boolean Function Query Properties
• Efficient probabilistic algorithm for estimating the algebraic properties of Boolean functions for large \(n\)
• An efficient algorithm for calculating Boolean difference

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)