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
HTML articles powered by AMS MathViewer

by Federico Amadio Guidi, Sofia Lindqvist and Giacomo Micheli;

Math. Comp. 88 (2019), 2005-2025

DOI: https://doi.org/10.1090/mcom/3400

Published electronically: November 27, 2018

HTML | PDF | Request permission

Abstract:

Let $n$ be a positive integer. In this paper we provide a general theory to produce full orbit sequences in the affine $n$-dimensional space over a finite field. For $n=1$ our construction covers the case of the Inversive Congruential Generators (ICG). In addition, for $n>1$ 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.

References

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, DOI 10.1109/TIT.2005.855615
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, DOI 10.1007/BF01235718
Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456, DOI 10.1007/BFb0093404
Jürgen Eichenauer-Herrmann, Inversive congruential pseudorandom numbers avoid the planes, Math. Comp. 56 (1991), no. 193, 297–301. MR 1052092, DOI 10.1090/S0025-5718-1991-1052092-X
J. Eichenauer-Herrmann, Inversive congruential pseudorandom numbers: A tutorial, Int. Stat. Rev., 1992, pp. 167–176.
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, DOI 10.1090/S0025-5718-1993-1159168-9
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, DOI 10.1007/978-1-4612-1690-2_{4}
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, DOI 10.1007/978-3-642-02181-7_{2}1
Andrea Ferraguti and Giacomo Micheli, On the existence of infinite, non-trivial $F$-sets, J. Number Theory 168 (2016), 1–12. MR 3515802, DOI 10.1016/j.jnt.2016.03.024
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, DOI 10.1007/978-3-319-55227-9_{6}
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.
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, DOI 10.1090/S0025-5718-2013-02780-9
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, DOI 10.1109/TIT.2002.806144
D. R. Heath-Brown and G. Micheli, Irreducible polynomials over finite fields produced by composition of quadratics, arXiv preprint arXiv:1701.05031, 2017.
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
Carlos J. Moreno and Oscar Moreno, Exponential sums and Goppa codes. I, Proc. Amer. Math. Soc. 111 (1991), no. 2, 523–531. MR 1028291, DOI 10.1090/S0002-9939-1991-1028291-1
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
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, DOI 10.1007/3-540-44828-4_{2}
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, DOI 10.1007/978-3-642-13797-6_{5}
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, DOI 10.1016/j.ffa.2010.05.002
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, DOI 10.1090/S0025-5718-09-02271-6
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, DOI 10.1090/S0002-9939-10-10404-3
A. Schönhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inform., 1 (1971), no. 2, 139–144, .
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
Igor E. Shparlinski, On the average distribution of pseudorandom numbers generated by nonlinear permutations, Math. Comp. 80 (2011), no. 274, 1053–1061. MR 2772110, DOI 10.1090/S0025-5718-2010-02408-1
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, DOI 10.1007/1-4020-5334-4_{4}
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, DOI 10.1007/978-3-642-15874-2_{9}