Skip to Main content Skip to Navigation
Conference papers

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
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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 :
Conference papers
Complete list of metadatas
Contributor : Sorina Ionica <>
Submitted on : Wednesday, July 20, 2011 - 3:03:03 PM
Last modification on : Friday, October 9, 2020 - 2:40:05 PM

Links full text



Nadia El Mrabet, Aurore Guillevic, Sorina Ionica. Efficient multiplication in finite field extensions of degree 5. AFRICACRYPT 2011 - 4th International Conference on Cryptology, Jul 2011, Dakar, Senegal. pp.188-205, ⟨10.1007/978-3-642-21969-6_12⟩. ⟨inria-00609920⟩



Record views