Return to Question

Polynomials $p(x) \bmod N$, where $p(x)$ is of integer coefficients and $N$ is a composite of two distinct primes $p, q$, form a cycle --- usually leaving a tail because the cycle tends to close not on the first element of the sequence. The cycle size is called the period of the polynomial.

Definition (cycle). A sequence generated by a polynomial $p(x) \bmod N$ has a cycle if there are indices $i, j$ with $i \neq j$ satisfying $$p(x_i) \bmod N = p(x_j) \bmod N.$$ Its cycle length is $j - i$. End of definition.

Trying out a few different polynomials in the form $x^n + 1 \bmod N$, I noticed even $n$ yields cycles with a smaller period than with odd $n$. I computed the average cycle length from the sample of all $C(50,2)$ composites $N$ formed by taking combinations of the smallest 50 primes.

Polynomials $f(x) \bmod N$, where $f(x)$ is of integer coefficients and $N$ is a composite of two distinct primes $p, q$, form a cycle --- usually leaving a tail because the cycle tends to close not on the first element of the sequence. The cycle size is called the period of the polynomial.

Definition (cycle). A sequence generated by a polynomial $f(x) \bmod N$ has a cycle if there are indices $i, j$ with $i \neq j$ satisfying $$f(x_i) \bmod N = f(x_j) \bmod N.$$ Its cycle length is $j - i$. End of definition.

Trying out a few different polynomials in the form $x^n + 1 \bmod N$, I noticed even $n$ yields cycles with a smaller period than with odd $n$. I computed the average cycle length from the sample of all $C(50,2)$ composites $N$ formed by taking combinations of the smallest $50$ primes.

Definition (cycle). A sequence generated by a polynomial $p(x) \bmod N$ has a cycle if there are indices $i, j$ with $i \neq j$ satisfying $$p(x_i) \bmod N = p(x_j) \bmod N.$$ Its cycle length is $j - i$. End of definition.