Timeline for Proof for new deterministic primality test
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 2, 2023 at 2:32 | comment | added | Max Alekseyev | Just for the record, the question was cross-posted to MSE: math.stackexchange.com/q/1410031 | |
| Apr 1, 2023 at 1:59 | answer | added | Max Alekseyev | timeline score: 30 | |
| Sep 22, 2015 at 21:03 | comment | added | Włodzimierz Holsztyński | @JeppeStigNielsen -- thank you. *** (Not all my q's are hard :-) ). | |
| Sep 22, 2015 at 9:45 | comment | added | Jeppe Stig Nielsen | @WłodzimierzHolsztyński The "only if" direction is obvious because of Fermat's little theorem and the fact that $1$ cannot have other square roots than $\pm 1$ inside $(\mathbb{Z}/N\mathbb{Z})^\times$ (this group is cyclic of order $N-1$ when $N$ is prime). | |
| Sep 21, 2015 at 21:46 | comment | added | Jeppe Stig Nielsen | You: That means, with small $p$ and large $n$, we could generate huge prime numbers We already have Proth's theorem which allows us to find huge prime of this form (even when the initial odd multiplier is not prime). This has been used for example to establish that numbers thought to be non-Sierpiński (because of lack of any obvious covering sets) were in fact so. Maybe someone can comment on the relationship between Proth's theorem and your conjecture above? | |
| Sep 14, 2015 at 19:31 | comment | added | Felipe Voloch | @Arul For Fermat numbers, OP's question is Pepin's test. | |
| Sep 14, 2015 at 10:50 | comment | added | user76479 | $p=2$ gives $N=2^k+1$. Has anyone tested primality for numbers of form $N=2^{2^k}+1$? It is conjectured there are only finitely many of these. May be this will be helpful to find a false prime | |
| Sep 12, 2015 at 15:26 | answer | added | Felipe Voloch | timeline score: 6 | |
| Sep 12, 2015 at 12:54 | comment | added | joro | Modulo errors there are no counterexamples for $p \le 10^7, n \le 10^2$. | |
| Sep 12, 2015 at 12:21 | comment | added | მამუკა ჯიბლაძე | Now checking with the precise criterion, currently reached $n$ up to $14$ with first $3000$ primes (the $3000$th prime is $27449$). However this seems to be not much of an evidence in view of the above example with $p=356387$. | |
| Sep 12, 2015 at 12:01 | comment | added | joro | How do you generate primes fast? The test works for Mersenne primes and you are working modulo large $N$? | |
| Sep 12, 2015 at 10:45 | comment | added | user76479 | Why downvote seems like Guest_2015 is chasing good leads here. | |
| Sep 12, 2015 at 10:44 | comment | added | მამუკა ჯიბლაძე | OMG will check with precise criterion then. How far did you check it? | |
| Sep 12, 2015 at 10:38 | comment | added | Guest_2015 | Criterion can not replaced by $3^{N-1}\equiv 1 ($mod $N)$ because there is a counter example. $N =356387⋅2^{11}+1=12289⋅59393$ while $3^{N−1}≡1($mod$N)$ | |
| Sep 12, 2015 at 10:30 | comment | added | მამუკა ჯიბლაძე | (Well to be precise, checked against $3^{N-1}\equiv1\mod N$) | |
| Sep 12, 2015 at 10:25 | comment | added | მამუკა ჯიბლაძე | Did a quick check, seems to hold for first 90 primes $p$ and $n\leqslant 20$ | |
| Sep 12, 2015 at 10:23 | answer | added | Guest_2015 | timeline score: 12 | |
| Sep 12, 2015 at 10:22 | comment | added | მამუკა ჯიბლაძე | Seems to be related to a question by Tony Reix | |
| Sep 12, 2015 at 10:00 | comment | added | Włodzimierz Holsztyński | Is one of the implications true? | |
| Sep 12, 2015 at 9:56 | review | Low quality posts | |||
| Sep 12, 2015 at 12:14 | |||||
| Sep 12, 2015 at 9:43 | comment | added | Igor Rivin | What led you to this claim? | |
| Sep 12, 2015 at 9:41 | review | First posts | |||
| Sep 12, 2015 at 9:55 | |||||
| Sep 12, 2015 at 9:26 | history | asked | Guest_2015 | CC BY-SA 3.0 |