×

zbMATH — the first resource for mathematics

The Carlitz rank of permutations of finite fields: a survey. (English) Zbl 1332.11106
Summary: L. Carlitz [Proc. Am. Math. Soc. 4, 538 (1953; Zbl 0052.03704)] proved that any permutation polynomial \(f\) of a finite field \(\mathbb F_q\) is a composition of linear polynomials and the monomials \(x^{q-2}\). This result motivated the study of Carlitz rank of \(f\), which is defined in 2009 to be the minimum number of inversions \(x^{q-2}\), needed to obtain \(f\), byE. Aksoy et al. [Finite Fields Appl. 15, No. 4, 428–440 (2009; Zbl 1232.11124)] We give a survey of results obtained so far on natural questions related to this concept and indicate a variety of applications, which emerged recently.

MSC:
11T06 Polynomials over finite fields
65C10 Random number generation in numerical analysis
Software:
OEIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmad, S., Cycle structure of automorphisms of finite cyclic groups, J. Comb. Theory, 6, 370-374, (1969) · Zbl 0169.34101
[2] Aksoy, E.; Çeşmelioğlu, A.; Meidl, W.; Topuzoğlu, A., On the Carlitz rank of permutation polynomials, Finite Fields Appl., 15, 428-440, (2009) · Zbl 1232.11124
[3] Avenancio-Leon, C., Analysis of some properties of interleavers for turbo codes, (Proc. of NCUR, Lexington, USA, (2005))
[4] Beth, T.; Ding, C., On almost perfect nonlinear permutations, (Eurocrypt ’93, Lect. Notes Comput. Sci., vol. 765, (1993), Springer-Verlag New York), 65-76 · Zbl 0951.94524
[5] Blackburn, S. R.; Gomez-Perez, D.; Gutierrez, J.; Shparlinski, I. E., Predicting the inversive generator, (Paterson, K. G., Lect. Notes Comput. Sci., vol. 2898, (2003), Springer-Verlag Berlin), 264-275 · Zbl 1123.94330
[6] Blackburn, S. R.; Gomez-Perez, D.; Gutierrez, J.; Shparlinski, I. E., Predicting nonlinear pseudorandom number generators, Math. Comput., 74, 1471-1494, (2005) · Zbl 1136.11316
[7] Bracken, C.; Leander, G., A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree, Finite Fields Appl., 16, 231-242, (2010) · Zbl 1194.94182
[8] Carlitz, L., Permutations in a finite field, Proc. Am. Math. Soc., 4, 538, (1953) · Zbl 0052.03704
[9] Çeşmelioğlu, A., On the cycle structure of permutation polynomials, (2008), Sabanci University, PhD thesis · Zbl 1153.11057
[10] Çeşmelioğlu, A., 2012. On permutations with full cycle. Preprint.
[11] Çeşmelioğlu, A.; Meidl, W.; Topuzoğlu, A., On the cycle structure of permutation polynomials, Finite Fields Appl., 14, 593-614, (2008) · Zbl 1153.11057
[12] Çeşmelioğlu, A.; Meidl, W.; Topuzoğlu, A., Enumeration of a class of sequences generated by inversions, (Li, Y.; Zhang, S.; Ling, S.; Wang, H.; Xing, C.; Niederreiter, H., Proceedings of the First Int. Workshop on Coding and Cryptology, Fujian, China, June 2007, Ser. Coding Theory Cryptol., vol. 4, (2008), World Scientific Publishing Co. Singapore)
[13] Çeşmelioğlu, A.; Meidl, W.; Topuzoğlu, A., Permutations with prescribed properties, J. Comput. Appl. Math, (2013)
[14] Chaix, H.; Faure, H., Discrepance et diaphonie en dimension un, Acta Arith., 63, 103-141, (1993) · Zbl 0772.11022
[15] Chou, W.-S., The period lengths of inversive pseudorandom vector generations, Finite Fields Appl., 1, 126-132, (1995) · Zbl 0822.11054
[16] Chou, W.-S.; Shparlinski, I. E., On the cycle structure of repeated exponentiation modulo a prime, J. Number Theory, 107, 2, 345-356, (2004) · Zbl 1060.11059
[17] Comtet, L., Advanced combinatorics: the art of finite and infinite expansions, (1974), Reidel Dordrecht
[18] Corrada-Bravo, C. J.; Rubio, I. M., Deterministic interleavers for turbo codes with random-like performance and simple implementation, (Proc. of the 3rd International Symposium on Turbo Codes and Related Topics, Brest, France, (2003)), 555-558
[19] Das, P., The number of permutation polynomials of a given degree over a finite field, Finite Fields Appl., 8, 478-490, (2002) · Zbl 1029.11066
[20] Drmota, M.; Tichy, R., Sequences, discrepancies and applications, (1997), Springer-Verlag Berlin · Zbl 0877.11043
[21] Faure, H., Discrepance de suites associees a un systeme de numeration (en dimension un), Bull. Soc. Math. Fr., 109, 143-182, (1981) · Zbl 0488.10052
[22] Faure, H., Good permutations for extreme discrepancy, J. Number Theory, 42, 47-56, (1992) · Zbl 0768.11026
[23] Faure, H., Discrepancy and diaphony of digital \((0; 1)\)-sequences in prime base, Acta Arith., 117, 125-148, (2005) · Zbl 1080.11054
[24] Faure, H., Irregularities of distribution of digital \((0; 1)\)-sequences in prime base, Electron. J. Comb. Number Theory, 5, 3, (2005) · Zbl 1084.11041
[25] Flahive, M.; Niederreiter, H., On inversive congruential generators for pseudorandom numbers, (Finite Fields, Coding Theory, and Advances in Communications and Computing, Las Vegas, NV, 1991, Lect. Notes Pure Appl. Math., vol. 141, (1993), Marcel Dekker New York), 75-80 · Zbl 0790.11058
[26] Gomez-Perez, D.; Gutierrez, J.; Ibeas, Á., Attacking the Pollard generator, IEEE Trans. Inf. Theory, 52, 5518-5523, (2006) · Zbl 1309.94144
[27] Gomez-Perez, D.; Ostafe, A.; Topuzoğlu, A., On the Carlitz rank of permutations of \(\mathbb{F}_q\) and pseudorandom sequences, J. Complexity, (2013)
[28] Gutierrez, J.; Niederreiter, H.; Shparlinski, I., On the multidimensional distribution of inversive congruential pseudorandom numbers in parts of the period, Monatshefte Math., 129, 31-36, (2000) · Zbl 1011.11053
[29] Gutierrez, J.; Shparlinski, I.; Winterhof, A., On the linear and nonlinear complexity profile of nonlinear pseudorandom number-generators, IEEE Trans. Inf. Theory, 49, 60-64, (2003) · Zbl 1063.65005
[30] Heegard, C.; Wicker, S. B., Turbo coding, (1999), Kluwer Academic Publishers Dordrecht · Zbl 0996.94535
[31] Konyagin, S.; Pappalardi, F., Enumerating polynomials over finite fields by degree, Finite Fields Appl., 8, 548-553, (2002) · Zbl 1029.11067
[32] Konyagin, S.; Pappalardi, F., Enumerating polynomials over finite fields by degree II, Finite Fields Appl., 12, 26-37, (2006) · Zbl 1163.11350
[33] Krawczyk, H., How to predict congruential generators, J. Algorithms, 13, 527-545, (1992) · Zbl 0784.65006
[34] Lidl, R.; Mullen, G. L., Cycle structure of dickson permutation polynomials, Math. J. Okayama Univ., 33, 1-11, (1991) · Zbl 0759.11044
[35] Lidl, R.; Niederreiter, H., Finite fields, (1997), Cambridge University Press Cambridge
[36] Matsui, M., Linear cryptanalysis method for DES cipher, (Eurocrypt ’93, Lect. Notes Comput. Sci., vol. 765, (1993), Springer-Verlag New York), 386-397 · Zbl 0951.94519
[37] Mullen, G. L., Permutation polynomials over finite fields, (Finite Fields, Coding Theory, and Advances in Communications and Computing, Las Vegas, NV, 1991, Lect. Notes Pure Appl. Math., vol. 141, (1993), Marcel Dekker New York), 131-151 · Zbl 0808.11069
[38] Niederreiter, H., Random number generation and quasi-Monte Carlo methods, (1992), SIAM Press · Zbl 0761.65002
[39] Niederreiter, H.; Shparlinski, I. E., On the distribution and lattice structure of nonlinear congruential pseudorandom numbers, Finite Fields Appl., 5, 246-253, (1999) · Zbl 0942.11037
[40] Niederreiter, H.; Shparlinski, I. E., On the distribution of pseudorandom numbers and vectors generated by inversive methods, Appl. Algebra Eng. Commun. Comput., 10, 3, 189-202, (2000) · Zbl 0999.11040
[41] Niederreiter, H.; Shparlinski, I. E., On the distribution of inversive congruential pseudorandom numbers in parts of the period, Math. Comput., 70, 1569-1574, (2001) · Zbl 0983.11048
[42] Niederreiter, H.; Shparlinski, I. E., Dynamical systems generated by rational functions, (Fossorier, M.; Hoeholdt, T.; Poli, A., AAECC, Lect. Notes Comput. Sci., vol. 2643, (2003), Springer-Verlag Berlin), 6-17 · Zbl 1030.11072
[43] Nyberg, K., Differentially uniform mappings for cryptography, (Eurocrypt ’93, Lect. Notes Comput. Sci., vol. 765, (1993), Springer-Verlag New York), 55-64 · Zbl 0951.94510
[44] Panario, D.; Sakzad, A.; Stevens, B.; Wang, Q., Two new measures for permutations: ambiguity and deficiency, IEEE Trans. Inf. Theory, 57, 11, 7648-7657, (2011) · Zbl 1365.20051
[45] Pausinger, F., Weak multipliers for generalized Van der Corput sequences, J. Théor. Nr. Bordx., 24, 699-719, (2012)
[46] Pausinger, F.; Schmid, W. Ch., A good permutation for one-dimensional diaphony, Monte Carlo Methods Appl., 16, 307-322, (2010) · Zbl 1206.11096
[47] Pausinger, F.; Schmid, W. Ch., A lower bound for the diaphony of generalised Van der Corput sequences in arbitrary base b, Unif. Distrib. Theory, 6, 2, 31-46, (2011) · Zbl 1313.11096
[48] Rubio, I. M.; Mullen, G. L.; Corrada-Bravo, C. J.; Castro, F. N., Dickson permutation polynomials that decompose in cycles of the same length, (Contemp. Math., vol. 461, (2007)), 229-240
[49] Schmidt, W. M., Irregularities of distribution VII, Acta Arith., 21, 45-50, (1972) · Zbl 0244.10035
[50] Shparlinski, I. E., Finite fields: theory and computation - the meeting point of number theory, computer science, coding theory and cryptography, Math. Appl., vol. 477, (1999), Kluwer Academic Publishers · Zbl 0967.11052
[51] Shparlinski, I. E., Cryptographic applications of analytic number theory: complexity lower bounds and pseudorandomness, (2003), Birkhäuser Verlag · Zbl 1036.94001
[52] Sloane, N. J., Online encyclopedia of integer sequences, (2010), Published electronically at
[53] Sun, J.; Takeshita, O. Y., Interleavers for turbo codes using permutation polynomials over integer rings, IEEE Trans. Inf. Theory, 51, 101-130, (2005) · Zbl 1280.94121
[54] Topuzoğlu, A.; Winterhof, A., Pseudorandom sequences, (Garcia, A.; Stichtenoth, H., Topics in Geometry, Coding Theory and Cryptography, (2006), Springer-Verlag), 135-166 · Zbl 1134.11030
[55] Winterhof, A., Recent results on recursive nonlinear pseudorandom number generators, (Carlet, C.; Pott, A., SETA 2010, Lect. Notes Comput. Sci., (2010), Springer-Verlag Berlin), 113-124 · Zbl 1256.11043
[56] Zinterhof, P., Über einige abschätzungen bei der approximation von funktionen mit gleichverteilungsmethoden, Österr. Akad. Wiss. SB, II 185, 121-132, (1976) · Zbl 0356.65007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.