The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Le ηT appariement pour les courbes elliptiques supersingulaires sur GF(3m) a retenu l'attention en raison de son efficacité de calcul. Puisque la plupart des parties de calcul du ηT les appariements sont GF(3m) multiplications, il est important d’améliorer la vitesse de la multiplication lors de la mise en œuvre du ηT appariement. Dans cet article, nous étudions l'implémentation logicielle de GF(3m) multiplication et proposer d'utiliser des trinômes irréductibles xm+axk+b sur GF(3) tel que k est un multiple de w, Où w est la longueur en bits du mot du processeur ciblé. Nous appelons les trinômes « trinômes optimaux de réduction (ROT) ». Les ROT existent en réalité pour plusieurs met pour les valeurs typiques de w = 16 et 32. Nous les listons pour les diplômes d'extension m = 97, 167, 193, 239, 317 et 487. Ces mLes valeurs découlent de considérations de sécurité. En utilisant les ROT, nous sommes en mesure de mettre en œuvre des opérations modulo (réductions) efficaces pour GF(3m) multiplication par rapport aux cas dans lesquels d'autres types de trinômes irréductibles sont utilisés (par exemple, les trinômes avec un minimum k pour chaque m). La raison en est que pour les cas utilisant des ROT, le nombre d'opérations de décalage sur des données à précision multiple est réduit de moitié par rapport aux cas utilisant d'autres trinômes. Nos résultats d'implémentation montrent que les programmes de réduction spécialisés pour les ROT sont 20 à 30 % plus rapides sur un processeur 32 bits et environ 40 % plus rapides sur un processeur 16 bits par rapport aux programmes utilisant des trinômes irréductibles avec des valeurs générales. k.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Toshiya NAKAJIMA, Tetsuya IZU, Tsuyoshi TAKAGI, "Reduction Optimal Trinomials for Efficient Software Implementation of the ηT Pairing" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 9, pp. 2379-2386, September 2008, doi: 10.1093/ietfec/e91-a.9.2379.
Abstract: The ηT pairing for supersingular elliptic curves over GF(3m) has been paid attention because of its computational efficiency. Since most computation parts of the ηT pairing are GF(3m) multiplications, it is important to improve the speed of the multiplication when implementing the ηT pairing. In this paper we investigate software implementation of GF(3m) multiplication and propose using irreducible trinomials xm+axk+b over GF(3) such that k is a multiple of w, where w is the bit length of the word of targeted CPU. We call the trinomials "reduction optimal trinomials (ROTs)." ROTs actually exist for several m's and for typical values of w = 16 and 32. We list them for extension degrees m = 97, 167, 193, 239, 317, and 487. These m's are derived from security considerations. Using ROTs, we are able to implement efficient modulo operations (reductions) for GF(3m) multiplication compared with cases in which other types of irreducible trinomials are used (e.g., trinomials with a minimum k for each m). The reason for this is that for cases using ROTs, the number of shift operations on multiple precision data is reduced to less than half compared with cases using other trinomials. Our implementation results show that programs of reduction specialized for ROTs are 20-30% faster on 32-bit CPU and approximately 40% faster on 16-bit CPU compared with programs using irreducible trinomials with general k.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.9.2379/_p
Copier
@ARTICLE{e91-a_9_2379,
author={Toshiya NAKAJIMA, Tetsuya IZU, Tsuyoshi TAKAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Reduction Optimal Trinomials for Efficient Software Implementation of the ηT Pairing},
year={2008},
volume={E91-A},
number={9},
pages={2379-2386},
abstract={The ηT pairing for supersingular elliptic curves over GF(3m) has been paid attention because of its computational efficiency. Since most computation parts of the ηT pairing are GF(3m) multiplications, it is important to improve the speed of the multiplication when implementing the ηT pairing. In this paper we investigate software implementation of GF(3m) multiplication and propose using irreducible trinomials xm+axk+b over GF(3) such that k is a multiple of w, where w is the bit length of the word of targeted CPU. We call the trinomials "reduction optimal trinomials (ROTs)." ROTs actually exist for several m's and for typical values of w = 16 and 32. We list them for extension degrees m = 97, 167, 193, 239, 317, and 487. These m's are derived from security considerations. Using ROTs, we are able to implement efficient modulo operations (reductions) for GF(3m) multiplication compared with cases in which other types of irreducible trinomials are used (e.g., trinomials with a minimum k for each m). The reason for this is that for cases using ROTs, the number of shift operations on multiple precision data is reduced to less than half compared with cases using other trinomials. Our implementation results show that programs of reduction specialized for ROTs are 20-30% faster on 32-bit CPU and approximately 40% faster on 16-bit CPU compared with programs using irreducible trinomials with general k.},
keywords={},
doi={10.1093/ietfec/e91-a.9.2379},
ISSN={1745-1337},
month={September},}
Copier
TY - JOUR
TI - Reduction Optimal Trinomials for Efficient Software Implementation of the ηT Pairing
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2379
EP - 2386
AU - Toshiya NAKAJIMA
AU - Tetsuya IZU
AU - Tsuyoshi TAKAGI
PY - 2008
DO - 10.1093/ietfec/e91-a.9.2379
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2008
AB - The ηT pairing for supersingular elliptic curves over GF(3m) has been paid attention because of its computational efficiency. Since most computation parts of the ηT pairing are GF(3m) multiplications, it is important to improve the speed of the multiplication when implementing the ηT pairing. In this paper we investigate software implementation of GF(3m) multiplication and propose using irreducible trinomials xm+axk+b over GF(3) such that k is a multiple of w, where w is the bit length of the word of targeted CPU. We call the trinomials "reduction optimal trinomials (ROTs)." ROTs actually exist for several m's and for typical values of w = 16 and 32. We list them for extension degrees m = 97, 167, 193, 239, 317, and 487. These m's are derived from security considerations. Using ROTs, we are able to implement efficient modulo operations (reductions) for GF(3m) multiplication compared with cases in which other types of irreducible trinomials are used (e.g., trinomials with a minimum k for each m). The reason for this is that for cases using ROTs, the number of shift operations on multiple precision data is reduced to less than half compared with cases using other trinomials. Our implementation results show that programs of reduction specialized for ROTs are 20-30% faster on 32-bit CPU and approximately 40% faster on 16-bit CPU compared with programs using irreducible trinomials with general k.
ER -