Efficient multiplications in F55nF55n and F77nF77n

Efficient multiplications in finite fields of characteristics 5 and 7 are used for computing the Eta pairing over divisor class groups of the hyperelliptic curves Lee et al. (2008) [1]. In this paper, using the recent methods for multiplication in finite fields, the explicit formulas for multiplication in F55nF55n and F77nF77n are obtained with 10 multiplications in F5nF5n for F55nF55n and 15 multiplications in F7nF7n for F77nF77n improving the results in Cenk and Özbudak (2008) [4], Cenk et al. (2009) [5], Lee et al. (2008) [1] and Montgomery (2005) [12]. The timing results of implementations of the Karatsuba type formulas and the proposed formula for multiplication in F55⋅89F55⋅89 are given.

► Efficient multiplications in finite fields are important in applications.
► Characteristics 5 and 7 are used for the Eta pairing.
► We give efficient multiplication formulas for F55nF55n and F77nF77n.
► Timing comparisons are also given.