Timeline for Why do polynomials $x^n + 1 \bmod N$ close a shorter cycle when $n$ is even than when $n$ is odd?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2019 at 0:23 | vote | accept | user136217 | ||
| Mar 2, 2019 at 12:58 | vote | accept | user136217 | ||
| Mar 3, 2019 at 0:23 | |||||
| Feb 24, 2019 at 22:04 | answer | added | kodlu | timeline score: 6 | |
| Feb 24, 2019 at 11:08 | comment | added | user136217 | Changed $p(x)$ to $f(x)$. Thank you. | |
| Feb 24, 2019 at 11:06 | history | edited | user136217 | CC BY-SA 4.0 |
edited body
|
| Feb 24, 2019 at 3:32 | comment | added | Gerry Myerson | Please edit into the body of your question this explanation that your sequence comes from iterating the polynomial. Also, please don't use $p$ for both a polynomial and a prime number in the same paragraph. | |
| Feb 24, 2019 at 1:34 | history | edited | user136217 | CC BY-SA 4.0 |
added 236 characters in body
|
| Feb 24, 2019 at 1:28 | comment | added | user136217 | Yes, $p(x)$ is a function $f: \mathbb{Z}/n \to \mathbb{Z}/n$, but we get a cycle when $i \neq j$ satisfies $p(x_i) = p(x_j)$. From that point on, the sequence repeats its cycle forever. | |
| Feb 24, 2019 at 0:12 | comment | added | user44191 | On another note: when you say a "cycle", do you mean considering $p(x)$ as a function $f: \mathbb{Z}/n \rightarrow \mathbb{Z}/n$, and looking at the number $i$ such that there is a $j,$with $f^{(j)} = f^{(j + i)}$, the composition power of the function? It may be useful to clarify the question. | |
| Feb 24, 2019 at 0:10 | comment | added | user44191 | One possibility: when $n$ is divisible by $2$, all of the outputs are of the form $y^2 + 1$. For all odd primes $p$, this halves the number of outputs; for $N$ composite, it halves the number of outputs for each odd prime factor. | |
| Feb 23, 2019 at 22:57 | history | edited | YCor |
edited tags
|
|
| Feb 23, 2019 at 22:35 | review | First posts | |||
| Feb 24, 2019 at 0:14 | |||||
| Feb 23, 2019 at 22:31 | history | asked | user136217 | CC BY-SA 4.0 |