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

7
views

0
downloads

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

Citation Formats

M. Cenk and F. Özbudak, “Improved Polynomial Multiplication Formulas over F-2 Using Chinese Remainder Theorem,” IEEE TRANSACTIONS ON COMPUTERS, vol. 58, no. 4, pp. 572–576, 2009, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/30949.