Пусть F – конечное поле, |F| = q и n – натуральное число. Линейной рекуррентной последовательностью (кратко: л.р.п.) n-го порядка над полем F называется всякая последовательность s = s₀s₁… элементов поля F, являющаяся решением следующей системы рекуррентных уравнений:

, i = 0, 1, …,

(1)

где h₀, h₁, …, h_n – некоторые фиксированные  элементы поля F, h₀ ≠ 0 и h_n = 1. Многочлен h(x) = h₀ + h₁x + … + h_n-1x^n-1 + xⁿF[x] называется характеристическим многочленом данной л.р.п. Система уравнений (1), записанная в виде:

si+n = − , i = 0, 1, …,

(2)

указывает правило, по которому при любых заданных в F значениях s₀, s₁, …, s_n–1, представляющих собой начальное условие системы, вычисляется в s сначала значение s_n, затем по известным s₁, …, s_n – значение s_n+1 и т.д., по s_is_i+1…s_i+n–1 – значение s_i+n.

Разным начальным условиям рассматриваемой системы уравнений отвечают разные ее решения, поэтому количество всех решений системы равно qⁿ. При s₀s₁…s_n–1 = 00…0 все символы в s равны 0, и такая л.р.п. называется нулевой. Поскольку уравнения в системе линейны, то любая линейная комбинация их решений будет снова решением, а все решения образуют векторное пространство над F. Его базис состоит из решений, отвечающих единичным векторам начальных условий 10…0, 01…0, …, 00…1. Таким образом, множество всех л.р.п. n-го порядка с одним и тем же характеристическим многочленом является векторным пространством размерности n над полем F.

Последовательность s = s₀s₁s₂… называется периодической, если существует натуральное m такое, что s_i = s_i+m для всех i ≥ 0. Наименьшее m с этим свойством называется периодом последовательности s.