Journal of Integer Sequences, Vol. 4 (2001), Article 01.1.1 |

Department of Computer Science

National University of Ireland

Maynooth, Co. Kildare, Ireland

Email address: fred@cs.may.ie

**Abstract:**
This paper might fairly be said to fall between three stools:
the presentation and justification of a number of related computational methods
associated with LFSR sequences, including finding the order, recurrence and
general term; the exploration of tutorial examples and survey of applications;
and a rigorous treatment of one topic, the recursive construction of the
number wall, which we believe has not previously appeared.

The *Number Wall* is the table of Toeplitz determinants associated with a
sequence over an arbitrary integral domain, particularly
**Z**,
**F _{p}**,

Much of the paper collects and summarizes relevant classical theory in
Formal Power Series (Section 1), Linear Recurrences (Section 2), Padé Blocks (essentially)
(Section 3),
Vandermonde Interpolation (Section 8), and Difference Tables (Section 9).
A `frame' relation between the elements of the number wall containing zeros
(a *non-normal C-table*, in Padé terminology) is stated and proved (Section 4),
with the resulting recursive generation algorithm and some special cases (Section 5);
the consequences of basing the wall on this algorithm instead are explored (Section 6),
and a cellular automaton is employed to optimize it in linear time (Section 7).

The connections between number walls and classical Padé tables are
discussed briefly (Section 11), with other associated areas (Linear Complexity,
QD Algorithm, Toda Flows, Berlekamp-Massey) reviewed even more briefly
(Section 12). Among topics covered incidentally are the explicit number wall
for an LFSR, in particular for a diagonal binomial coefficient (Section 8);
dealing with high-degree `polynomials' over finite fields, fast computation
of LFSR order over **F _{p}**, and the wall of a linear function of a given
sequence (Section 9). There are numerous examples throughout, culminating in a final
gruelingly extensive one (Section 13).

**Keywords:** Number Wall, Zero Window, Persymmetric, Toeplitz Matrix,
Hankel Determinant, Linear Complexity, Finite Field, Cryptographic Security,
LFSR, Extrapolation, Toda Flow, Linear Recurring Sequence, Difference Equation,
Zero-Square Table, QD Method, Vandermonde, Formal Laurent Series, Padé Table.

**AMS Subject Classification:** 94A55, 65D05, 11C20, 65-04, 68Q15, 68Q68, 41A21.

Received January 1, 2001; revised version received September 25, 2001. Published in Journal of Integer Sequences, October 7, 2001.

Return to
**Journal of Integer Sequences home page**