## Bent function

Let f be a boolean function. Recall that f is a bent function
when all its Walsh Fourier coefficient have the same magnitude.
The Walsh coefficient at a point y of GF(2,m)

f*( y ) = sum_{x in GF(2,m)} (-1)^( f(x) + y.x )
One can check that if f is bent then f o A + l is bent for all
affine transformation A and all affine boolean function l. Two
cubics g and f on RM(3,8) are equivalent if there exists a
pair (A,l) such that :
g = f o A + l
The objective of the project is to compute
the number of classes of bent cubics in 8
variables.
## Classification of RM(3,8)*

We start from the
partial
classification of the GL-action on RM(3,8)*. From this data, computed
the first time by Xiang Dong Hou (1996), we deduce the
complete
classification by a random approah.
input
f : form of degree 3
N : orbit size of f
output
G : fixator of f
hash := hashtable with 2^30 entries
goal := #GL(2,8) / N
G := { 1 }
while ( #G < goal )
begin
A := at random in AG( 2, 8 )
g := f o A
if collision at g
then
B := hash[ g ]
G := < G, A/B >
else
hash[ g ] = A
fi
end
return G

The running time depends on the
order of the fixator :
cardinality time sec
----------------------------------------
192 5490.43 91 minutes
336 3161.40
432 5481.38
768 4529.87
2304 2412.72
3072 1289.77
3072 2158.04
3072 3454.79
10752 1134.07
18432 631.41
24576 849.16
46080 691.06
49152 880.67
82944 370.08
96768 242.83
294912 203.39
393216 133.73
1179648 96.90
1474560 42.01
1548288 62.53
1935360 46.87
2359296 90.66
9437184 31.39
47185920 18.83
88080384 11.91
1056964608 3.67
1387266048 3.91
2972712960 3.12
11890851840 0.96
63417876480 1.04
55046716784640 0.48
5348063769211699200 0.41

## Classification of RM(3,8)/RM(1,8)

We say that a homogeneous form `fq` such that `f + q` is bent. The
ANF `a_u` of a bentable cubic form satisfies
the quadratic equations:
For all subset W of {1,2,...,8}, with #W >=6
0 = sum_{ u U v = W } a_u a_v

With knowledge of the fixator group it
is easy to determine the GL-class of bent
cubics modulo affine terms. The fixator
group of a cubic form f acts over the
quadratic forms by
`
q --> q^A + f_A
`
where `f_A` is the boundary `f^A + f`.

Applying plain vanilla with this group action
one gets :
[
11 GL-class of bent functions ]
real 12m21.386s
user 12m17.661s
sys 0m3.648s

The same can be done with the affine group
[
9 AG-class of bent functions ]
real 15m32.983s
user 15m26.343s
sys 0m6.557s

Philippe Langevin
Last modification june 2013.