Algorithm for constructing the system of representatives of maximal length cycles of polynomial substitution over the galois ring
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 <sup>n-2</sup>, where q <sup>n</sup> - cardinality of ring and p <sup>n</sup> - 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 <sup>n-1</sup>) elementary operations as n tends to infinity, where I is the degree of the polynomial.