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
Improved Three-Way Split Formulas for Binary Polynomial and Toeplitz Matrix Vector Products
Date
2013-07-01
Author
Cenk, Murat
Hasan, M. Anwar
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
69
views
0
downloads
Cite This
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 are an optimization of Sunar's formulas. Then, we present formulas with five recursive multiplications based on field extension. In addition, we extend the latter formulas to TMVP. We evaluate the space and delay complexities when computations are performed in parallel and provide a comparison with best known methods.
Subject Keywords
Binary polynomial
,
Toeplitz matrix
,
Subquadratic space complexity multiplier
,
Finite field
URI
https://hdl.handle.net/11511/30721
Journal
IEEE TRANSACTIONS ON COMPUTERS
DOI
https://doi.org/10.1109/tc.2012.96
Collections
Graduate School of Applied Mathematics, Article
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...
A note on the minimal polynomial of the product of linear recurring sequences
Cakcak, E (1999-08-06)
Let F be a field of nonzero characteristic, with its algebraic closure, F. For positive integers a, b, let J(a, b) be the set of integers k, such that (x - 1)k is the minimal polynomial of the termwise product of linear recurring sequences sigma and tau in F ($) over bar, with minimal polynomials (x - 1)(a) and (x - 1)(b) respectively. This set plays a crucial role in the determination of the product of linear recurring sequences with arbitrary minimal polynomials. Here, we give an explicit formula to deter...
Improved three-way split formulas for binary polynomial multiplication
Cenk, Murat; Hasan, M. Anwar (2011-08-12)
In this paper we deal with 3-way split formulas for binary field multiplication with five recursive multiplications of smaller sizes. We first recall the formula proposed by Bernstein at CRYPTO 2009 and derive the complexity of a parallel multiplier based on this formula. We then propose a new set of 3-way split formulas with five recursive multiplications based on field extension. We evaluate their complexities and provide a comparison.
Improved Polynomial Multiplication Formulas over F-2 Using Chinese Remainder Theorem
Cenk, Murat; Özbudak, Ferruh (2009-04-01)
Let n and l be positive integers and f(x) be an irreducible polynomial over F-2 such that ldeg(f(x)) < 2n - 1. We obtain an effective upper bound for the multiplication complexity of n-term polynomials modulo f(x)(l). This upper bound allows a better selection of the moduli when the Chinese Remainder Theorem is used for polynomial multiplication over F-2. We give improved formulas to multiply polynomials of small degree over F-2. In particular, we improve the best known multiplication complexities over F-2 ...
On multiplication in finite fields
Cenk, Murat; Özbudak, Ferruh (2010-04-01)
We present a method for multiplication in finite fields which gives multiplication algorithms with improved or best known bilinear complexities for certain finite fields. Our method generalizes some earlier methods and combines them with the recently introduced complexity notion (M) over cap (q)(l), which denotes the minimum number of multiplications needed in F-q in order to obtain the coefficients of the product of two arbitrary l-term polynomials modulo x(l) in F-q[x]. We study our method for the finite ...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
M. Cenk and M. A. Hasan, “Improved Three-Way Split Formulas for Binary Polynomial and Toeplitz Matrix Vector Products,”
IEEE TRANSACTIONS ON COMPUTERS
, pp. 1345–1361, 2013, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/30721.