Article Contents

2017, Volume 11, Issue 2: 397-407. Doi: 10.3934/amc.2017034

This issue Previous Article Some new results on the conjecture on exceptional APN functions and absolutely irreducible polynomials: The gold case Next Article

Cycle structure of iterating Redei functions

1.
Institute of Mathematics, State University of Campinas, Brazil
2.
School of Mathematics and Statistics, Carleton University, Canada
3.
Academic Department of Mathematics, UTFPR, Brazil

Received: February 2016

Revised: March 2016

Published: September 2017

C. Qureshi is supported by FAPESP 2012/10600-2 and CNPq 158670/2015-9; D. Panario is supported by NSERC

Abstract / Introduction Full Text(HTML) Figure(1) Related Papers Cited by

Abstract

Vasiga and Shallit [17] study tails and cycles in orbits of iterations of quadratic polynomials over prime fields. These results were extended to repeated exponentiation by Chou and Shparlinski [3]. We show, using the quadratic reciprocity law, that it is possible to extend these results to Rédei functions over prime fields.

Keywords:

Mathematics Subject Classification: Primary: 11T71; Secondary: 94A62.

Citation:

Full Text(HTML)

Figure 1. This figure (taken from [14]) illustrates the inductive definition of $T_V$ when $V$ is a $\nu$-series with four components $V=(\nu_1,\nu_2,\nu_3,\nu_4)$. A node $v$ labelled by a rooted tree $T$ indicates that $v$ is the root of a tree isomorphic to $T$

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

	L. Blum , M. Blum and M. Shub , A simple unpredictable pseudo-random number generator, SIAM J. Comput., 15 (1986) , 364-383. doi: 10.1137/0215025.
	R. Brent and J. Pollard , Factorization of the eighth Fermat number, Math. Comput., 36 (1981) , 627-630. doi: 10.2307/2007666.
	W. Chou and I. E. Shparlinski , On the cycle structure of repeated exponentiation modulo a prime, J. Number Theory, 107 (2004) , 345-356. doi: 10.1016/j.jnt.2004.04.005.
	D. A. Cox, Primes of the Form $x^2+ny^2$: Fermat, Class Field Theory and Complex Multiplication, Wiley-Interscience, 1989.
	FIPS PUB 186-4, Digital Signature Standard (DSS), Federal Information Processing Standards Publication, NIST, 2013.
	R. Lidl and W. B. Müller , Generalization of the Fibonacci pseudoprime test, Discrete Math., 92 (1991) , 211-220. doi: 10.1016/0012-365X(91)90282-7.
	W. Meidl and A. Winterhof , On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions, Finite Fields Appl., 13 (2007) , 628-634. doi: 10.1016/j.ffa.2005.10.001.
	NIST Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, NIST, 2007.
	R. Nobauer , Cryptoanalysis of the Rédei scheme, Contrib. General Algebra, 3 (1984) , 255-264.
	R. Nobauer , Key distribution systems based on polynomial functions and Rédei functions, Probl. Contr. Inf. Theory, 15 (1986) , 91-100.
	R. Pieper , Cryptanalysis of Rédei-and Dickson permutations on arbitrary finite rings, AAECC, 4 (1993) , 59-76. doi: 10.1007/BF01270400.
	J. M. Pollard , A monte carlo method for factorization, BIT, 15 (1975) , 331-334.
	J. M. Pollard , Monte carlo methods for index computation (mod $p$), Math. Comp., 32 (1978) , 918-924. doi: 10.2307/2006496.
	C. Qureshi and D. Panario , Rédei actions on finite fields and multiplication map in cyclic groups, SIAM J. Discrete Math., 29 (2015) , 1486-1503. doi: 10.1137/140993338.
	A. Sakzad , M. Sadeghi and D. Panario , Cycle structure of permutation functions over finite fields and their applications, Adv. Math. Commun., 6 (2012) , 347-361. doi: 10.3934/amc.2012.6.347.
	M. Sha , Digraphs from endomorphisms of finite cyclic groups, J. Combin. Math. Combin. Comp., 83 (2012) , 105-120.
	T. Vasiga and J. Shallit , On the iteration of certain quadratic maps over $GF(p)$, Discrete Math., 277 (2004) , 219-240. doi: 10.1016/S0012-365X(03)00158-4.
	M. Wiener and R. Zuccherato, Faster attacks on elliptic curve cryptosystems, in Selected Areas in Cryptography, 1998,190-200. doi: 10.1007/3-540-48892-8_15.