Efficient multiplication in F-3lm, m >= 1 and 5 <= l <= 18


1st International Conference on Cryptology in Africa, Casablanca, Morocco, 11 - 14 June 2008, vol.5023, pp.406-409 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 5023
  • City: Casablanca
  • Country: Morocco
  • Page Numbers: pp.406-409
  • Keywords: Chinese Remainder Theorem, finite field multiplication, pairing based cryptography, KARATSUBA-LIKE FORMULAS, 6-TERM, 5-TERM
  • Middle East Technical University Affiliated: Yes


Using a method based on Chinese Remainder Theorem for polynomial multiplication and suitable reductions, we obtain an efficient multiplication method for finite fields of characteristic 3. Large finite fields of characteristic 3 are important for pairing based cryptography [3]. For 5 <= l <= 18, we show that our method gives canonical multiplication formulae over F-3lm for any m >= 1 with the best multiplicative complexity improving the bounds in [6]. We give explicit formula in the case F-36.97.