Title :
Improved n-Term Karatsuba-Like Formulas in GF(2)
Author_Institution :
Inst. of Numerical Math., Moscow, Russia
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;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.2010.233
