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

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

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
Volume429
Issue number8-9
DOIs
Publication statusPublished - 16 Oct 2008
Externally publishedYes

Keywords

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

Fingerprint

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