On computing the degree of a Chebyshev Polynomial from its value. (May 2021)

• Record Type: Journal Article
• Authors: Imamoglu, Erdal; Kaltofen, Erich L.
• Is Part Of: Journal of symbolic computation. Volume 104(2021)
• Page Start: 159
• Page End: 167
• Publication Date: 2021-05
• Subjects: Algorithms -- Discrete logarithms -- Chebyshev Polynomials -- Interpolation in terms of the Chebyshev Polynomials of the First Kind; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2020.04.011
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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 ).