Timeline for Primality test for specific class of generalized Fermat numbers
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 18, 2020 at 2:18 | comment | added | Chua KS | It seems useful to state many of your tests in term of Chebyshev.Eg. Lucas-Lehmer for Mersenne prime $M_p=2^p-1$ can be rephrased as $M_p$ is prime iff $T_{2^{p-2}}(2)=0$ mod $M_p$ and the Chebyshev rule $T_m(T_n(x))=T_{mn}(x)$ implied many possible method for computing the residue. Since $2^{p-2}=4^{(p-3)/2}.2$, one can iterate with $T_4$ as $T_{2^{p-2}}(2)=T_4^{(p-3)/2}(T_2(2))$ mod $M_p$. This halfed the number of steps but evaluating $T_4$ is more expansive. Every partition of $p-2$ into positive parts give a different way to compute the residue. At least good for checking correctness | |
| Aug 15, 2020 at 4:48 | comment | added | Chua KS | $P_m(x)=2T_m(x/2)$ where $T_m(x)$ is the Chebyshev polynomial of the first kind. The claim can be rephrased as $F_{p,n}$ is prime iff $T_{2^{2^n-2}p^{2^n}}(4)=0$ mod $F_{p,n}$. Since $T_m(T_n(x))=T_{mn}(x)$, the RHS can be computed efficiently as $T_{ (2p)}^{2^n-2}(T_{p^2}(4))$ mod $F_{p,n}$, where the $2^n-2$ in the power means iteration. | |
| Aug 13, 2020 at 3:50 | history | edited | Pedja | CC BY-SA 4.0 |
Changed notation
|
| Aug 10, 2020 at 12:46 | history | edited | Pedja | CC BY-SA 4.0 |
Added some constraints to the claim
|
| Jun 14, 2018 at 6:19 | history | edited | Pedja | CC BY-SA 4.0 |
added link to the GitHub repository
|
| S Apr 25, 2018 at 10:59 | history | bounty ended | CommunityBot | ||
| S Apr 25, 2018 at 10:59 | history | notice removed | CommunityBot | ||
| Apr 24, 2018 at 21:46 | comment | added | Steven Stadnicki | It might be worth noting that the $P_m$ satisfy a particularly straightforward linear recurrence. | |
| Apr 24, 2018 at 19:00 | history | edited | Pedja | CC BY-SA 3.0 |
fixed grammar
|
| Apr 22, 2018 at 13:43 | comment | added | Pedja | @MaxAlekseyev Actually this is a generalization of Inkeri's primality test for Fermat numbers...Reference : Tests for primality, Ann. Acad. Sci. Fenn. Ser. A I 279 (1960), 1-19. | |
| Apr 22, 2018 at 13:09 | comment | added | Max Alekseyev | Looks like a generalization of arxiv.org/abs/0705.3664 (which concerns $b=2$) | |
| S Apr 17, 2018 at 9:29 | history | bounty started | Pedja | ||
| S Apr 17, 2018 at 9:29 | history | notice added | Pedja | Draw attention | |
| Apr 17, 2018 at 9:28 | history | edited | Pedja | CC BY-SA 3.0 |
added some relevant informations
|
| Apr 16, 2018 at 17:28 | history | edited | Pedja | CC BY-SA 3.0 |
reworded a question
|
| Apr 8, 2017 at 11:04 | history | edited | Pedja | CC BY-SA 3.0 |
improved formatting
|
| Apr 8, 2017 at 10:55 | history | edited | Pedja | CC BY-SA 3.0 |
fixed grammar
|
| Jul 1, 2014 at 10:13 | review | First posts | |||
| Jul 1, 2014 at 10:21 | |||||
| Jul 1, 2014 at 9:57 | history | asked | Pedja | CC BY-SA 3.0 |