• DocumentCode
    1398525
  • Title

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

  • Author

    Oseledets, Ivan

  • Author_Institution
    Inst. of Numerical Math., Moscow, Russia
  • Volume
    60
  • Issue
    8
  • fYear
    2011
  • Firstpage
    1212
  • Lastpage
    1216
  • 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.
  • Keywords
    integer programming; polynomials; Chinese remainder theorem; modulus polynomial; n-term Karatsuba-like formula; polynomial multiplication; Approximation algorithms; Cathode ray tubes; Complexity theory; Neodymium; Polynomials; Sparse matrices; Vectors; Chinese remainder theorem; Karatsuba algorithm.; Polynomial multiplication; fast algorithm;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/TC.2010.233
  • Filename
    5661770
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1398525