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

**Download 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

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

- Desjardins, D. L., & Zieve, M. E. On the structure of polynomial mappings modulo an odd prime power, Arxiv.math/013046v1.
- Dickson, L. E. (1901) Linear Groups, with an exposition of the Galois field theory, Published by Leipzig B.G. tuebner.
- Dickson, L. E. (1896–97) Analytic representation of substitutions, Ann. of Math., v. 11, 65–120.
- Mullen, G. L., & Mummert, C. (2004) Finite Fields and Applications, AMS.
- Gouvˆea, F.Q. (1993) p-adic Numbers, Springer-Verlag Berlin Heidelberg.
- Gupta, I., Narain, L., & Madhavan, C. E. V. (2003) Cryptological Applications of Permutation Polynomials, Electron. Notes Discrete Math., 15, 91.
- 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.
- Laigle-Chapuy, Y. (2007) Permutation polynomials and applications to coding theory, Finite Fields Appl., 13(1), 58–70.
- Larin, M. V. (2002) Transitive polynomial transformations of residue rings, Discrete Math. Appl., 12(2), 127–10.
- Li, S. Permutation Polynomials modulo m, Arxiv.math/0509523v6.
- 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.
- 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.
- Lidl, R., & M¨uller, W. B. (1984) Permutation polynomials in RSA-Cryptosystems, In D. Chaum (Ed.), Advances in Cryptology, Springer US, 293–301.
- Mollin, R. A. (2011) Algebraic Number Theory, 2nd Ed., CRC Press.
- Rivest, R. L. (2001) Permutation Polynomials Modulo 2w, Finite Fields Appl., 7, 287–292.
- 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.

## Related papers

## Cite this paper

Javaheri, M., & Rusak, G. (2016). On transitive polynomials modulo integers. Notes on Number Theory and Discrete Mathematics, 22(2), 23-35.