Timeline for Chebyshev polynomials of the first kind and primality testing
Current License: CC BY-SA 4.0
31 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 6, 2020 at 4:53 | history | edited | Pedja | CC BY-SA 4.0 |
Fixed broken link
|
| Jun 6, 2020 at 4:46 | comment | added | Simd | What was the conclusion on this new test? Did it turn out to be correct/faster/better? | |
| Jun 6, 2020 at 3:17 | history | edited | Pedja | CC BY-SA 4.0 |
Added two more journals
|
| Apr 20, 2020 at 4:53 | history | edited | Pedja | CC BY-SA 4.0 |
Added link to the Google Play
|
| Jan 26, 2020 at 5:11 | history | edited | Pedja | CC BY-SA 4.0 |
Updated a link to the Sage Math Cell
|
| Nov 27, 2019 at 20:08 | answer | added | Max Alekseyev | timeline score: 7 | |
| Nov 22, 2019 at 10:03 | history | edited | Pedja | CC BY-SA 4.0 |
added link to the Amazon App Store
|
| Nov 7, 2019 at 9:35 | comment | added | Pedja | @DavidESpeyer Journal of Number Theory also allows authors to make their individual articles open. | |
| Nov 6, 2019 at 16:26 | comment | added | David E Speyer | Not that I think I am going to earn the reward, but could you please choose a non-Elsevier journal? Algebra and Number Theory is an open journal whose standards are at least as high. | |
| Nov 6, 2019 at 16:21 | comment | added | David E Speyer | Since no one has said this explicitly yet: It is easy to see that, if $n$ is prime, then $T_n(x) \equiv x^n \bmod n$. Indeed, $T_n(x)$ is the unique polynomial such that $T_n(u+u^{-1}) = u^n + u^{-n}$ and, if $n$ is prime and we take coefficients modulo $n$, then $x^n$ has this property. | |
| Nov 6, 2019 at 11:11 | history | edited | Pedja | CC BY-SA 4.0 |
added link to the gist
|
| Oct 17, 2019 at 14:04 | history | edited | Pedja | CC BY-SA 4.0 |
Offered a bounty
|
| Jul 6, 2019 at 14:58 | comment | added | Pedja | Generalization of this claim and an attempted proof of it can be found here. | |
| May 14, 2019 at 20:43 | history | edited | Pedja | CC BY-SA 4.0 |
Added link to the Sage Cell
|
| Dec 7, 2017 at 5:10 | comment | added | Dendi Suhubdy | @IgoRivin We tried implementing the algorithm in C++ here without directly computing T_n(x) github.com/dendisuhubdy/Chebyshev-primality-test/blob/master/…. This is really cool! | |
| S Nov 26, 2017 at 13:42 | history | bounty ended | Pedja | ||
| S Nov 26, 2017 at 13:42 | history | notice removed | Pedja | ||
| Nov 21, 2017 at 18:53 | comment | added | მამუკა ჯიბლაძე | @IgorRivin Thanks to the answer by Lucia to that question, I believe the answer to your question is more than positive - seems like this produces a logarithmically efficient primality test. I tried to demonstrate it in another answer below. | |
| Nov 21, 2017 at 18:47 | answer | added | მამუკა ჯიბლაძე | timeline score: 33 | |
| Nov 21, 2017 at 13:38 | comment | added | მამუკა ჯიბლაძე | I've now posted a separate question about that | |
| Nov 21, 2017 at 12:29 | comment | added | მამუკა ჯიბლაძე | @IgorRivin Seems that it depends on how fast one can find $T_n(x)\mod x^r-1$ (for very small $r$, about $\log n$) without computing $T_n(x)$ itself completely. The way it is implemented now, the whole $T_n(x)$ is found first, and I think it is worse than polynomial then. | |
| Nov 19, 2017 at 18:32 | answer | added | მამუკა ჯიბლაძე | timeline score: 8 | |
| Nov 19, 2017 at 15:01 | history | edited | Pedja |
retaged
|
|
| S Nov 19, 2017 at 13:50 | history | bounty started | Pedja | ||
| S Nov 19, 2017 at 13:50 | history | notice added | Pedja | Draw attention | |
| Nov 19, 2017 at 10:48 | history | edited | Pedja | CC BY-SA 3.0 |
simplified the code
|
| Nov 18, 2017 at 8:01 | comment | added | Pedja | @IgorRivin Please see analysis at the top of the page 8 . Since these two algorithms are similar their time complexities should be the same . | |
| Nov 17, 2017 at 17:07 | comment | added | Igor Rivin | This is very cool, but, if true, can it be made into a useful algorithm? As stated it is about an $O(n^2)$ algorithm to determine primality of $n$ | |
| Nov 17, 2017 at 16:04 | comment | added | Pedja | @მამუკა ჯიბლაძე A stack overflow error has occurred . | |
| Nov 17, 2017 at 14:57 | comment | added | მამუკა ჯიბლაძე |
I tried it with $n=311231$ and got this: PARI/GP interpreter crashed -- automatically restarting. *** at top-level: if(Mod((polchebyshev(n,1,x))%(x^r-1),n)-( *** ^-------------------- *** incorrect type in gtos [integer expected] (t_POL).
|
|
| Nov 17, 2017 at 13:49 | history | asked | Pedja | CC BY-SA 3.0 |