IEICE TRANSACTIONS on Fundamentals
A New Representation of Elements of Binary Fields with Subquadratic Space Complexity Multiplication of Polynomials
Summary :
In this paper, Hermite polynomial representation is proposed as an alternative way to represent finite fields of characteristic two. We show that multiplication in Hermite polynomial representation can be achieved with subquadratic space complexity. This representation enables us to find binomial or trinomial irreducible polynomials which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. We then show that the product of two elements in Hermite polynomial representation can be performed as Toeplitz matrix-vector product. This representation is very interesting for NIST recommended binary field GF(2571) since there is no ONB for the corresponding extension. This representation can be used to obtain more efficient finite field arithmetic.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E96-A No.10 pp.2016-2024
- Publication Date
- 2013/10/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E96.A.2016
- Type of Manuscript
- PAPER
- Category
- General Fundamentals and Boundaries
Authors
Ferruh ÖZBUDAK
METU,Institute of Applied Mathematics, METU
Sedat AKLEYLEK
Institute of Applied Mathematics, METU,Ondokuz May{i}s University
Murat CENK
Institute of Applied Mathematics, METU,University of Waterloo
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Ferruh ÖZBUDAK, Sedat AKLEYLEK, Murat CENK, "A New Representation of Elements of Binary Fields with Subquadratic Space Complexity Multiplication of Polynomials" in IEICE TRANSACTIONS on Fundamentals,
vol. E96-A, no. 10, pp. 2016-2024, October 2013, doi: 10.1587/transfun.E96.A.2016.
Abstract: In this paper, Hermite polynomial representation is proposed as an alternative way to represent finite fields of characteristic two. We show that multiplication in Hermite polynomial representation can be achieved with subquadratic space complexity. This representation enables us to find binomial or trinomial irreducible polynomials which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. We then show that the product of two elements in Hermite polynomial representation can be performed as Toeplitz matrix-vector product. This representation is very interesting for NIST recommended binary field GF(2571) since there is no ONB for the corresponding extension. This representation can be used to obtain more efficient finite field arithmetic.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E96.A.2016/_p
Copy
@ARTICLE{e96-a_10_2016,
author={Ferruh ÖZBUDAK, Sedat AKLEYLEK, Murat CENK, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A New Representation of Elements of Binary Fields with Subquadratic Space Complexity Multiplication of Polynomials},
year={2013},
volume={E96-A},
number={10},
pages={2016-2024},
abstract={In this paper, Hermite polynomial representation is proposed as an alternative way to represent finite fields of characteristic two. We show that multiplication in Hermite polynomial representation can be achieved with subquadratic space complexity. This representation enables us to find binomial or trinomial irreducible polynomials which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. We then show that the product of two elements in Hermite polynomial representation can be performed as Toeplitz matrix-vector product. This representation is very interesting for NIST recommended binary field GF(2571) since there is no ONB for the corresponding extension. This representation can be used to obtain more efficient finite field arithmetic.},
keywords={},
doi={10.1587/transfun.E96.A.2016},
ISSN={1745-1337},
month={October},}
Copy
TY - JOUR
TI - A New Representation of Elements of Binary Fields with Subquadratic Space Complexity Multiplication of Polynomials
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2016
EP - 2024
AU - Ferruh ÖZBUDAK
AU - Sedat AKLEYLEK
AU - Murat CENK
PY - 2013
DO - 10.1587/transfun.E96.A.2016
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E96-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2013
AB - In this paper, Hermite polynomial representation is proposed as an alternative way to represent finite fields of characteristic two. We show that multiplication in Hermite polynomial representation can be achieved with subquadratic space complexity. This representation enables us to find binomial or trinomial irreducible polynomials which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. We then show that the product of two elements in Hermite polynomial representation can be performed as Toeplitz matrix-vector product. This representation is very interesting for NIST recommended binary field GF(2571) since there is no ONB for the corresponding extension. This representation can be used to obtain more efficient finite field arithmetic.
ER -
English
