Linear Recurring Sequences Over Finite Fields

Author: McEliece, Robert James

Year: 1967

Degree: Dissertation (Ph.D.)

Advisor: Hall, Marshall

Committee Member: Unknown, Unknown

Option: Mathematics

DOI: 10.7907/1KMK-T118

Abstract

This thesis deals with the problem of how the elements from a finite field F of characteristic p are distributed among the various linear recurrent sequences with a given fixed characteristic polynomial fε F[x]. The first main result is a method of extending the so-called "classical method" for solving linear recurrences in terms of the roots of f. The main difficulty is that f might have a root θ which occurs with multiplicity exceeding p-1; this is overcome by replacing the solutions θt, tθt, t2θt, ..., by the solutions θt, (t1)θt, (t2)θt, .... The other main result deals with the number N of times a given element a ε F appears in a period of the sequence, and for a≠0, the result is of the form N≡0 (mod pε where ε is an integer which depends upon f, but not upon the particular sequence in question. Several applications of the main results are given.

Files