Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
A New Representation of Elements of Binary Fields with Subquadratic Space Complexity Multiplication of Polynomials
Date
2013-10-01
Author
Özbudak, Ferruh
Cenk, Murat
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
191
views
0
downloads
Cite This
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(2(571)) since there is no ONB for the corresponding extension. This representation can be used to obtain more efficient finite field arithmetic.
Subject Keywords
Hermite polynomials
,
Binary field representation
,
Polynomial multiplication
,
Subquadratic space complexity
URI
https://hdl.handle.net/11511/31897
Journal
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
DOI
https://doi.org/10.1587/transfun.e96.a.2016
Collections
Graduate School of Applied Mathematics, Article
Suggestions
OpenMETU
Core
Polynomial Multiplication over Binary Fields Using Charlier Polynomial Representation with Low Space Complexity
AKLEYLEK, SEDAT; Cenk, Murat; Özbudak, Ferruh (2010-12-15)
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 repre...
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...
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...
A Hilbert Space of Probability Mass Functions and Applications on the Sum-Product Algorithm
Bayramoglu, Muhammet Fatih; Yılmaz, Ali Özgür (2008-09-05)
In this paper a Hilbert space structure of probability mass functions (PMF) will be presented. The tools provided by the Hilbert space, specifically the norm and the inner product, may be useful while analyzing and improving the sum-product algorithm in many aspects. Our approach provides a metric distance between PMFs and a new point of a view of the log-likelihood ratio (LLR) such that the LLR representation is nothing but a Hilbert space representation.
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
F. Özbudak and M. Cenk, “A New Representation of Elements of Binary Fields with Subquadratic Space Complexity Multiplication of Polynomials,”
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
, pp. 2016–2024, 2013, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31897.