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

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


We propose two exhaustive search-type methods for the construction of Karatsuba-like algorithms for fast computation of certain bilinear forms in GF(2). The computation is done via an explicit construction of trilinear decompositions using heuristica search algorithms. Using that approach several old and new algorithms for the fast computation of bilinear forms were obtained.

Original languageEnglish
Pages (from-to)2052-2066
Number of pages15
JournalLinear Algebra and Its Applications
Issue number8-9
Publication statusPublished - 16 Oct 2008
Externally publishedYes


  • 15A33
  • 15A69
  • Karatsuba
  • Karatsuba-Ofman
  • Optimal algorithms
  • Polynomial multiplication
  • Tensors
  • Trilinear decomposition


Dive into the research topics of 'Optimal Karatsuba-like formulae for certain bilinear forms in GF(2)'. Together they form a unique fingerprint.

Cite this