The search functionality is under construction.

The search functionality is under construction.

The η_{T} pairing for supersingular elliptic curves over GF(3^{m}) has been paid attention because of its computational efficiency. Since most computation parts of the η_{T} pairing are GF(3^{m}) 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(3^{m}) multiplication and propose using irreducible trinomials *x*^{m}+*ax*^{k}+*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(3^{m}) 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*.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2379-2386

- Publication Date
- 2008/09/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1093/ietfec/e91-a.9.2379

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category

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.

Copy

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(3^{m}) has been paid attention because of its computational efficiency. Since most computation parts of the η_{T} pairing are GF(3^{m}) 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(3^{m}) multiplication and propose using irreducible trinomials *x*^{m}+*ax*^{k}+*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(3^{m}) 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

Copy

@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(3^{m}) has been paid attention because of its computational efficiency. Since most computation parts of the η_{T} pairing are GF(3^{m}) 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(3^{m}) multiplication and propose using irreducible trinomials *x*^{m}+*ax*^{k}+*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(3^{m}) 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},}

Copy

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(3^{m}) has been paid attention because of its computational efficiency. Since most computation parts of the η_{T} pairing are GF(3^{m}) 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(3^{m}) multiplication and propose using irreducible trinomials *x*^{m}+*ax*^{k}+*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(3^{m}) 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 -