Optimal Karatsuba-like formulae for certain bilinear forms in GF(2) (Q947669)

Given some field \(F\) and a known bilinear form belonging to \(F,\) the construction of optimal algorithms for computing such a bilinear form enjoys a large literature. Here the author chooses \(F\) to be the \(GF(2)\), the field with only two elements, and presents several combinatorial approaches for finding optimal Karatsuba-like formulae for fast computing of certain bilinear forms in \(GF(2)\). Two exhaustive search algorithms are proposed which exploit an explicit construction of trilinear decompositions. All considered examples are symmetric but results about non-symmetric case are promised in a separate paper.