On multiplication in finite fields

Cenk M., ÖZBUDAK F.

JOURNAL OF COMPLEXITY, cilt.26, sa.2, ss.172-186, 2010 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 26 Sayı: 2
  • Basım Tarihi: 2010
  • Doi Numarası: 10.1016/j.jco.2009.11.002
  • Dergi Adı: JOURNAL OF COMPLEXITY
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.172-186
  • Anahtar Kelimeler: Finite fields, Algebraic function fields, Bilinear complexity, OPTIMAL-ALGORITHMS, COMPLEXITY, CONSTRUCTIONS, 5-TERM, BOUNDS, 6-TERM
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

We present a method for multiplication in finite fields which gives multiplication algorithms with improved or best known bilinear complexities for certain finite fields. Our method generalizes some earlier methods and combines them with the recently introduced complexity notion (M) over cap (q)(l), which denotes the minimum number of multiplications needed in F-q in order to obtain the coefficients of the product of two arbitrary l-term polynomials modulo x(l) in F-q[x]. We study our method for the finite fields F(q)n, where 2 <= n <= 18 and q = 2, 3,4 and we improve or reach the currently best known bilinear complexities. We also give some applications in cryptography. (C) 2010 Published by Elsevier Inc.