On transitive polynomials modulo integers

Mohammad Javaheri and Gili Rusak
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 22, 2016, Number 2, Pages 23–35
Full paper (PDF, 223 Kb)

Details

Authors and affiliations

Mohammad Javaheri
School of Science, Siena College
515 Loudon Road, Loudonville, NY 12110, USA

Gili Rusak
School of Engineering, Stanford University
353 Serra Mall, Stanford, CA 94305, USA

Abstract

A polynomial P(x) with integer coefficients is said to be transitive modulo m, if for every x, y ∈ ℤ there exists k ≥ 0 such that P^k(x) = y (mod m). In this paper, we construct new examples of transitive polynomials modulo prime powers and partially describe cubic and quartic transitive polynomials. We also study the orbit structure of affine maps modulo prime powers.

Keywords

• Transitive polynomials
• Permutation polynomials

AMS Classification

• 11T06

References

 

1. Desjardins, D. L., & Zieve, M. E. On the structure of polynomial mappings modulo an odd prime power, Arxiv.math/013046v1.
2. Dickson, L. E. (1901) Linear Groups, with an exposition of the Galois field theory, Published by Leipzig B.G. tuebner.
3. Dickson, L. E. (1896–97) Analytic representation of substitutions, Ann. of Math., v. 11, 65–120.
4. Mullen, G. L., & Mummert, C. (2004) Finite Fields and Applications, AMS.
5. Gouvˆea, F.Q. (1993) p-adic Numbers, Springer-Verlag Berlin Heidelberg.
6. Gupta, I., Narain, L., & Madhavan, C. E. V. (2003) Cryptological Applications of Permutation Polynomials, Electron. Notes Discrete Math., 15, 91.
7. Kedlaya, K., & Ng, L. (2015) Solutions to the 73rd William Lowell Putnam Mathematical Competition, http://kskedlaya.org/putnam-archive/2012s.pdf, Last visited: August 14, 2015.
8. Laigle-Chapuy, Y. (2007) Permutation polynomials and applications to coding theory, Finite Fields Appl., 13(1), 58–70.
9. Larin, M. V. (2002) Transitive polynomial transformations of residue rings, Discrete Math. Appl., 12(2), 127–10.
10. Li, S. Permutation Polynomials modulo m, Arxiv.math/0509523v6.
11. Lidl, R., & Mullen, G. L. (1988) When does a polynomial over a finite field permute the elements of the field? Amer. Math. Monthly, 95(3), 243–246.
12. Lidl, R., & Mullen, G. L. (1993) When does a polynomial over a finite field permute the elements of the field? II, Amer. Math. Monthly, 100(1), 71–74.
13. Lidl, R., & M¨uller, W. B. (1984) Permutation polynomials in RSA-Cryptosystems, In D. Chaum (Ed.), Advances in Cryptology, Springer US, 293–301.
14. Mollin, R. A. (2011) Algebraic Number Theory, 2nd Ed., CRC Press.
15. Rivest, R. L. (2001) Permutation Polynomials Modulo 2w, Finite Fields Appl., 7, 287–292.
16. Rivest, R. L., Robshaw, M. J. B., Sidney, R., & Yin, Y. L. The RC6 block cipher, http: //people.csail.mit.edu/rivest/Rc6.pdf, Last visited: June 2016.