Efficient multiplication in finite field extensions of degree 5
Résumé
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.
Pour les extensions de degré 2 et 3, les méthodes de Karatsuba et Toom-Cook permettent de calculer une multiplication dans l'extension avec 3 et 5 multiplications dans le corps de base, respectivement. Pour les extensions de degré 5, les formules de Montgomery calculent la multiplication avec 13 multiplications dans le corps de base. Nous avons proposé une méthode qui calcule la multiplication dans $\F_{p^5}$ avec $9$ multiplications dans $\F_p$. Notre méthode est basée sur une intérpolation de Newton et utilise un nombre plus grand d'additions dans $\F_p$ que la méthode de Montgomery. Néanmoins, notre implémentation montre que nos formules sont plus rapides que celle de Montgomery lorsqu'on travaille avec des nombres de taille cryptographique.