Timeline for Chebyshev polynomials of the first kind and primality testing
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 18, 2019 at 19:02 | comment | added | Pedja | wolframcloud.com/objects/princeps37/Published/Cheby.cdf | |
| Nov 26, 2017 at 13:42 | history | bounty ended | Pedja | ||
| Nov 26, 2017 at 2:39 | comment | added | Gene S. Kopp | @RyanO'Donnell While the algorithm is $\tilde{O}(\log^3 n)$ in the worst case, it is $\tilde{O}(\log^2 n)$ in the average case and in the average prime case, because $r$ may be taken to be $O_{\varepsilon}(1)$ except on a set of density $\varepsilon$ defined by congruence conditions. | |
| Nov 23, 2017 at 18:28 | comment | added | Vít Tuček | @მამუკაჯიბლაძე Right. So far we have two families of polynomials. Maybe we can identify more and then try to find out what they have in common which could perhaps give us some information on why such a conjecture might be true. | |
| Nov 23, 2017 at 17:44 | comment | added | მამუკა ჯიბლაძე | @VítTuček Acknowledged - after all this one is also a conjecture (so far). I don't think it will turn out easier to prove than theirs... | |
| Nov 23, 2017 at 15:06 | comment | added | Vít Tuček | @მამუკაჯიბლაძე Look at their conjecture in section six -- the one mentioned by the OP. I mean, it's great that this conjecture seems plausible also for $T_n$ and not only for $(x-1)^n$. Maybe it could be worthwhile to to try to find some large class of polynomials with this property. | |
| Nov 23, 2017 at 8:13 | comment | added | მამუკა ჯიბლაძე | @VítTuček You are right, that one is in fact simpler: have to find $n-1$st power of $x+a$ modulo $x^r-1$ instead of $n-1$st power of a 2$\times$2 matrix. On the other hand, in their case $r$ is larger and one has to test for several $a$s. | |
| Nov 22, 2017 at 13:48 | comment | added | Vít Tuček | @RyanO'Donnell Which is the same complexity as in the Agrawal et al. paper. I don't understand what, if anything, was gained by using Čebyšev's polynomials. | |
| Nov 22, 2017 at 3:25 | history | edited | მამუკა ჯიბლაძე | CC BY-SA 3.0 |
Sorry, `Inner` does not work this way
|
| Nov 22, 2017 at 3:24 | comment | added | Ryan O'Donnell | Looks like using the FFT method to multiply polynomials, and assuming r = O(log n), the whole algorithm takes O(log^3 n) time (times some polyloglogs, depending on your exact model of computation). | |
| Nov 22, 2017 at 2:46 | history | edited | მამუკა ჯიბლაძე | CC BY-SA 3.0 |
2 is prime
|
| Nov 22, 2017 at 2:33 | history | edited | მამუკა ჯიბლაძე | CC BY-SA 3.0 |
more code optimization
|
| Nov 22, 2017 at 2:19 | history | edited | მამუკა ჯიბლაძე | CC BY-SA 3.0 |
deleted 8 characters in body
|
| Nov 22, 2017 at 2:08 | history | edited | მამუკა ჯიბლაძე | CC BY-SA 3.0 |
another slight code improvement
|
| Nov 22, 2017 at 2:02 | history | edited | მამუკა ჯიბლაძე | CC BY-SA 3.0 |
another slight code improvement
|
| Nov 22, 2017 at 1:40 | history | edited | მამუკა ჯიბლაძე | CC BY-SA 3.0 |
it obviously will eventually cross the zero line (when the time needed exceeds one unit)
|
| Nov 21, 2017 at 22:23 | comment | added | მამუკა ჯიბლაძე | @IgorRivin Pleasure is mine indeed :) | |
| Nov 21, 2017 at 21:53 | history | edited | მამუკა ჯიბლაძე | CC BY-SA 3.0 |
slight improvement in the code
|
| Nov 21, 2017 at 19:48 | history | edited | მამუკა ჯიბლაძე | CC BY-SA 3.0 |
replaced time/log by log(time)/loglog
|
| Nov 21, 2017 at 19:39 | comment | added | Igor Rivin | That IS amazing, thanks for investigating! | |
| Nov 21, 2017 at 18:47 | history | answered | მამუკა ჯიბლაძე | CC BY-SA 3.0 |