Multiplication of polynomials modulo x(n)

Date

2011-07-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

192
views

0
downloads

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 polynomials of degree at most (n - 1) modulo x(l) over R. This new complexity notion provides improved bounds on the minimum number of multiplications needed to multiply two arbitrary polynomials of degree at most (n - 1) modulo x(n) over R.

Subject Keywords

Multiplication of power series, Multiplication algorithms, Multiplicative complexity, Multiplication of polynomials

URI

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

Journal

THEORETICAL COMPUTER SCIENCE

DOI

https://doi.org/10.1016/j.tcs.2011.02.031

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

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 the arithmetic complexity of Strassen-like matrix multiplications Cenk, Murat (2017-05-01) The Strassen algorithm for multiplying 2 x 2 matrices requires seven multiplications and 18 additions. The recursive use of this algorithm for matrices of dimension n yields a total arithmetic complexity of (7n(2.81) - 6n(2)) for n = 2(k). Winograd showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying 2 x 2 matrices with seven multiplications is called a Strassen-like algorithm. Winograd also discovered an additively optimal Stras...
On the Polynomial Multiplication in Chebyshev Form Akleylek, Sedat; Cenk, Murat; Özbudak, Ferruh (2012-04-01) We give an efficient multiplication method for polynomials in Chebyshev form. This multiplication method is different from the previous ones. Theoretically, we show that the number of multiplications is at least as good as Karatsuba-based algorithm. Moreover, using the proposed method, we improve the number of additions slightly. We remark that our method works efficiently for any N and it is easy to implement. To the best of our knowledge, the proposed method has the best multiplication and addition comple...
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.

Citation Formats

M. Cenk and F. Özbudak, “Multiplication of polynomials modulo x(n),” THEORETICAL COMPUTER SCIENCE, pp. 3451–3462, 2011, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/30894.