The purpose of this paper is to prove that the value of the period  of a linear recurring sequence modulo p is intimately linked to the decomposition of its companion polynomial modulo p and to deduce fast algorithms providing a multiple of

We study in detail the cost of the calculation of  for binary and cubic recurrences.

For the cubic recurrences, we give also the matrix method and prove that the beginning of Berlekamp’s algorithm can also lead to the same result.

linear recurring sequences, period, modulo p, polynomials, Legendre symbols, companion polynomial, algorithm cost, Berlekamp’s algorithm, rank of a matrix, law of reciprocity quadratic.