Fast algorithms of public key cryptosystem based on Chebyshev polynomials over finite field

The computation of Chebyshev polynomial over finite field is a dominating operation for a public key cryptosystem. Two generic algorithms with running time of have been presented for this computation: the matrix algorithm and the characteristic polynomial algorithm, which are feasible but not optimized. In this paper, these two algorithms are modified in procedure to get faster execution speed. The complexity of modified algorithms is still, but the number of required operations is reduced, so the execution speed is improved. Besides, a new algorithm relevant with eigenvalues of matrix in representation of Chebyshev polynomials is also presented, which can further reduce the running time of that computation if certain conditions are satisfied. Software implementations of these algorithms are realized, and the running time comparison is given. Finally an efficient scheme for the computation of Chebyshev polynomial over finite field is presented.