Timeline for Primality test for $N=2^mp^n +1$
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 5, 2020 at 18:31 | comment | added | Gerhard Paseman | Perhaps. For even better bounds, check out mathoverflow.net/q/221357 .Thanks for reminding me about Phi_{m-1}. Gerhard "Maybe Phi Is Good Enough" Paseman, 2020.08.05. | |
| Aug 5, 2020 at 18:25 | comment | added | Geoff Robinson | Note that the polynomial I use is $\Phi_{m-1}(x)$, not $\Phi_{m}(x)$. Note also that both these questions test with integer of the form $b = a^{\frac{m-1}{f}}$, where $f$ is basically the radical of $(m-1),$ and we basically need to check whether $b^{\frac{f}{p} } \equiv 1$ (mod $m$) for any prime divisor $p$ of $f$. I think this is close to what happens in the new edit. | |
| Aug 5, 2020 at 18:15 | comment | added | Gerhard Paseman | It is addressed to you Geoff. I think my point is now that the problems have to do with a given P(), while your theorem does not talk about P(), but about something that is computationally harder to obtain (what is Phi_m when you know that m is not prime but also do not know the factors of m) (sorry, I need to use m-1 in some places)? I like the later edit, but in my view it has relevance more to general theory than to the proposed series of problems. Gerhard "Wants Theorems Talking About P()" Paseman, 2020.08.05. | |
| Aug 5, 2020 at 18:15 | comment | added | Geoff Robinson | Nevertheless, in theory the method does give a test for primality of $m$, knowing only the prime factorization of $m-1$. While calculating the polynomial $\Phi_{m-1}(x)$ may be unwieldy, it does not know or care whether or not $m$ is prime. Also, we may note that $(h+1)^{\phi(m-1) } \geq \Phi_{m-1}(h) \geq (h-1)^{\phi(m-1)}.$ | |
| Aug 5, 2020 at 18:06 | comment | added | Geoff Robinson | If the question is addressed to me, I agree that this criterion seems likely to have no "practical" use. I partly wanted to point out that there is a whole family of examples of problems of this kind that could be posed of the same nature. These problems would not strictly be "duplicates" of each other, but are close to being duplicates. | |
| Aug 5, 2020 at 17:51 | comment | added | Gerhard Paseman | Although I am not challenging the mathematics, I wonder about the utility. If m is not prime (but we don't know that yet), we also want a guarantee that there is no h with P(h) a multiple of m, where P() is the polynomial we would use to test (and would equal Phi_m() if m were prime, but doesn't because m is not prime). Can you give us a theorem using P()? Gerhard "Wants To Cover His Bases" Paseman, 2020.08.05. | |
| Aug 5, 2020 at 11:09 | history | edited | Geoff Robinson | CC BY-SA 4.0 |
typos, minor text changes
|
| Aug 5, 2020 at 10:38 | history | edited | Geoff Robinson | CC BY-SA 4.0 |
Pointed out that solution to problem is a consequence of a more general fact.
|
| Aug 3, 2020 at 17:07 | history | edited | Geoff Robinson | CC BY-SA 4.0 |
Minor amendments
|
| Aug 3, 2020 at 11:02 | history | edited | Geoff Robinson | CC BY-SA 4.0 |
typo
|
| Aug 3, 2020 at 9:33 | history | edited | Geoff Robinson | CC BY-SA 4.0 |
Extra explanation
|
| Aug 3, 2020 at 3:09 | vote | accept | Pedja | ||
| Aug 2, 2020 at 19:55 | history | edited | Geoff Robinson | CC BY-SA 4.0 |
added clarification
|
| Aug 2, 2020 at 19:48 | history | answered | Geoff Robinson | CC BY-SA 4.0 |