Определение: Уравнение L(x(k)) = x(k+n) + a₁(k)x(k+n+1) + … + a_n(k)x(k) = {0, F(k)}, причём
0 – (R₀) однородное уравнение.
F(k) – R₁ неоднородное уравнение.
где a_i(k) – функция в N→R, i = 1…n и F(k)≠0 (тривиально) – неизвестная функция, x(k) – неизвестная функция называются линейными рекуррентными уравнениями (ЛРУ) однородными и неоднородными соответственно с постоянными коэффициентами.

Замечание: Такие уравнения R₀ и R₁ называют стационарными ЛРУ или СЛРУ однородными и неоднородными соответственно.

Определение: Выражение L(y) = λⁿ + a₁λ^n-1 + … + a_n-1λ + a_n есть характеристический компонент для однородного СЛРУ R₀ (Равно как и для неоднородного СЛРУ R₁).

Теорема: Если:
λ₁, … , λ_p – вещественные кокни характеристического уравнения
l₁, … , l_p – их кратности
μ₁, … , μ_s – группа комплексных корней
μ_j = α_j+β_j, j=1, … ,s
μ₁*, … , μ_s* — группа комплексно сопряженных корней.

μ_j = α_j — iβ_j, j = 1, …, s

r₁, …, r_s – их кратность
p_jφ_j — модуль и аргумент для комплексного числа μ_j, то функции:
x_j(k) = k^m_j(λ_j)^k , j=1,…,p; m_j=0,…,l_j-1
y_j = k^m_j(ρ_j)^kcos(φ_jk), j=1,…,s_j; m_j=0,…,r_j-1
z_j = k^m_j(ρ_j)^ksin(φ_jk), j=1,…,s_j; m_j=0,…,r_j-1
составляют решение для однородной СЛРУ(r₀).

Замечание:. Если x₁(k),…, x_n(k) есть ФСР для однородного СРЛУ (r0), то его общее решение x_oo(k)=C₁x₁(k)+…+ C_nx_n(k), где произвольные постоянные пробегают множество вещественных чисел R – независимо друг от друга.

Если x_чн есть какое либо частное неоднородное решение СЛРУ(r₁), то если x_он=x_чн+ x_oo(k)=C₁x₁(k)+…+ C_nx_n(k)

Нахождение частного решения часто бывает непростой задачей, но для некоторых специальных правых частей R₁, такое решение может быть найдено, например, если правая часть R₁ есть квазиполином.
f(k)=P_m(k), то функция x_чн может быть найдена в виде x_чн=k^rQ_m(k)λ^k,где r есть кратность корня характеристического уравнения, а Q_m(k) – есть полином степени m, неизвестные коэффициенты которого: a₀,a₁,…,a_m – подлежат определению.

Замечание: СЛРУ, определена на элементах групп, широко используемых в криптографии.

Комментарии запрещены.