Efficient Multiplication over Extension Fields

International audienceThe efficiency of cryptographic protocols rely on the speed of the underlying arithmetic and finite field computation. In the literature , several methods on how to improve the multiplication over extensions fields Fqm , for prime q were developped. These optimisations are often related to the Karatsuba and Toom Cook methods. However, the speeding-up is only interesting when m is a product of powers of 2 and 3. In general cases, a fast multiplication over Fqm is implemented through the use of the naive schoolbook method. In this paper, we propose a new efficient multiplication over Fqm for any power m. The multiplication relies on the notion of Adapted Modular Number System (AMNS), introduced in 2004 by [3]. We improve the construction of an AMNS basis and we provide a fast implementation of the multiplication over Fqm , which is faster than GMP and NTL