Timeline for Proof for new deterministic primality test possible?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| May 26, 2016 at 15:14 | comment | added | Max Alekseyev | Tested all $n$ below $10^{11}$, no counterexamples found. | |
| May 24, 2016 at 9:19 | comment | added | Guest_2015 | @SJR: There is no special reason. I have choosen it, because it is simple. | |
| May 24, 2016 at 7:58 | comment | added | Sidney Raffer | @Guest: Did you have a special reason for choosing $n^2+4$, rather than any other polynomial whose values are all congruent to 3 or 5 mod 8? | |
| May 23, 2016 at 8:16 | comment | added | Guest_2015 | @kodlu: 1.) I did not say, this test is a general primality test. As anyone can read, it is a primality test for numbers of the form $2^2+n^2$. 2.) If conjecture holds, it is definitely a deterministic test. 3.) If we take for $n$ numbers of the form $n=2^k+1$, this primality test has - with fast modular exponentiation - nearly the same time complexity as Lucas-Lehmer test. So this test is also for huge numbers usable. | |
| May 22, 2016 at 22:18 | comment | added | kodlu | Nice question. Even if true, it wouldn't give a deterministic primality test as stated, since it can't be applied to arbitrary candidates for primality. I'd call it a prime distinguisher. | |
| May 22, 2016 at 13:56 | comment | added | Max Alekseyev | No counterexamples for $n$ below $2^{32}$. In fact, below $2^{64}$ there is only one pseudoprime $N$ of the form $n^2+4$ (for $n=22047$), but it does not divive $2^{(N-1)/2}+1$. | |
| May 22, 2016 at 13:04 | comment | added | Sidney Raffer | Related: mathoverflow.net/questions/234348/… | |
| May 22, 2016 at 12:25 | comment | added | Carlo Beenakker | the "only if" part is Fermat's little theorem | |
| May 22, 2016 at 11:33 | comment | added | joro | Couldn't find counterexamples up to n=10^8, might be wrong. | |
| May 22, 2016 at 10:13 | history | asked | Guest_2015 | CC BY-SA 3.0 |