19

This is an immediate successor of Chebyshev polynomials of the first kind and primality testing and does not have any other motivation - although original motivation seems to be huge since a positive answer (if not too complicated) would give a very efficient primality test (see the linked question for details).

Recall that the Chebyshev polynomials Tn(x) are defined by T0(x)=1, T1(x)=x and Tn+1(x)=2xTn(x)−Tn−1(x), and there are several explicit expressions for their coefficients. Rather than writing them down (you can find them at the Wikipedia link anyway), let me just give a couple of examples: T15(x)=−15x(1−47⋅82⋅3x2+426⋅7⋅8⋅92⋅3⋅4⋅5x4−438⋅9⋅102⋅3⋅4x6+4410⋅112⋅3x8−45122x10+46x12)+47x15 T17(x)=17x(1−48⋅92⋅3x2+427⋅8⋅9⋅102⋅3⋅4⋅5x4−438⋅9⋅10⋅112⋅3⋅4⋅5x6+4410⋅11⋅122⋅3⋅4x8−4512⋅132⋅3x10+46142x12−47x14)+48x17 It seems that n is a prime if and only if all the ratios in the parentheses are integers; this is most likely well known and easy to show.

The algorithm described in the above question requires determining whether, for an odd n, coefficients of the remainder from dividing Tn(x)−xn by xr−1, for some fairly small prime r (roughly ∼logn) are all divisible by n. In other words, denoting by aj, j=0,1,2,... the coefficients of Tn(x)−xn, we have to find out whether the sum sj:=aj+aj+r+aj+2r+... is divisible by n for each j=0,1,...,r−1.

The question then is: given r and n as above (n odd, r a prime much smaller than n), is there an efficient method to find these sums sj without calculating all aj? I. e., can one compute Tn(x) modulo xr−1 (i. e. in a ring where xr=1) essentially easier than first computing the whole Tn(x) and then dividing by xr−1 in the ring of polynomials?

(As already said, only the question of divisibility of the result by n is required; also r is explicitly given (it is the smallest prime with n not ±1 modulo r). This might be easier to answer than computing the whole polynomials mod xr−1.)

მამუკა ჯიბლაძე
  • 17,468

2 Answers2

28

There's a rapid algorithm to compute Tn(x) modulo (n,xr−1). Note that (Tn(x)Tn−1(x))=(2x−110)(Tn−1(x)Tn−2(x))=(2x−110)n−1(x1). Now you can compute these matrix powers all modulo (n,xr−1) rapidly by repeated squaring. Clearly O(logn) multiplications (of 2×2 matrices) are required, and the matrices have entries that are polynomials of degree at most r and coefficients bounded by n. So the complexity is a polynomial in r and logn.

Lucia
  • 43,311
  • 1
    Thank you very much! I've now implemented your algorithm at another answer and that very primitive implementation seems to really be logarithmically efficient (the actual r needed is itself somewhere near logn) – მამუკა ჯიბლაძე Nov 21 '17 at 19:00
  • 3
    We tried implementing the algorithm in C++ here without directly computing T_n(x) https://github.com/dendisuhubdy/Chebyshev-primality-test/blob/master/src/chebyshev-primality-test.cpp – Dendi Suhubdy Dec 07 '17 at 05:09
  • 2
    And, in the same way that Fibonacci number calculation by matrix powers can be optimised, this can be optimised with the recurrences T2n=2Tn2−1 and T2n+1=2TnTn+1−x – Peter Taylor Sep 12 '19 at 15:09
5

The coefficient of xj in (T_n(x)\bmod (x^r-1)) equals the coefficient of t^{n+r-j-1} in \frac{(1+t^2)^{r-j}}{2^{r-j}} \frac{((1+t^2)^{r-1}t - 2^{r-1}t^{r-1})}{((1+t^2)^r - 2^rt^r)}. This coefficient can be explicitly computed as \sum_{k\geq 0} 2^{rk-r+j} \left( \binom{r-1-j-rk}{\frac{n+r-j-2-rk}{2}} - 2^{r-1}\binom{-j-rk}{\frac{n-j-rk}{2}}\right). (here the binomial coefficients are zero whenever their lower indices are noninteger or negative)

Max Alekseyev
  • 30,425