Abstract

We consider the periodicity of recursive sequences defined by linear homogeneous recurrence relations of arbitrary order, when they are reduced modulo a positive integer m. We show that the period of such a sequence with characteristic polynomial f can be expressed in terms of the order of ω = x + ⟨f⟩ as a unit in the quotient ring Z_m[ω] = Z_m[x] ∕ ⟨f⟩. When m = p is prime, this order can be described in terms of the factorization of f in the polynomial ring Z_p[x]. We use this connection to develop efficient algorithms for determining the factorization types of monic polynomials of degree k ≤ 5 in Z_p[x].

Keywords

Mathematical Subject Classification 2000

Milestones

Authors