On the Polynomial Multiplication in Chebyshev Form

Date

2012-04-01

Author

Akleylek, Sedat
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

262
views

0
downloads

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 complexity for the N-term polynomial multiplication in Chebyshev form with 3 <= N <= 13.

Subject Keywords

Chebyshev polynomials, Theory of computation, Multiplication of polynomials, Arithmetic complexity

URI

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

Journal

IEEE TRANSACTIONS ON COMPUTERS

DOI

https://doi.org/10.1109/tc.2011.38

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

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 computation of generalized division polynomials Küçüksakallı, Ömer (2015-01-01) We give an algorithm to compute the generalized division polynomials for elliptic curves with complex multiplication. These polynomials can be used to generate the ray class fields of imaginary quadratic fields over the Hilbert class field with no restriction on the conductor.
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.
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...
On algebraic K-theory of real algebraic varieties with circle action Ozan, Yıldıray (Elsevier BV, 2002-05-24) Assume that X is a compact connected orientable nonsingular real algebraic variety with an algebraic free S-1-action so that the quotient Y=X/S-1 is also a real algebraic variety. If pi:X --> Y is the quotient map then the induced map between reduced algebraic K-groups, tensored with Q, pi* : (K) over bar (0)(R(Y, C)) circle times Q --> (K) over bar (0)(R(X, C)) circle times Q is onto, where R(X, C) = R(X) circle times C, R(X) denoting the ring of entire rational (regular) functions on the real algebraic va...

Citation Formats

S. Akleylek, M. Cenk, and F. Özbudak, “On the Polynomial Multiplication in Chebyshev Form,” IEEE TRANSACTIONS ON COMPUTERS, pp. 584–587, 2012, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/32195.