JP Journal of Algebra, Number Theory and Applications
Volume 26, Issue 2, Pages 159 - 172
(September 2012)
|
|
ON THE DETERMINATION OF PERIODS OF LINEAR RECURRENCES
Oumar Fall, Oumar Diankha, Maurice Mignotte and Mamadou Sangharé
|
Abstract: 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. |
Keywords and phrases: |
|
Number of Downloads: 417 | Number of Views: 1229 |
|