Efficient multiplication in finite field extensions of degree 5

Nadia El Mrabet 1 Aurore Guillevic * Sorina Ionica 2
* Corresponding author
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : Small degree extensions of finite fields are commonly used for cryptographic purposes. For extension fields of degree 2 and 3, the Karatsuba and Toom Cook formulae perform a multiplication in the extension field using 3 and 5 multiplications in the base field, respectively. For degree 5 extensions, Montgomery has given a method to multiply two elements in the extension field with 13 base field multiplications. We propose a faster algorithm, which requires only 9 base field multiplications. Our method, based on Newton's interpolation, uses a larger number of additions than Montgomery's one but our implementation of the two methods shows that for cryptographic sizes, our algorithm is much faster.
Document type :
Journal articles
Complete list of metadatas

Contributor : Sorina Ionica <>
Submitted on : Wednesday, July 20, 2011 - 3:03:03 PM
Last modification on : Wednesday, November 20, 2019 - 2:23:17 AM


  • HAL Id : inria-00609920, version 1


Nadia El Mrabet, Aurore Guillevic, Sorina Ionica. Efficient multiplication in finite field extensions of degree 5. Progress in Cryptology-Africacrypt 2011, Springer, 2011, pp.188-205. ⟨inria-00609920⟩



Record views