TAOCP 3.3.4 Exercise 24
Let X_n \equiv aX_{n-1}+bX_{n-2}\pmod p, where $p$ is prime, and suppose that the recurrence has period $p^2-1$.
Section 3.3.4: The Spectral Test
Exercise 24. ▶ [M28] Generalize the spectral test to second-order sequences of the form $X_n = (aX_{n-1} + bX_{n-2}) \bmod p$, having period length $p^2 - 1$. (See Eq. 3.2.2–(8).) How should Algorithm S be modified?
Verified: yes
Solve time: 5m34s
Exercise 3.3.4.24
Let
$$ X_n \equiv aX_{n-1}+bX_{n-2}\pmod p, $$
where $p$ is prime, and suppose that the recurrence has period $p^2-1$. By the theory of linear recurrences over $\mathbf F_p$, this means that the state vectors
$$ (X_{n-1},X_n)\in \mathbf F_p^2 $$
run through all nonzero pairs exactly once.
We seek the analogue of the spectral test for the points
$$ \left(\frac{X_n}{p},\frac{X_{n+1}}{p},\ldots,\frac{X_{n+t-1}}{p}\right). $$
For ordinary linear congruential generators, the spectral test is based on the shortest nonzero integer vector satisfying one modular relation. Here the recurrence has order $2$, hence two independent modular relations arise.
1. Representation of the sequence
Define sequences $A_n,B_n$ by
$$ A_0=1,\quad A_1=0, $$
$$ B_0=0,\quad B_1=1, $$
and for $n\ge2$,
$$ A_n\equiv aA_{n-1}+bA_{n-2}\pmod p, $$
$$ B_n\equiv aB_{n-1}+bB_{n-2}\pmod p. $$
Then every term of the recurrence has the form
$$ X_n\equiv A_nX_0+B_nX_1\pmod p. $$
Now let $u_1,\ldots,u_t\in\mathbf Z$. Consider
$$ S_n=u_1X_n+u_2X_{n+1}+\cdots+u_tX_{n+t-1}. $$
Substituting the representation above gives
$$ S_n \equiv \left(\sum_{j=1}^t u_jA_{n+j-1}\right)X_0 + \left(\sum_{j=1}^t u_jB_{n+j-1}\right)X_1 \pmod p. $$
Since the period is $p^2-1$, the pairs $(X_0,X_1)$ run through all nonzero vectors of $\mathbf F_p^2$. Therefore
$$ S_n\equiv0\pmod p \quad\text{for all states} $$
if and only if both coefficients vanish:
$$ \sum_{j=1}^t u_jA_{n+j-1}\equiv0\pmod p, $$
$$ \sum_{j=1}^t u_jB_{n+j-1}\equiv0\pmod p. $$
Because $A_n$ and $B_n$ satisfy the same recurrence as $X_n$, it suffices to take $n=0$. Hence the admissible vectors $u=(u_1,\ldots,u_t)$ are those satisfying
$$ \sum_{j=1}^t u_jA_{j-1}\equiv0\pmod p, \tag{1} $$
$$ \sum_{j=1}^t u_jB_{j-1}\equiv0\pmod p. \tag{2} $$
These are the analogues of the single congruence
$$ u_1+au_2+\cdots+a^{t-1}u_t\equiv0\pmod m $$
for ordinary linear congruential generators.
The set of all integer vectors satisfying (1) and (2) forms a lattice in $\mathbf Z^t$.
2. Spectral quantity
The spectral test is determined by the shortest nonzero vector in this lattice.
Thus $\nu_t$ is defined by
$$ \nu_t = \min \left{ \sqrt{u_1^2+\cdots+u_t^2} : (u_1,\ldots,u_t)\ne0, \ \text{((1)) and ((2)) hold} \right}. $$
Geometrically, the points
$$ \left(\frac{X_n}{p},\ldots,\frac{X_{n+t-1}}{p}\right) $$
lie on families of parallel hyperplanes whose normals are precisely the admissible vectors $u$. The quantity $\nu_t$ measures the spacing structure exactly as in the ordinary spectral test.
3. Matrix form
Introduce the companion matrix
$$ M= \begin{pmatrix} 0&1\ b&a \end{pmatrix}. $$
Then
$$ \binom{X_n}{X_{n+1}} = M^n \binom{X_0}{X_1}. $$
If
$$ M^n= \begin{pmatrix} A_n&B_n\ A_{n+1}&B_{n+1} \end{pmatrix}, $$
conditions (1) and (2) become
$$ \sum_{j=1}^t u_jM^{j-1} \equiv0 \pmod p, $$
interpreted componentwise in $\mathbf F_p^{2\times2}$. Equivalently, the first row must vanish modulo $p$, giving exactly the two scalar congruences above.
4. Modification of Algorithm S
Algorithm S for ordinary linear congruential generators maintains one modular recurrence relation. In the present problem, it must maintain two simultaneously.
For the ordinary case, the coefficients
$$ 1,a,a^2,\ldots $$
appear in the congruence condition. Here they are replaced by the pairs
$$ (A_n,B_n), $$
generated by the second-order recurrence.
Thus the algorithm is modified as follows.
- Compute the sequences $A_n,B_n$ recursively:
$$ A_n\equiv aA_{n-1}+bA_{n-2}\pmod p, $$
$$ B_n\equiv aB_{n-1}+bB_{n-2}\pmod p. $$
- Replace the single congruence test by the simultaneous conditions
$$ \sum_{j=1}^t u_jA_{j-1}\equiv0\pmod p, $$
$$ \sum_{j=1}^t u_jB_{j-1}\equiv0\pmod p. $$
- During the recursive search over integer vectors $u$, carry along two accumulated residues instead of one.
For example, if the first $k$ coefficients have been chosen, maintain
$$ R_k^{(A)} = \sum_{j=1}^k u_jA_{j-1}\pmod p, $$
$$ R_k^{(B)} = \sum_{j=1}^k u_jB_{j-1}\pmod p. $$
Each extension step updates both residues recursively.
- A vector $u$ is admissible only when both final residues vanish modulo $p$. Among all nonzero admissible vectors, Algorithm S selects one minimizing
$$ u_1^2+\cdots+u_t^2. $$
Hence the only essential change is that the scalar modular relation in Algorithm S becomes a two-component modular relation generated by the companion recurrence.