The first important case occurs when m is a prime number, and f is the almost linear recurrence
Here the coefficients (c1, . . ., cn) must be such that
is a primitive polynomial modulo m, in the sense discussed following Eq. 3.2.2–(9). The number of such polynomials is φ(mn – 1)/n, large enough to allow us to find one in which only a few of the c’s are nonzero. [This construction goes back to a pioneering paper of Willem Mantel, Nieuw Archief voor Wiskunde (2) 1 (1897), 172–184.]
For example, suppose m = 2. We can generate binary n-tuples with ...