Let $P$ be a given polynomial of degree $n$ with coefficients in a finite field.
Let $S_0$ be a given polynomial of degree less than $n$ with coefficients in that field.
How do we derive the (smallest) period of $i\mapsto S_i=S_0\,x^i\bmod P$ ?
My initial motivation/exploration was with the Boolean field, where $S_i$ is the state of a Galois LFSR with polynomial $P$ and initial state $S_0$, in a cryptographic context. I see that
- if $S_0=0$, period is 1
- if $P$ is irreducible and $S_0\ne0$ then
- $S_0$ is coprime with $P$;
- thus the period is the smallest $i$ with $x^i-1$ a multiple of $P$;
- restricting to the Boolean case in the next bullet points, the period divides $2^n-1$, and is exactly that for primitive $P$;
- we can experimentally find the period by factoring $2^n-1$ and pulling out those factors $u_j$ leaving $x^{(2^n-1)/(\prod u_j)}-1$ a multiple of $P$, with that condition testable with $O(n^3)$ time and $O(n)$ memory; but I wonder if there's a more direct method.
- otherwise
- we can factor $P$ into $\prod P_i$ with $P_i$ primitive of order $n_i$;
- the period divides $\prod(2^{n_i}-1)$, but I'm moving out of my comfort zone.
My math background is engineering+self-taught, and I'm struggling in particular about
- how $\gcd(P,S_0)$ can be used to predict how the period varies with $S_0$;
- what's the effect of squares in the factorization of $P$;
- how we can obtain the factorization of $P$ better than by trial division with irreducible polynomials (or delegating to Wolfram's Alpha);
- how things generalize for a finite field other than Booleans.