Algorithm for constructing the system of representatives of maximal length cycles of polynomial substitution over the galois ring | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 7 (Приложение).

There are no polynomials with full cycle over the Galois ring. The maximal length of cycle of polynomial mapping over the Galois ring equals q(q - 1)p , where q - cardinality of ring and p - its characteristic. In this work, an algorithm is presented for constructing the system of representatives of all maximal length cycles of a polynomial substitution over the Galois ring. Let an elementary operation be the production in the Galois ring, then the complexity of the algorithm equals O(1q ) elementary operations as n tends to infinity, where I is the degree of the polynomial.