On computing the degree of a Chebyshev Polynomial from its value
Journal of Symbolic Computation, cilt.104, ss.159-167, 2021 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 104
- Basım Tarihi: 2021
- Doi Numarası: 10.1016/j.jsc.2020.04.011
- Dergi Adı: Journal of Symbolic Computation
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Computer & Applied Sciences, INSPEC, MathSciNet, zbMATH, DIALNET
- Sayfa Sayıları: ss.159-167
- Anahtar Kelimeler: Algorithms, Discrete logarithms, Chebyshev Polynomials, Interpolation in terms of the Chebyshev, Polynomials of the First Kind
- Kırklareli Üniversitesi Adresli: Evet
Özet
Algorithms for interpolating a polynomial f from its evaluation points whose running time depends on the sparsity t of the polynomial when it is represented as a linear combination of t Chebyshev Polynomials of the First Kind with non-zero scalar coefficients are given by Lakshman and Saunders (1995), Kaltofen and Lee (2003) and Arnold and Kaltofen (2015). The term degrees are computed from values of Chebyshev Polynomials of those degrees. We give an algorithm that computes those degrees in the manner of the Pohlig and Hellman algorithm (1978) for computing discrete logarithms modulo a prime number p when the factorization of p−1 (or p+1) has small prime factors, that is, when p−1 (or p+1) is smooth. Our algorithm can determine the Chebyshev degrees modulo such primes in bit complexity log(p)O(1) times the squareroot of the largest prime factor of p−1 (or p+1).