Improved n-Term Karatsuba-Like Formulas in GF(2)

Ivan V. Oseledets

Abstract

It is well known that Chinese Remainder Theorem (CRT) can be used to construct efficient algorithms for multiplication of polynomials over GF(2). In this note, we show how to select an appropriate set of modulus polynomials to obtain minimal number of multiplications.
BibTeX
@article{oseledets2011improved,
  author = {Ivan V. Oseledets},
  title = {{Improved n-Term Karatsuba-Like Formulas in GF(2)}},
  journal = {IEEE Trans. Computers},
  year = {2011},
  url = {https://openreview.net/forum?id=E9yUPZocIta},
}

Loading related content...

Figure