Efficient Implementation
Why implementation matters
Fundamental to any area of research is the ability to reproduce reported experiments, both for verification and for advancement. Boolean function research is unusual in how much it depends on raw computation: classifying functions, searching for good ones and computing their properties can involve many billions of steps. Yet the cryptographic literature has historically said little about how to implement these computations efficiently, leaving each researcher to reinvent the machinery.
This page summarises the implementation techniques that made the exhaustive $n = 6$ classification feasible. The guiding principle is to minimise not just the number of operations but the number of expensive operations — conditionals, multiplication, division, modular reduction — in favour of cheap bitwise operations (XOR, AND, SHIFT).
Packing truth tables into words
The natural representation of a Boolean function is a full array of $2^n$ integers, one per input. It is simple, but wasteful: a truth table or ANF needs only one bit per entry, so a full integer array uses 32× more memory than necessary.
The alternative packs the output values into the full machine word. A function of $n$ variables then needs an array of
$$N = 2^{n} / 32 = 2^{\,n-5}$$
32-bit words (for $n \ge 5$) — a memory saving of roughly 97%. Bit $i$ of the truth table lives at bit $i \bmod 32$ of word $\lfloor i / 32 \rfloor$:
/* set bit i to 1 */ array[i >> 5] |= (1 << (i & 31));
/* get bit i */ ( array[i >> 5] >> (i & 31) ) & 1;
The shift i >> 5 replaces a division and i & 31 replaces
a modular reduction — both examples of strength reduction. Crucially, packing also
lets many transforms process 32 outputs at once. Computing a Hamming weight,
for instance, needs only $2^{\,n-5}$ word-level popcounts instead of $2^{n}$ single-bit
lookups.
Key transforms
Three transforms underpin almost all property computations. Each was implemented to operate directly on the packed words, using precomputed lookup tables for the byte-level sub-results.
Algebraic Normal Form
The ANF gives the unique multilinear polynomial representation of a function over $\mathrm{GF}(2)$ (the functions of degree at most $r$ are exactly the Reed–Muller code $\mathrm{RM}(r,n)$), and from it the algebraic order and algebraic weight. The transform is a Möbius transform over the Boolean lattice; with byte-indexed lookup tables the four bytes of each 32-bit word can be transformed together, then combined.
Walsh–Hadamard Transform
The WHT is the workhorse of nonlinearity analysis: the nonlinearity follows directly from the maximum absolute Walsh coefficient,
$$\mathrm{NL}(f) = 2^{\,n-1} - \tfrac{1}{2}\,\max_{a}\,\lvert W_f(a)\rvert .$$
A precomputed table of the WHT of every 8-bit sub-function turns the transform into a small number of table lookups and additions per word.
Autocorrelation
By the Wiener–Khinchin theorem the autocorrelation is the inverse WHT of the power spectrum ($W_f^2$). The optimised autocorrelation routine therefore reuses the WHT implementation directly, computing the squared spectrum and transforming back.
In the modern library
These same ideas carry over to 64-bit words, where an $n = 6$ function fits in a single machine word and the per-function cost roughly halves again. A modern reimplementation of these transforms — with the packing scheme above — is in active development and validates its results against the classification data published on this site.