Polynomial Multiplication over Binary Fields Using Charlier Polynomial Representation with Low Space Complexity

Date

2010-12-15

Author

AKLEYLEK, SEDAT
Cenk, Murat
Özbudak, Ferruh

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

260
views

0
downloads

In this paper, we give a new way to represent certain finite fields GF(2(n)). This representation is based on Charlier polynomials. We show that multiplication in Charlier polynomial representation can be performed with subquadratic space complexity. One can obtain binomial or trinomial irreducible polynomials in Charlier polynomial representation which allows us faster modular reduction over binary fields when there is no desirable such low weight irreducible polynomial in other representations. This representation is very interesting for NIST recommended binary field GF(2(283)) since there is no ONB for the corresponding extension. We also note that recommended NisT and SEC binary fields can be constructed with low weight Charlier polynomials.

Subject Keywords

Charlier polynomials, Binary field representation, Polynomial multiplication, Subquadratic space complexity

URI

https://hdl.handle.net/11511/31174

DOI

https://doi.org/10.1007/978-3-642-17401-8_17

Collections

Graduate School of Applied Mathematics, Conference / Seminar

Suggestions

OpenMETU
Core

A New Representation of Elements of Binary Fields with Subquadratic Space Complexity Multiplication of Polynomials Özbudak, Ferruh; Cenk, Murat (2013-10-01) 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 pro...
On the arithmetic operations over finite fields of characteristic three with low complexity AKLEYLEK, SEDAT; Özbudak, Ferruh; Özel, Claire Susanna (2014-03-15) In this paper, the Hermite polynomial representation is adapted as a new way to represent certain finite fields of characteristic three. We give the multiplication method to multiply two elements of F-3n in the Hermite polynomial representation with subquadratic computational complexity by using a divide-and-conquer idea. We show that in some cases there is a set of irreducible binomials in the Hermite polynomial representation to obtain modular reduction with a lower addition complexity than the standard p...
Improved Three-Way Split Formulas for Binary Polynomial and Toeplitz Matrix Vector Products Cenk, Murat; Hasan, M. Anwar (2013-07-01) In this paper, we consider three-way split formulas for binary polynomial multiplication and Toeplitz matrix vector product (TMVP). We first recall the best known three-way split formulas for polynomial multiplication: the formulas with six recursive multiplications given by Sunar in a 2006 IEEE Transactions on Computers paper and the formula with five recursive multiplications proposed by Bernstein at CRYPTO 2009. Second, we propose a new set of three-way split formulas for polynomial multiplication that a...
Multiplication in a Galois Ring AKLEYLEK, SEDAT; Özbudak, Ferruh (2015-09-18) In this paper, we focus on the efficient multiplication in a Galois ring of the size 4(n), where n is a positive integer. We consider to adapt the finite field multiplication methods to the Galois ring multiplication. We give the polynomial multiplication in the Galois ring as a Toeplitz matrix-vector multiplication design with a modification used in finite fields of characteristic two. By this method, we reduce the multiplication complexity. Note that the proposed approach can be easily generalized to Galo...
New Efficient Algorithms for Multiplication Over Fields of Characteristic Three Cenk, Murat; Hasan, M. Anwar (2018-03-01) In this paper, we first present an enhancement of the well-known Karatsuba 2-way and 3-way algorithms for characteristic three fields, denoted by where nae1. We then derive a 3-way polynomial multiplication algorithm with five 1/3 sized multiplications that use interpolation in . Following the computation of the arithmetic and delay complexity of the proposed algorithm, we provide the results of our hardware implementation of polynomial multiplications over and . The final proposal is a new 3-way polynomial...

Citation Formats

S. AKLEYLEK, M. Cenk, and F. Özbudak, “Polynomial Multiplication over Binary Fields Using Charlier Polynomial Representation with Low Space Complexity,” 2010, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31174.