Polynomial multiplication over binary fields using charlier polynomial representation with low space complexity

Akleylek S., CENK M., ÖZBUDAK F.

11th International Conference on Cryptology in India, INDOCRYPT 2010, Hyderabad, Hindistan, 12 - 15 Aralık 2010, cilt.6498 LNCS, ss.227-237 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 6498 LNCS
  • Doi Numarası: 10.1007/978-3-642-17401-8_17
  • Basıldığı Şehir: Hyderabad
  • Basıldığı Ülke: Hindistan
  • Sayfa Sayıları: ss.227-237
  • Anahtar Kelimeler: binary field representation, Charlier polynomials, polynomial multiplication, subquadratic space complexity
  • Ondokuz Mayıs Üniversitesi Adresli: Hayır

Özet

In this paper, we give a new way to represent certain finite fields GF(2n ). This representation is based on Charlier polynomials. We show that multiplication in Charlier polynomial representation can be performed with subquadratic space complexity. One can obtain binomial or trinomial irreducible polynomials in Charlier polynomial representation which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. This representation is very interesting for NIST recommended binary field GF(2283) since there is no ONB for the corresponding extension. We also note that recommended NIST and SEC binary fields can be constructed with low weight Charlier polynomials. © 2010 Springer-Verlag Berlin Heidelberg.