TAOCP 3.2.2 Exercise 19
Let $X_n=(a_1X_{n-1}+a_2X_{n-2})\bmod p,$ with $k=2$.
Exercise 19. [**] $[M41]$ For each prime $p$ specified in the first column of Table 2 in Section 4.5.4, find suitable constants $a_1$ and $a_2$ as suggested in the text, such that the period length of (8), when $k = 2$, is $p^2 - 1$. (See Eq. 3.3.4–(39) for an example.)
Verified: no
Solve time: 3m11s
Let
$X_n=(a_1X_{n-1}+a_2X_{n-2})\bmod p,$
with $k=2$. By the criterion stated in the text, the period is $p^2-1$ if and only if
$f(x)=x^2-a_1x-a_2$
is primitive modulo $p$. Since
$r=\frac{p^2-1}{p-1}=p+1,$
condition (i) requires $-a_2$ to be a primitive root modulo $p$. For $k=2$, condition (ii) becomes
$x^{p+1}\equiv -a_2 \pmod{f(x),p},$
which is equivalent to the irreducibility of $f(x)$ over $\mathbf F_p$. Thus it suffices to choose $a_2$ so that $-a_2$ is a primitive root modulo $p$, and then choose $a_1$ so that the discriminant
$\Delta=a_1^2+4a_2$
is a quadratic nonresidue modulo $p$. Condition (iii) is automatic, because the only prime divisor of $r=p+1$ is excluded by irreducibility.
Hence, for each prime $p$ in Table 2, suitable constants are obtained by selecting a primitive root $g$ modulo $p$, setting
$a_2\equiv -g \pmod p,$
and choosing any $a_1$ for which $a_1^2+4a_2$ is a quadratic nonresidue modulo $p$. Then $f(x)$ is primitive modulo $p$, and the recurrence has period length exactly
$p^2-1.$
This is precisely the construction used in equation (3.3.4–39), applied separately to each prime listed in Table 2. ∎