**Evaluation Methods for Chebyshev Polynomials**

*Zhengjun Cao and Lihua Liu and Leming Hong*

**Abstract: **The security of cryptosystems based on Chebyshev recursive relation, T_n(x)=2xT_{n-1}(x)-T_{n-2}(x), relies on the difficulty of finding the large degree of Chebyshev polynomials from given parameters. The relation cannot be used to evaluate T_n(x) if n is very large. We will investigate other three methods: matrix-multiplication-based evaluation, halve-and-square evaluation, and root-extraction-based evaluation. Though they have the same theoretical complexity O(\log n\log^2p), we find in some cases the root-extraction-based method is more efficient than the others, which is as fast as the general modular exponentiation. The result indicates that the hardness of some cryptosystems based on modular Chebyshev polynomials
is almost equivalent to that of solving general discrete logarithm.

**Category / Keywords: **foundations / Chebyshev polynomials; matrix-multiplication-based evaluation; halve-and-square evaluation; root-extraction-based evaluation.

**Date: **received 29 Oct 2020

**Contact author: **caozhj at shu edu cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20201102:104014 (All versions of this report)

**Short URL: **ia.cr/2020/1365

[ Cryptology ePrint archive ]