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
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
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 Polynomial Multiplication Formulas over F-2 Using Chinese Remainder Theorem
Date
2009-04-01
Author
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
195
views
0
downloads
Cite This
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 in the literature in some cases.
Subject Keywords
Finite field polynomial multiplication
,
Chinese remainder theorem
URI
https://hdl.handle.net/11511/30949
Journal
IEEE TRANSACTIONS ON COMPUTERS
DOI
https://doi.org/10.1109/tc.2008.207
Collections
Graduate School of Applied Mathematics, Article
Suggestions
OpenMETU
Core
Results on complexity of multiplication over finite fields
Cenk, Murat; Özbudak, Ferruh; Department of Cryptography (2009)
Let n and l be positive integers and f (x) be an irreducible polynomial over Fq such that ldeg( f (x)) < 2n - 1, where q is 2 or 3. 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 Chinese Remainder Theorem is used for polynomial multiplication over Fq. We give improved formulae to multiply polynomials of small degree over Fq. In particular we improve the best known multiplication complexi...
Efficient multiplication in double-struck F sign3ℓm, m ≥ 1 and 5 ≤ ℓ ≤ 18
Cenk, Murat; Özbudak, Ferruh (2008-06-14)
Using a method based on Chinese Remainder Theorem for polynomial multiplication and suitable reductions, we obtain an efficient multiplication method for finite fields of characteristic 3. Large finite fields of characteristic 3 are important for pairing based cryptography [3]. For 5 <= l <= 18, we show that our method gives canonical multiplication formulae over F-3lm for any m >= 1 with the best multiplicative complexity improving the bounds in [6]. We give explicit formula in the case F-36.97.
Multiplication of polynomials modulo x(n)
Cenk, Murat; Özbudak, Ferruh (2011-07-01)
Let n, l be positive integers with l <= 2n - 1. Let R be an arbitrary nontrivial ring, not necessarily commutative and not necessarily having a multiplicative identity and R[x] be the polynomial ring over R. In this paper, we give improved upper bounds on the minimum number of multiplications needed to multiply two arbitrary polynomials of degree at most (n - 1) modulo x(n) over R. Moreover, we introduce a new complexity notion, the minimum number of multiplications needed to multiply two arbitrary polynomi...
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...
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...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
M. Cenk and F. Özbudak, “Improved Polynomial Multiplication Formulas over F-2 Using Chinese Remainder Theorem,”
IEEE TRANSACTIONS ON COMPUTERS
, pp. 572–576, 2009, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/30949.