Counting the Functions in Each Class
An affine equivalence class groups Boolean functions that share the same cryptographic properties. But how big is each class, that is, how many of the $2^{2^n}$ functions does it contain? The PhD research behind this site answered this exactly for every class with $n \le 6$, using what the thesis calls the self-mapping constant.
Self mappings
An affine transform maps $f$ to $g(x) = f(Dx \oplus a) \oplus b \cdot x \oplus c$, where $D$ is an invertible $n \times n$ binary matrix, $a, b \in \mathbb{Z}_2^n$ and $c \in \mathbb{Z}_2$. A transform that maps $f$ to itself is a self mapping of $f$. The identity is always one, so every function has at least one.
The thesis proves three facts about self mappings (Chapter 4):
- The self mappings of $f$ form a subgroup of the affine group, so their number, $\theta$, divides the order of the group.
- If $f$ and $g$ are equivalent, the number of distinct transforms taking $f$ to $g$ is exactly $\theta$, the number of self mappings of $f$.
- Equivalent functions have the same number of self mappings, so $\theta$ is a property of the whole class: the self-mapping constant.
The class-size formula
Counting the choices for $D$ (row $k$ can be any vector outside the span of the previous rows, giving $2^n - 2^k$ choices), $a$, $b$ and $c$, the total number of affine transforms is
$$\mathcal{T} = 2^{2n+1} \prod_{i=0}^{n-1} \left(2^n - 2^i\right).$$
Since every function in a class $\mathcal{C}$ is reached from $f$ by exactly $\theta$ of these transforms, the number of functions in the class is simply
$$\#\mathcal{C} = \frac{\mathcal{T}}{\theta}.$$
(This is an instance of the orbit–stabiliser theorem; the self mappings are the stabiliser of $f$ in the affine group.) The bounds follow immediately: $\theta \ge 1$, and the largest $\theta$ belongs to the smallest class, the affine functions, with $2^{n+1}$ members.
| n | affine transforms 𝒯 |
|---|---|
| 3 | 21,504 |
| 4 | 10,321,920 |
| 5 | 20,478,689,280 |
| 6 | 165,140,150,353,920 |
For example, with $n = 4$ there are $15 \times 14 \times 12 \times 8 = 20{,}160$ invertible matrices, and $20{,}160 \times 16 \times 16 \times 2 = 10{,}321{,}920$ transforms.
All 48 classes for $n = 5$
Class numbers and example functions match the $n = 5$ class table. There are 33 distinct values of $\theta$, from 32 (class 35, the largest class, with 639,959,040 functions) to 319,979,520 (the affine class, with 64). The class sizes sum to exactly $2^{32} = 4{,}294{,}967{,}296$.
| class | example | self maps θ | functions in class |
|---|---|---|---|
| 1 | 0xaa55aa55 | 319,979,520 | 64 |
| 2 | 0xaa55ab55 | 9,999,360 | 2,048 |
| 3 | 0xaa55bb55 | 645,120 | 31,744 |
| 4 | 0xaa5dbb55 | 64,512 | 317,440 |
| 5 | 0xaaddbb55 | 258,048 | 79,360 |
| 6 | 0xaa5dbb51 | 9,216 | 2,222,080 |
| 7 | 0x2a5dbb51 | 1,920 | 10,665,984 |
| 8 | 0xaaddbb51 | 9,216 | 2,222,080 |
| 9 | 0x2a5dbf51 | 11,520 | 1,777,664 |
| 10 | 0x6a5dbb51 | 720 | 28,442,624 |
| 11 | 0x2addbb51 | 768 | 26,664,960 |
| 12 | 0xa8ddbb51 | 18,432 | 1,111,040 |
| 13 | 0xaeddda51 | 720 | 28,442,624 |
| 14 | 0x0a5dbf51 | 1,152 | 17,776,640 |
| 15 | 0x8addda51 | 144 | 142,213,120 |
| 16 | 0xa8dd9b51 | 768 | 26,664,960 |
| 17 | 0x88ddbb51 | 64,512 | 317,440 |
| 18 | 0x88ddbb11 | 2,064,384 | 9,920 |
| 19 | 0x8c5dda51 | 1,152 | 17,776,640 |
| 20 | 0xa89d9b51 | 12,288 | 1,666,560 |
| 21 | 0x8eddda51 | 192 | 106,659,840 |
| 22 | 0xaefdda51 | 72 | 284,426,240 |
| 23 | 0x025dbf51 | 1,024 | 19,998,720 |
| 24 | 0x88ddda51 | 96 | 213,319,680 |
| 25 | 0x88dd9b51 | 5,376 | 3,809,280 |
| 26 | 0xceddda51 | 48 | 426,639,360 |
| 27 | 0x0eddda51 | 144 | 142,213,120 |
| 28 | 0x425dbf51 | 64 | 319,979,520 |
| 29 | 0x8cddda51 | 48 | 426,639,360 |
| 30 | 0x88dddb51 | 1,008 | 20,316,160 |
| 31 | 0x289d9b51 | 768 | 26,664,960 |
| 32 | 0x86fdda51 | 768 | 26,664,960 |
| 33 | 0x88dddb71 | 4,032 | 5,079,040 |
| 34 | 0xcefdda51 | 120 | 170,655,744 |
| 35 | 0x0efdda51 | 32 | 639,959,040 |
| 36 | 0x288d9b51 | 768 | 26,664,960 |
| 37 | 0x8cfdda51 | 48 | 426,639,360 |
| 38 | 0x8cdddb51 | 576 | 35,553,280 |
| 39 | 0x8ccdda51 | 256 | 79,994,880 |
| 40 | 0x289d9b41 | 23,040 | 888,832 |
| 41 | 0x488ddb51 | 192 | 106,659,840 |
| 42 | 0xccfdda51 | 60 | 341,311,488 |
| 43 | 0x688d9b51 | 192 | 106,659,840 |
| 44 | 0x288d9b41 | 11,520 | 1,777,664 |
| 45 | 0x288d1b41 | 368,640 | 55,552 |
| 46 | 0xdcfdda51 | 1,920 | 10,665,984 |
| 47 | 0x68ad9b51 | 6,144 | 3,333,120 |
| 48 | 0x688ddb51 | 1,536 | 13,332,480 |
$n = 6$: the self-mapping distribution
For the 150,357 classes of $n = 6$ there are 122 distinct values of $\theta$. Most classes have no symmetry at all: 91,184 classes have $\theta = 1$ (only the identity), so each contains the full $\mathcal{T} = 165{,}140{,}150{,}353{,}920$ functions. A further 32,454 have $\theta = 2$ and 12,522 have $\theta = 4$. At the other extreme, the affine class has $\theta = 1{,}290{,}157{,}424{,}640$.
Number of $n = 6$ classes for each value of θ: all 122 values
| self maps θ | classes |
|---|---|
| 1 | 91,184 |
| 2 | 32,454 |
| 3 | 206 |
| 4 | 12,522 |
| 6 | 530 |
| 7 | 4 |
| 8 | 5,590 |
| 10 | 12 |
| 12 | 582 |
| 14 | 8 |
| 16 | 2,665 |
| 18 | 6 |
| 20 | 30 |
| 24 | 506 |
| 32 | 1,275 |
| 36 | 29 |
| 40 | 4 |
| 42 | 4 |
| 48 | 351 |
| 60 | 8 |
| 64 | 591 |
| 72 | 54 |
| 96 | 191 |
| 120 | 18 |
| 128 | 346 |
| 144 | 50 |
| 168 | 4 |
| 192 | 183 |
| 240 | 14 |
| 256 | 140 |
| 288 | 36 |
| 320 | 4 |
| 336 | 2 |
| 360 | 5 |
| 384 | 130 |
| 432 | 6 |
| 480 | 1 |
| 512 | 79 |
| 576 | 9 |
| 640 | 1 |
| 672 | 1 |
| 720 | 9 |
| 768 | 43 |
| 1,008 | 5 |
| 1,024 | 39 |
| 1,152 | 54 |
| 1,296 | 4 |
| 1,344 | 2 |
| 1,440 | 6 |
| 1,536 | 72 |
| 1,920 | 3 |
| 2,048 | 29 |
| 2,160 | 2 |
| 2,304 | 13 |
| 2,880 | 1 |
| 3,072 | 20 |
| 3,456 | 5 |
| 3,840 | 8 |
| 4,032 | 3 |
| 4,096 | 9 |
| 4,320 | 3 |
| 4,608 | 24 |
| 5,040 | 2 |
| 5,376 | 1 |
| 5,760 | 1 |
| 6,144 | 22 |
| 7,680 | 1 |
| 8,064 | 2 |
| 8,192 | 3 |
| 9,216 | 2 |
| 10,752 | 4 |
| 12,288 | 19 |
| 13,824 | 1 |
| 16,384 | 2 |
| 17,280 | 1 |
| 18,432 | 4 |
| 23,040 | 6 |
| 24,576 | 3 |
| 32,256 | 5 |
| 36,864 | 8 |
| 40,320 | 2 |
| 43,008 | 1 |
| 46,080 | 5 |
| 49,152 | 7 |
| 56,448 | 2 |
| 61,440 | 1 |
| 64,512 | 1 |
| 65,536 | 1 |
| 73,728 | 11 |
| 86,016 | 2 |
| 98,304 | 1 |
| 110,592 | 2 |
| 120,960 | 1 |
| 122,880 | 3 |
| 184,320 | 2 |
| 258,048 | 2 |
| 294,912 | 2 |
| 344,064 | 1 |
| 393,216 | 1 |
| 483,840 | 1 |
| 589,824 | 2 |
| 688,128 | 1 |
| 737,280 | 3 |
| 884,736 | 1 |
| 1,105,920 | 4 |
| 1,290,240 | 1 |
| 1,451,520 | 1 |
| 2,064,384 | 3 |
| 2,359,296 | 1 |
| 3,538,944 | 1 |
| 4,128,768 | 2 |
| 4,423,680 | 1 |
| 14,450,688 | 1 |
| 30,965,760 | 2 |
| 70,778,880 | 1 |
| 92,897,280 | 1 |
| 115,605,504 | 1 |
| 123,863,040 | 1 |
| 639,959,040 | 1 |
| 1,981,808,640 | 1 |
| 20,158,709,760 | 1 |
| 1,290,157,424,640 | 1 |
How many functions have each nonlinearity? ($n = 6$)
Summing the class sizes over the classes at each nonlinearity gives the exact number of 6-variable functions with that nonlinearity. For nonlinearity below 16 these follow from a known closed formula, $\binom{64}{N} \cdot 2^{7}$; for 16 and above, the thesis obtained them by summing class sizes. The total is exactly $2^{64}$, and the 5,425,430,528 functions of nonlinearity 28 are precisely the bent functions, summed over the four bent classes.
| nonlinearity | number of functions |
|---|---|
| 0 | 128 |
| 1 | 8,192 |
Source. J. Fuller, Analysis of Affine Equivalent Boolean Functions for Cryptography, PhD thesis, QUT, 2003: Chapter 4 (self mappings, class sizes, nonlinearity counts) and Appendix 4 (tables), available from QUT ePrints; see also Millan, Fuller and Dawson, CEC 2003. All tables on this page were re-checked in 2026 against the original PhD output files. Maiorana's 1991 classification of the cosets of $\mathrm{RM}(1,6)$ records stabiliser orders in coding-theory terms.