Subquadratic Space Complexity Binary Field Multiplier Using Double Polynomial Representation - Sorbonne Université
Article Dans Une Revue IEEE Transactions on Computers Année : 2010

Subquadratic Space Complexity Binary Field Multiplier Using Double Polynomial Representation

Résumé

This paper deals with binary field multiplication. We use the bivariate representation of binary field called Double Polynomial System (DPS) presented in [11]. This concept generalizes the composite field representation to every finite field. As shown in [11], the main interest of DPS representation is that it enables to use Lagrange approach for multiplication, and in the best case, Fast Fourier Transform approach, which optimizes Lagrange approach. We use here a different strategy from [11] to perform reduction, and we also propose in this paper, some new approaches for constructing DPS. We focus on DPS, which provides a simpler and more efficient method for coefficient reduction. This enables us to avoid a multiplication required in the Montgomery reduction approach of [11], and thus to improve the complexity of the DPS multiplier. The resulting algorithm proposed in the present paper is subquadratic in space Oðn 1:31 Þ and logarithmic in time. The space complexity is 33 percent better than in [11] and 18 percent faster. It is asymptotically more efficient than the best known method [6] (specifiably more efficient than [6] when n ! 3;000). Furthermore, our proposal is available for every n and not only for n a power of two or three.

Dates et versions

hal-01098801 , version 1 (26-05-2017)

Licence

Copyright (Tous droits réservés)

Identifiants

Citer

Jean-Claude Bajard, Christophe Negre, Thomas Plantard. Subquadratic Space Complexity Binary Field Multiplier Using Double Polynomial Representation. IEEE Transactions on Computers, 2010, 59 (12), pp.1585-1597. ⟨10.1109/TC.2010.141⟩. ⟨hal-01098801⟩
191 Consultations
1 Téléchargements

Altmetric

Partager

More