Timeline for Is there an explicit expression for Chebyshev polynomials modulo $x^r-1$?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 12, 2019 at 15:09 | comment | added | Peter Taylor | And, in the same way that Fibonacci number calculation by matrix powers can be optimised, this can be optimised with the recurrences $T_{2n} = 2 T_n{}^2 - 1$ and $T_{2n+1} = 2 T_n T_{n+1} - x$ | |
| Dec 7, 2017 at 5:09 | comment | added | Dendi Suhubdy | We tried implementing the algorithm in C++ here without directly computing T_n(x) github.com/dendisuhubdy/Chebyshev-primality-test/blob/master/… | |
| Nov 21, 2017 at 19:00 | comment | added | მამუკა ჯიბლაძე | 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 $\log n$) | |
| Nov 21, 2017 at 15:57 | vote | accept | მამუკა ჯიბლაძე | ||
| Nov 21, 2017 at 15:54 | history | answered | Lucia | CC BY-SA 3.0 |