Full orbit sequences in affine spaces via fractional jumps and pseudorandom number generation

Amadio Guidi, Federico; Lindqvist, Sofia; Micheli, Giacomo

doi:10.1090/mcom/3400

Full orbit sequences in affine spaces via fractional jumps and pseudorandom number generation

Authors: Federico Amadio Guidi, Sofia Lindqvist and Giacomo Micheli
Journal: Math. Comp. 88 (2019), 2005-2025
MSC (2010): Primary 11B37, 15B33, 11T06, 11K38, 11K45, 11T23, 65C10, 37P25
DOI: https://doi.org/10.1090/mcom/3400
Published electronically: November 27, 2018
MathSciNet review: 3925495
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: Let be a positive integer. In this paper we provide a general theory to produce full orbit sequences in the affine -dimensional space over a finite field. For our construction covers the case of the Inversive Congruential Generators (ICG). In addition, for we show that the sequences produced using our construction are easier to compute than ICG sequences. Furthermore, we prove that they have the same discrepancy bounds as the ones constructed using the ICG.

[1] Nina Brandstätter and Arne Winterhof, Some notes on the two-prime generator of order 2, IEEE Trans. Inform. Theory 51 (2005), no. 10, 3654–3657. MR 2237532, https://doi.org/10.1109/TIT.2005.855615
[2] Wun Seng Chou, On inversive maximal period polynomials over finite fields, Appl. Algebra Engrg. Comm. Comput. 6 (1995), no. 4-5, 245–250. MR 1339590, https://doi.org/10.1007/BF01235718
[3] Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456
[4] Jürgen Eichenauer-Herrmann, Inversive congruential pseudorandom numbers avoid the planes, Math. Comp. 56 (1991), no. 193, 297–301. MR 1052092, https://doi.org/10.1090/S0025-5718-1991-1052092-X
[5] J. Eichenauer-Herrmann,
Inversive congruential pseudorandom numbers: A tutorial,
Int. Stat. Rev., 1992, pp. 167-176.
[6] Jürgen Eichenauer-Herrmann, Statistical independence of a new class of inversive congruential pseudorandom numbers, Math. Comp. 60 (1993), no. 201, 375–384. MR 1159168, https://doi.org/10.1090/S0025-5718-1993-1159168-9
[7] Jürgen Eichenauer-Herrmann, Eva Herrmann, and Stefan Wegenkittl, A survey of quadratic and inversive congruential pseudorandom numbers, Monte Carlo and quasi-Monte Carlo methods 1996 (Salzburg), Lect. Notes Stat., vol. 127, Springer, New York, 1998, pp. 66–97. MR 1644512, https://doi.org/10.1007/978-1-4612-1690-2_4
[8] Edwin D. El-Mahassni and Domingo Gomez, On the distribution of nonlinear congruential pseudorandom numbers of higher orders in residue rings, Applied algebra, algebraic algorithms, and error-correcting codes, Lecture Notes in Comput. Sci., vol. 5527, Springer, Berlin, 2009, pp. 195–203. MR 2580868, https://doi.org/10.1007/978-3-642-02181-7_21
[9] Andrea Ferraguti and Giacomo Micheli, On the existence of infinite, non-trivial 𝐹-sets, J. Number Theory 168 (2016), 1–12. MR 3515802, https://doi.org/10.1016/j.jnt.2016.03.024
[10] Andrea Ferraguti, Giacomo Micheli, and Reto Schnyder, On sets of irreducible polynomials closed by composition, Arithmetic of finite fields, Lecture Notes in Comput. Sci., vol. 10064, Springer, Cham, 2016, pp. 77–83. MR 3649090
[11] A. Ferraguti, G. Micheli, and R. Schnyder,
Irreducible compositions of degree two polynomials over finite fields have regular structure,
arXiv preprint arXiv:1701.06040, 2017.
[12] Domingo Gómez-Pérez, Alina Ostafe, and Igor Shparlinski, Algebraic entropy, automorphisms and sparsity of algebraic dynamical systems and pseudorandom number generators, Math. Comp. 83 (2014), no. 287, 1535–1550. MR 3167471, https://doi.org/10.1090/S0025-5718-2013-02780-9
[13] Jaime Gutierrez, Igor E. Shparlinski, and Arne Winterhof, On the linear and nonlinear complexity profile of nonlinear pseudorandom number-generators, IEEE Trans. Inform. Theory 49 (2003), no. 1, 60–64. MR 1965887, https://doi.org/10.1109/TIT.2002.806144
[14] D. R. Heath-Brown and G. Micheli,
Irreducible polynomials over finite fields produced by composition of quadratics,
arXiv preprint arXiv:1701.05031, 2017.
[15] Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR 1412797
[16] Carlos J. Moreno and Oscar Moreno, Exponential sums and Goppa codes. I, Proc. Amer. Math. Soc. 111 (1991), no. 2, 523–531. MR 1028291, https://doi.org/10.1090/S0002-9939-1991-1028291-1
[17] Harald Niederreiter and Igor E. Shparlinski, Recent advances in the theory of nonlinear pseudorandom number generators, Monte Carlo and quasi-Monte Carlo methods, 2000 (Hong Kong), Springer, Berlin, 2002, pp. 86–102. MR 1958848
[18] Harald Niederreiter and Igor E. Shparlinski, Dynamical systems generated by rational functions, Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 2003) Lecture Notes in Comput. Sci., vol. 2643, Springer, Berlin, 2003, pp. 6–17. MR 2042407, https://doi.org/10.1007/3-540-44828-4_2
[19] Alina Ostafe, Pseudorandom vector sequences derived from triangular polynomial systems with constant multipliers, Arithmetic of finite fields, Lecture Notes in Comput. Sci., vol. 6087, Springer, Berlin, 2010, pp. 62–72. MR 2674215, https://doi.org/10.1007/978-3-642-13797-6_5
[20] Alina Ostafe, Elena Pelican, and Igor E. Shparlinski, On pseudorandom numbers from multivariate polynomial systems, Finite Fields Appl. 16 (2010), no. 5, 320–328. MR 2678620, https://doi.org/10.1016/j.ffa.2010.05.002
[21] Alina Ostafe and Igor E. Shparlinski, On the degree growth in some polynomial dynamical systems and nonlinear pseudorandom number generators, Math. Comp. 79 (2010), no. 269, 501–511. MR 2552237, https://doi.org/10.1090/S0025-5718-09-02271-6
[22] Alina Ostafe and Igor E. Shparlinski, On the length of critical orbits of stable quadratic polynomials, Proc. Amer. Math. Soc. 138 (2010), no. 8, 2653–2656. MR 2644881, https://doi.org/10.1090/S0002-9939-10-10404-3
[23] A. Schönhage,
Schnelle Berechnung von Kettenbruchentwicklungen,
Acta Inform., 1 (1971), no. 2, 139-144, .
[24] A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, https://doi.org/10.1007/bf02242355
[25] Igor E. Shparlinski, On the average distribution of pseudorandom numbers generated by nonlinear permutations, Math. Comp. 80 (2011), no. 274, 1053–1061. MR 2772110, https://doi.org/10.1090/S0025-5718-2010-02408-1
[26] Alev Topuzoğlu and Arne Winterhof, Pseudorandom sequences, Topics in geometry, coding theory and cryptography, Algebr. Appl., vol. 6, Springer, Dordrecht, 2007, pp. 135–166. MR 2278037, https://doi.org/10.1007/1-4020-5334-4_4
[27] Arne Winterhof, Recent results on recursive nonlinear pseudorandom number generators (invited paper), Sequences and their applications—SETA 2010, Lecture Notes in Comput. Sci., vol. 6338, Springer, Berlin, 2010, pp. 113–124. MR 2830717, https://doi.org/10.1007/978-3-642-15874-2_9