Repository navigation
Expand file tree
/
Copy pathclass-sizes.html
More file actions
93 lines (87 loc) · 21 KB
/
Copy pathclass-sizes.html
File metadata and controls
93 lines (87 loc) · 21 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Class Sizes and the Self-Mapping Constant — Boolean Functions for Cryptography</title>
<meta name="description" content="How many Boolean functions are in each affine equivalence class: the self-mapping constant, all 48 class sizes for n = 5, and function counts by nonlinearity for n = 6.">
<meta name="author" content="Joanne Fuller">
<link rel="canonical" href="https://booleanfunction.github.io/class-sizes.html">
<link rel="icon" href="favicon.svg">
<link rel="stylesheet" href="style.css?v=c9669768">
<script>window.MathJax={tex:{inlineMath:[['$','$'],['\\(','\\)']]}};</script>
<script async src="https://cdn.jsdelivr.net/npm/mathjax@3.2.2/es5/tex-mml-chtml.js"></script>
</head>
<body>
<header class="site-head"><a class="masthead-title" href="index.html">Boolean Functions for Cryptography</a><nav class="masthead-nav" aria-label="Main"><a class="navlink" href="index.html">Home</a><a class="navlink" href="basics.html">Basics</a><details class="navgroup"><summary class="navlink active">Classes</summary><div class="navmenu"><a href="equivalence-classes.html">Equivalence classes & data</a><a href="class-sizes.html" aria-current="page">Class sizes</a><a href="connectivity.html">Connectivity</a></div></details><details class="navgroup"><summary class="navlink">Research</summary><div class="navmenu"><a href="constructions.html">Constructions & search</a><a href="sboxes.html">S-boxes & AES</a><a href="records.html">Records & open problems</a><a href="efficient-implementation.html">Efficient implementation</a></div></details><details class="navgroup"><summary class="navlink">Tools</summary><div class="navmenu"><a href="explore.html">Class Graph Explorer</a><a href="analyse.html">Function Analyser</a></div></details><a class="navlink" href="publications.html">Publications</a><a class="navlink" href="learning.html">Learning</a></nav></header>
<script>document.addEventListener('click',function(e){document.querySelectorAll('details.navgroup[open]').forEach(function(d){if(!d.contains(e.target))d.removeAttribute('open');});});document.addEventListener('keydown',function(e){if(e.key==='Escape')document.querySelectorAll('details.navgroup[open]').forEach(function(d){d.removeAttribute('open');});});document.addEventListener('toggle',function(e){var t=e.target;if(t.matches&&t.matches('details.navgroup')&&t.open)document.querySelectorAll('details.navgroup[open]').forEach(function(d){if(d!==t)d.removeAttribute('open');});},true);</script>
<main class="container">
<h1>Counting the Functions in Each Class</h1>
<p>An affine equivalence class groups Boolean functions that share the same cryptographic
properties. But how <em>big</em> 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 <strong>self-mapping constant</strong>.</p>
<h2>Self mappings</h2>
<p>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 <em>itself</em> is a <strong>self mapping</strong> of $f$. The identity is
always one, so every function has at least one.</p>
<p>The thesis proves three facts about self mappings (Chapter 4):</p>
<ol>
<li>The self mappings of $f$ form a <strong>subgroup</strong> of the affine group, so their number,
$\theta$, divides the order of the group.</li>
<li>If $f$ and $g$ are equivalent, the number of distinct transforms taking $f$ to $g$ is
<strong>exactly $\theta$</strong>, the number of self mappings of $f$.</li>
<li>Equivalent functions have the <strong>same</strong> number of self mappings, so $\theta$ is a
property of the whole class: the <em>self-mapping constant</em>.</li>
</ol>
<h2>The class-size formula</h2>
<p>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</p>
<p>$$\mathcal{T} = 2^{2n+1} \prod_{i=0}^{n-1} \left(2^n - 2^i\right).$$</p>
<p>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</p>
<p>$$\#\mathcal{C} = \frac{\mathcal{T}}{\theta}.$$</p>
<p>(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.</p>
<div class="table-scroll"><table><thead><tr><th class="num">n</th><th class="num">affine transforms 𝒯</th></tr></thead><tbody><tr><td class="num">3</td><td class="num">21,504</td></tr><tr><td class="num">4</td><td class="num">10,321,920</td></tr><tr><td class="num">5</td><td class="num">20,478,689,280</td></tr><tr><td class="num">6</td><td class="num">165,140,150,353,920</td></tr></tbody></table></div>
<p>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.</p>
<h2>All 48 classes for $n = 5$</h2>
<p>Class numbers and example functions match the
<a href="equivalence-classes.html">$n = 5$ class table</a>. 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$.</p>
<div class="table-scroll"><table><thead><tr><th class="num">class</th><th>example</th><th class="num">self maps θ</th><th class="num">functions in class</th></tr></thead><tbody><tr><td class="num">1</td><td><code>0xaa55aa55</code></td><td class="num">319,979,520</td><td class="num">64</td></tr><tr><td class="num">2</td><td><code>0xaa55ab55</code></td><td class="num">9,999,360</td><td class="num">2,048</td></tr><tr><td class="num">3</td><td><code>0xaa55bb55</code></td><td class="num">645,120</td><td class="num">31,744</td></tr><tr><td class="num">4</td><td><code>0xaa5dbb55</code></td><td class="num">64,512</td><td class="num">317,440</td></tr><tr><td class="num">5</td><td><code>0xaaddbb55</code></td><td class="num">258,048</td><td class="num">79,360</td></tr><tr><td class="num">6</td><td><code>0xaa5dbb51</code></td><td class="num">9,216</td><td class="num">2,222,080</td></tr><tr><td class="num">7</td><td><code>0x2a5dbb51</code></td><td class="num">1,920</td><td class="num">10,665,984</td></tr><tr><td class="num">8</td><td><code>0xaaddbb51</code></td><td class="num">9,216</td><td class="num">2,222,080</td></tr><tr><td class="num">9</td><td><code>0x2a5dbf51</code></td><td class="num">11,520</td><td class="num">1,777,664</td></tr><tr><td class="num">10</td><td><code>0x6a5dbb51</code></td><td class="num">720</td><td class="num">28,442,624</td></tr><tr><td class="num">11</td><td><code>0x2addbb51</code></td><td class="num">768</td><td class="num">26,664,960</td></tr><tr><td class="num">12</td><td><code>0xa8ddbb51</code></td><td class="num">18,432</td><td class="num">1,111,040</td></tr><tr><td class="num">13</td><td><code>0xaeddda51</code></td><td class="num">720</td><td class="num">28,442,624</td></tr><tr><td class="num">14</td><td><code>0x0a5dbf51</code></td><td class="num">1,152</td><td class="num">17,776,640</td></tr><tr><td class="num">15</td><td><code>0x8addda51</code></td><td class="num">144</td><td class="num">142,213,120</td></tr><tr><td class="num">16</td><td><code>0xa8dd9b51</code></td><td class="num">768</td><td class="num">26,664,960</td></tr><tr><td class="num">17</td><td><code>0x88ddbb51</code></td><td class="num">64,512</td><td class="num">317,440</td></tr><tr><td class="num">18</td><td><code>0x88ddbb11</code></td><td class="num">2,064,384</td><td class="num">9,920</td></tr><tr><td class="num">19</td><td><code>0x8c5dda51</code></td><td class="num">1,152</td><td class="num">17,776,640</td></tr><tr><td class="num">20</td><td><code>0xa89d9b51</code></td><td class="num">12,288</td><td class="num">1,666,560</td></tr><tr><td class="num">21</td><td><code>0x8eddda51</code></td><td class="num">192</td><td class="num">106,659,840</td></tr><tr><td class="num">22</td><td><code>0xaefdda51</code></td><td class="num">72</td><td class="num">284,426,240</td></tr><tr><td class="num">23</td><td><code>0x025dbf51</code></td><td class="num">1,024</td><td class="num">19,998,720</td></tr><tr><td class="num">24</td><td><code>0x88ddda51</code></td><td class="num">96</td><td class="num">213,319,680</td></tr><tr><td class="num">25</td><td><code>0x88dd9b51</code></td><td class="num">5,376</td><td class="num">3,809,280</td></tr><tr><td class="num">26</td><td><code>0xceddda51</code></td><td class="num">48</td><td class="num">426,639,360</td></tr><tr><td class="num">27</td><td><code>0x0eddda51</code></td><td class="num">144</td><td class="num">142,213,120</td></tr><tr><td class="num">28</td><td><code>0x425dbf51</code></td><td class="num">64</td><td class="num">319,979,520</td></tr><tr><td class="num">29</td><td><code>0x8cddda51</code></td><td class="num">48</td><td class="num">426,639,360</td></tr><tr><td class="num">30</td><td><code>0x88dddb51</code></td><td class="num">1,008</td><td class="num">20,316,160</td></tr><tr><td class="num">31</td><td><code>0x289d9b51</code></td><td class="num">768</td><td class="num">26,664,960</td></tr><tr><td class="num">32</td><td><code>0x86fdda51</code></td><td class="num">768</td><td class="num">26,664,960</td></tr><tr><td class="num">33</td><td><code>0x88dddb71</code></td><td class="num">4,032</td><td class="num">5,079,040</td></tr><tr><td class="num">34</td><td><code>0xcefdda51</code></td><td class="num">120</td><td class="num">170,655,744</td></tr><tr><td class="num">35</td><td><code>0x0efdda51</code></td><td class="num">32</td><td class="num">639,959,040</td></tr><tr><td class="num">36</td><td><code>0x288d9b51</code></td><td class="num">768</td><td class="num">26,664,960</td></tr><tr><td class="num">37</td><td><code>0x8cfdda51</code></td><td class="num">48</td><td class="num">426,639,360</td></tr><tr><td class="num">38</td><td><code>0x8cdddb51</code></td><td class="num">576</td><td class="num">35,553,280</td></tr><tr><td class="num">39</td><td><code>0x8ccdda51</code></td><td class="num">256</td><td class="num">79,994,880</td></tr><tr><td class="num">40</td><td><code>0x289d9b41</code></td><td class="num">23,040</td><td class="num">888,832</td></tr><tr><td class="num">41</td><td><code>0x488ddb51</code></td><td class="num">192</td><td class="num">106,659,840</td></tr><tr><td class="num">42</td><td><code>0xccfdda51</code></td><td class="num">60</td><td class="num">341,311,488</td></tr><tr><td class="num">43</td><td><code>0x688d9b51</code></td><td class="num">192</td><td class="num">106,659,840</td></tr><tr><td class="num">44</td><td><code>0x288d9b41</code></td><td class="num">11,520</td><td class="num">1,777,664</td></tr><tr><td class="num">45</td><td><code>0x288d1b41</code></td><td class="num">368,640</td><td class="num">55,552</td></tr><tr><td class="num">46</td><td><code>0xdcfdda51</code></td><td class="num">1,920</td><td class="num">10,665,984</td></tr><tr><td class="num">47</td><td><code>0x68ad9b51</code></td><td class="num">6,144</td><td class="num">3,333,120</td></tr><tr><td class="num">48</td><td><code>0x688ddb51</code></td><td class="num">1,536</td><td class="num">13,332,480</td></tr></tbody></table></div>
<h2>$n = 6$: the self-mapping distribution</h2>
<p>For the 150,357 classes of $n = 6$ there are <strong>122</strong> distinct values of $\theta$.
Most classes have no symmetry at all: <strong>91,184 classes have $\theta = 1$</strong> (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$.</p>
<details>
<summary><strong>Number of $n = 6$ classes for each value of θ</strong>: all 122 values</summary>
<div class="table-scroll"><table><thead><tr><th class="num">self maps θ</th><th class="num">classes</th></tr></thead><tbody><tr><td class="num">1</td><td class="num">91,184</td></tr><tr><td class="num">2</td><td class="num">32,454</td></tr><tr><td class="num">3</td><td class="num">206</td></tr><tr><td class="num">4</td><td class="num">12,522</td></tr><tr><td class="num">6</td><td class="num">530</td></tr><tr><td class="num">7</td><td class="num">4</td></tr><tr><td class="num">8</td><td class="num">5,590</td></tr><tr><td class="num">10</td><td class="num">12</td></tr><tr><td class="num">12</td><td class="num">582</td></tr><tr><td class="num">14</td><td class="num">8</td></tr><tr><td class="num">16</td><td class="num">2,665</td></tr><tr><td class="num">18</td><td class="num">6</td></tr><tr><td class="num">20</td><td class="num">30</td></tr><tr><td class="num">24</td><td class="num">506</td></tr><tr><td class="num">32</td><td class="num">1,275</td></tr><tr><td class="num">36</td><td class="num">29</td></tr><tr><td class="num">40</td><td class="num">4</td></tr><tr><td class="num">42</td><td class="num">4</td></tr><tr><td class="num">48</td><td class="num">351</td></tr><tr><td class="num">60</td><td class="num">8</td></tr><tr><td class="num">64</td><td class="num">591</td></tr><tr><td class="num">72</td><td class="num">54</td></tr><tr><td class="num">96</td><td class="num">191</td></tr><tr><td class="num">120</td><td class="num">18</td></tr><tr><td class="num">128</td><td class="num">346</td></tr><tr><td class="num">144</td><td class="num">50</td></tr><tr><td class="num">168</td><td class="num">4</td></tr><tr><td class="num">192</td><td class="num">183</td></tr><tr><td class="num">240</td><td class="num">14</td></tr><tr><td class="num">256</td><td class="num">140</td></tr><tr><td class="num">288</td><td class="num">36</td></tr><tr><td class="num">320</td><td class="num">4</td></tr><tr><td class="num">336</td><td class="num">2</td></tr><tr><td class="num">360</td><td class="num">5</td></tr><tr><td class="num">384</td><td class="num">130</td></tr><tr><td class="num">432</td><td class="num">6</td></tr><tr><td class="num">480</td><td class="num">1</td></tr><tr><td class="num">512</td><td class="num">79</td></tr><tr><td class="num">576</td><td class="num">9</td></tr><tr><td class="num">640</td><td class="num">1</td></tr><tr><td class="num">672</td><td class="num">1</td></tr><tr><td class="num">720</td><td class="num">9</td></tr><tr><td class="num">768</td><td class="num">43</td></tr><tr><td class="num">1,008</td><td class="num">5</td></tr><tr><td class="num">1,024</td><td class="num">39</td></tr><tr><td class="num">1,152</td><td class="num">54</td></tr><tr><td class="num">1,296</td><td class="num">4</td></tr><tr><td class="num">1,344</td><td class="num">2</td></tr><tr><td class="num">1,440</td><td class="num">6</td></tr><tr><td class="num">1,536</td><td class="num">72</td></tr><tr><td class="num">1,920</td><td class="num">3</td></tr><tr><td class="num">2,048</td><td class="num">29</td></tr><tr><td class="num">2,160</td><td class="num">2</td></tr><tr><td class="num">2,304</td><td class="num">13</td></tr><tr><td class="num">2,880</td><td class="num">1</td></tr><tr><td class="num">3,072</td><td class="num">20</td></tr><tr><td class="num">3,456</td><td class="num">5</td></tr><tr><td class="num">3,840</td><td class="num">8</td></tr><tr><td class="num">4,032</td><td class="num">3</td></tr><tr><td class="num">4,096</td><td class="num">9</td></tr><tr><td class="num">4,320</td><td class="num">3</td></tr><tr><td class="num">4,608</td><td class="num">24</td></tr><tr><td class="num">5,040</td><td class="num">2</td></tr><tr><td class="num">5,376</td><td class="num">1</td></tr><tr><td class="num">5,760</td><td class="num">1</td></tr><tr><td class="num">6,144</td><td class="num">22</td></tr><tr><td class="num">7,680</td><td class="num">1</td></tr><tr><td class="num">8,064</td><td class="num">2</td></tr><tr><td class="num">8,192</td><td class="num">3</td></tr><tr><td class="num">9,216</td><td class="num">2</td></tr><tr><td class="num">10,752</td><td class="num">4</td></tr><tr><td class="num">12,288</td><td class="num">19</td></tr><tr><td class="num">13,824</td><td class="num">1</td></tr><tr><td class="num">16,384</td><td class="num">2</td></tr><tr><td class="num">17,280</td><td class="num">1</td></tr><tr><td class="num">18,432</td><td class="num">4</td></tr><tr><td class="num">23,040</td><td class="num">6</td></tr><tr><td class="num">24,576</td><td class="num">3</td></tr><tr><td class="num">32,256</td><td class="num">5</td></tr><tr><td class="num">36,864</td><td class="num">8</td></tr><tr><td class="num">40,320</td><td class="num">2</td></tr><tr><td class="num">43,008</td><td class="num">1</td></tr><tr><td class="num">46,080</td><td class="num">5</td></tr><tr><td class="num">49,152</td><td class="num">7</td></tr><tr><td class="num">56,448</td><td class="num">2</td></tr><tr><td class="num">61,440</td><td class="num">1</td></tr><tr><td class="num">64,512</td><td class="num">1</td></tr><tr><td class="num">65,536</td><td class="num">1</td></tr><tr><td class="num">73,728</td><td class="num">11</td></tr><tr><td class="num">86,016</td><td class="num">2</td></tr><tr><td class="num">98,304</td><td class="num">1</td></tr><tr><td class="num">110,592</td><td class="num">2</td></tr><tr><td class="num">120,960</td><td class="num">1</td></tr><tr><td class="num">122,880</td><td class="num">3</td></tr><tr><td class="num">184,320</td><td class="num">2</td></tr><tr><td class="num">258,048</td><td class="num">2</td></tr><tr><td class="num">294,912</td><td class="num">2</td></tr><tr><td class="num">344,064</td><td class="num">1</td></tr><tr><td class="num">393,216</td><td class="num">1</td></tr><tr><td class="num">483,840</td><td class="num">1</td></tr><tr><td class="num">589,824</td><td class="num">2</td></tr><tr><td class="num">688,128</td><td class="num">1</td></tr><tr><td class="num">737,280</td><td class="num">3</td></tr><tr><td class="num">884,736</td><td class="num">1</td></tr><tr><td class="num">1,105,920</td><td class="num">4</td></tr><tr><td class="num">1,290,240</td><td class="num">1</td></tr><tr><td class="num">1,451,520</td><td class="num">1</td></tr><tr><td class="num">2,064,384</td><td class="num">3</td></tr><tr><td class="num">2,359,296</td><td class="num">1</td></tr><tr><td class="num">3,538,944</td><td class="num">1</td></tr><tr><td class="num">4,128,768</td><td class="num">2</td></tr><tr><td class="num">4,423,680</td><td class="num">1</td></tr><tr><td class="num">14,450,688</td><td class="num">1</td></tr><tr><td class="num">30,965,760</td><td class="num">2</td></tr><tr><td class="num">70,778,880</td><td class="num">1</td></tr><tr><td class="num">92,897,280</td><td class="num">1</td></tr><tr><td class="num">115,605,504</td><td class="num">1</td></tr><tr><td class="num">123,863,040</td><td class="num">1</td></tr><tr><td class="num">639,959,040</td><td class="num">1</td></tr><tr><td class="num">1,981,808,640</td><td class="num">1</td></tr><tr><td class="num">20,158,709,760</td><td class="num">1</td></tr><tr><td class="num">1,290,157,424,640</td><td class="num">1</td></tr></tbody></table></div>
</details>
<h2>How many functions have each nonlinearity? ($n = 6$)</h2>
<p>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.</p>
<div class="table-scroll"><table><thead><tr><th class="num">nonlinearity</th><th class="num">number of functions</th></tr></thead><tbody><tr><td class="num">0</td><td class="num">128</td></tr><tr><td class="num">1</td><td class="num">8,192</td></tr></tbody></table></div>
<div class="callout-note"><p><strong>Source.</strong> J. Fuller, <em>Analysis of Affine Equivalent
Boolean Functions for Cryptography</em>, PhD thesis, QUT, 2003: Chapter 4 (self mappings,
class sizes, nonlinearity counts) and Appendix 4 (tables), available from
<a href="https://eprints.qut.edu.au/15828/">QUT ePrints</a>; 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.</p></div>
</main>
<footer class="site-footer"><div class="foot-inner">
<span>© Dr Joanne Fuller · <a href="https://orcid.org/0000-0002-5221-3505" rel="me noopener">ORCID</a> · <a href="https://scholar.google.com/citations?user=aCp_g7IAAAAJ&hl=en" rel="me noopener">Google Scholar</a> · <a href="https://www.linkedin.com/in/joanne-fuller-phd-04955b1a/" rel="me noopener">LinkedIn</a></span>
<span>Content and data licensed <a href="https://creativecommons.org/licenses/by/4.0/" rel="license noopener">CC BY 4.0</a>: please <a href="equivalence-classes.html#cite">cite</a> when reusing</span>
</div></footer>
</body>
</html>