Inversive congruential generators modulo 217, with all 216 odd-valued points plotted. The first two are given by x−1+2 and the other two by x−1+45678, where the first/third plots have lag 1 and the second/fourth plots have lag 2. (Edit: actually, I just noticed I forgot to comment out
x ^= x>>>1, which provides a little bit of mixing, so these plots are not exactly of the ICG, but of the ICG conjugated with this xor-shift.)
ICGs have, in some sense, an optimal lack of lattice structure when the modulus is prime, but obviously that doesn’t carry over to prime power moduli. This statement apparently applies to both recursive ICGs (defined by a transition function ) and to explicit ICGs (defined by ).
We can prove that, for a recursive ICG modulo with the transition function , it attains the maximum period of if and only if and . The “only if” part is trivial. The rest will be proven by induction (boilerplate: “suppose this holds for some m blah blah blah”).
Lemma: 1 has exactly four square roots modulo 2m+1, namely, ±1 and 2m±1.
Proof: That the four given values are square roots is easily verified. Let be some square root of 1 not congruent to ±1, and let such that is an odd integer and .
Since reciprocation gives a perfect matching among the odd non-unity-square-roots, considering the odd numbers between and (inclusive), an even quantity of these must map within the same set (i.e. they don’t toggle the high bit), and so the remaining numbers (which toggle the high bit) must be even in quantity as well. By the bijectivity of reciprocation, we similarly have that an even number of odd numbers with the high bit set toggle the high bit under reciprocation.
Using the same trick as before of summing the overflow over the period of bits, we note that the overflow from reciprocation cancels itself out, as does overflow from the high bit of and overflow from multiplying by , which leaves overflow from adding , but we already know that that’s , or equivalently, , which is exactly the same as saying that the high bit is toggled every iterations, thereby showing that the maximum period of is attained with the given conditions.
With “small” values of , the ICG seems to have bad structure, which might be explainable with the help of Laurent series. For instance, we have , which is actually a finite series because 2 is nilpotent. Or maybe it makes more sense to defer to the fact that the transition function is a fractional linear transformation and do something about that.