An alternative class of irreducible polynomials for optimal extension fields

作者：Li, Yin^*; Chen, Gong liang; Li, Jian hua

来源：Designs, Codes and Cryptography, 2011, 60(2): 171-182.

DOI：10.1007/s10623-010-9424-6

• Irreducible polynomial
• Modular multiplication
• Optimal extension fields
• Elliptic curve
• Cryptography

Optimal extension fields (OEF) are a class of finite fields used to achieve efficient field arithmetic, especially required by elliptic curve cryptosystems (ECC). In software environment, OEFs are preferable to other methods in performance and memory requirement. However, the irreducible binomials required by OEFs are quite rare. Sometimes irreducible trinomials are alternative choices when irreducible binomials do not exist. Unfortunately, trinomials require more operations for field multiplication and thereby affect the efficiency of OEF. To solve this problem, we propose a new type of irreducible polynomials that are more abundant and still efficient for field multiplication. The proposed polynomial takes the advantage of polynomial residue arithmetic to achieve high performance for field multiplication which costs O(m (3/2)) operations in F-p. Extensive simulation results demonstrate that the proposed polynomials roughly outperform irreducible binomials by 20% in some finite fields of medium prime characteristic. So this work presents an interesting alternative for OEFs.

• 出版日期2011-8
• 单位上海交通大学