Improved Three-Way Split Formulas for Binary Polynomial and Toeplitz Matrix Vector Products

Cenk M., Negre C., Hasan M. A.

IEEE TRANSACTIONS ON COMPUTERS, cilt.62, sa.7, ss.1345-1361, 2013 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 62 Sayı: 7
  • Basım Tarihi: 2013
  • Doi Numarası: 10.1109/tc.2012.96
  • Dergi Adı: IEEE TRANSACTIONS ON COMPUTERS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.1345-1361
  • Anahtar Kelimeler: Binary polynomial, Toeplitz matrix, subquadratic space complexity multiplier, finite field, MULTIPLICATION, MULTIPLIERS, FIELDS
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this paper, we consider three-way split formulas for binary polynomial multiplication and Toeplitz matrix vector product (TMVP). We first recall the best known three-way split formulas for polynomial multiplication: the formulas with six recursive multiplications given by Sunar in a 2006 IEEE Transactions on Computers paper and the formula with five recursive multiplications proposed by Bernstein at CRYPTO 2009. Second, we propose a new set of three-way split formulas for polynomial multiplication that are an optimization of Sunar's formulas. Then, we present formulas with five recursive multiplications based on field extension. In addition, we extend the latter formulas to TMVP. We evaluate the space and delay complexities when computations are performed in parallel and provide a comparison with best known methods.