4
$\begingroup$

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.

In the table below, the second column shows the cycle length and the third column shows the tail length of the polynomial --- that is, tail length is defined as the number of elements before the cycle begins.

polynomial                   cycle length          tail length
x^[2] + 1 mod N                     33.31                 7.38
x^[3] + 1 mod N                    380.07                 3.40
x^[4] + 1 mod N                     13.43                 6.57
x^[5] + 1 mod N                   1242.46                 1.53
x^[6] + 1 mod N                     16.39                 5.85
x^[7] + 1 mod N                   1971.81                 1.07
x^[8] + 1 mod N                     11.47                 7.65
x^[9] + 1 mod N                    580.61                 2.58
x^[10] + 1 mod N                    11.13                 6.45
x^[11] + 1 mod N                  1593.10                 0.30
x^[12] + 1 mod N                    13.75                 4.32
x^[13] + 1 mod N                  1620.03                 0.19
x^[14] + 1 mod N                    26.46                 6.29
x^[15] + 1 mod N                   298.20                 2.68
x^[16] + 1 mod N                     9.67                 8.50
x^[17] + 1 mod N                  2643.80                 0.24
x^[18] + 1 mod N                    11.89                 6.03
x^[19] + 1 mod N                  1331.40                 0.06
x^[20] + 1 mod N                     9.25                 5.90
x^[21] + 1 mod N                   525.22                 2.65
x^[22] + 1 mod N                    12.49                 8.18
x^[23] + 1 mod N                  2005.32                 0.08
x^[24] + 1 mod N                    12.28                 4.77
x^[25] + 1 mod N                   913.86                 0.88
x^[26] + 1 mod N                    16.60                 7.54
x^[27] + 1 mod N                   488.15                 3.35
x^[28] + 1 mod N                    13.78                 7.16
x^[29] + 1 mod N                  2557.41                 0.01
x^[30] + 1 mod N                    11.59                 4.73
x^[31] + 1 mod N                  2919.89                 0.00
x^[32] + 1 mod N                    12.13                 7.20
x^[33] + 1 mod N                   660.20                 2.73
x^[34] + 1 mod N                    21.58                 8.06
x^[35] + 1 mod N                   981.59                 1.82
x^[36] + 1 mod N                     9.63                 6.00
x^[37] + 1 mod N                  1438.84                 0.05
x^[38] + 1 mod N                    12.43                 7.80
x^[39] + 1 mod N                   547.79                 2.70

We can also see in this table that if the power is prime, the cycle length is even larger than when it's merely an odd power.

To see this hierarchy of periods --- even powers smallest, odd powers, prime powers greatest ---, I computed the following three experiments. In all there experiments, the composite $N$ is all combinations of two primes in the set of all 50 smallest primes.

The first experiment computes the average period of polynomials $x^n + 1 \bmod N$ where $n$ is even in $\{2, ..., 12\}$.

>>> average_poly_class(primes()[0:50], [0,1,2,3], [2, 4, 6, 8, 10, 12])
{'poly': 'x^[2, 4, 6, 8, 10, 12] + 1 mod N',
 'avg_tail': 6.369387755102041,
 'avg_cycle': 16.580884353741496}

In the second experiment, $n$ is a non-prime odd power in $\{9,15,21,25,27,33\}$.

>>> average_poly_class(primes()[0:50], [0,1,2,3], [9,15,21,25,27,33])
{'poly': 'x^[9, 15, 21, 25, 27, 33] + 1 mod N',
 'avg_tail': 2.4783333333333335,
 'avg_cycle': 577.7066326530612}

In the third experiment, $n$ is a prime power in $\{3, 5, 7, 11, 13, 17\}$.

>>> average_poly_class(primes()[0:50], [0,1,2,3], [3, 5, 7, 11, 13, 17])
{'poly': 'x^[3, 5, 7, 11, 13, 17] + 1 mod N',
 'avg_tail': 1.1217006802721088,
 'avg_cycle': 1575.211768707483}

Can you explain this difference between even, odd, prime powers? Thank you.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – user44191
    Feb 24, 2019 at 0:10
  • $\begingroup$ 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. $\endgroup$
    – user44191
    Feb 24, 2019 at 0:12
  • $\begingroup$ 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. $\endgroup$
    – user136217
    Feb 24, 2019 at 1:28
  • 3
    $\begingroup$ 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. $\endgroup$ Feb 24, 2019 at 3:32
  • 1
    $\begingroup$ Changed $p(x)$ to $f(x)$. Thank you. $\endgroup$
    – user136217
    Feb 24, 2019 at 11:08

1 Answer 1

6
$\begingroup$

If $gcd(e,\lambda(N))=1,$ the sequence is purely periodic. Otherwise it may have an initial segment followed by a cycle, as you observe. Its maximal period divides the Carmichael function $\lambda(N)$ which is $\textrm{lcm}(p-1,q-1)$ when $N=pq,$ with $p,q$ prime.

Note that $2$ divides $\lambda(N)$ in this case, and explains the tendency in the period which you noticed. The paper Period of the power generator and small values of the Carmichael function by Friedlander, Pomerance and Shparlinski available here has a detailed discussion.

$\endgroup$
2
  • $\begingroup$ You must have meant $\gcd(e, \lambda(N)) = 1$ because that's what the paper says on page 1592, 5th paragraph. $\endgroup$
    – user136217
    Mar 3, 2019 at 0:30
  • 1
    $\begingroup$ Given this marvelous paper, the question I still have is whether what applies to polynomials $g(x) = x^e \bmod N$ also applies to $f(x) = x^e + 1 \bmod N$, where $\gcd(e, \lambda(N)) = 1$. The paper's results seems directed at $g(x)$ and not $f(x)$. $\endgroup$
    – user136217
    Mar 3, 2019 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.