Article

Dynamical systems generated by rational functions

Authors:

Igor E. ShparlinskiAuthors Info & Claims

AAECC'03: Proceedings of the 15th international conference on Applied algebra, algebraic algorithms and error-correcting codes

Pages 6 - 17

Published: 12 May 2003 Publication History

Abstract

We consider dynamical systems generated by iterations of rational functions over finite fields and residue class rings. We present a survey of recent developments and outline several open problem.

References

[1]

L. Arnold, Random Dynamical Systems, Springer-Verlag, Berlin, 1998.

Google Scholar

[2]

G. Barat, T. Downarowicz and P. Liardet, Dynamiques associées à une échelle de numération, Acta Arith. 103, 41-78 (2002).

Crossref

Google Scholar

[3]

V. Berthé and H. Nakada, On continued fraction expansions in positive characteristic: equivalence relations and some metric properties, Expositiones Math. 18, 257-284 (2000).

Google Scholar

[4]

L. Blum, M. Blum and M. Shub, A simple unpredictable pseudo-random number generator, SIAM J. Computing 15, 364-383 (1986).

Digital Library

Google Scholar

[5]

T. Cochrane, Exponential sums modulo prime powers, Acta Arith. 101, 131-149 (2002).

Crossref

Google Scholar

[6]

T. Cochrane, C. Li and Z.Y. Zheng, Upper bounds on character sums with rational function entries, Acta Math. Sinica (English Ser.) 19, 1-11 (2003).

Google Scholar

[7]

T. Cochrane and Z.Y. Zheng, Pure and mixed exponential sums, Acta Arith. 91, 249-278 (1999).

Crossref

Google Scholar

[8]

T. Cochrane and Z.Y. Zheng, Exponential sums with rational function entries, Acta Arith. 95, 67-95 (2000).

Crossref

Google Scholar

[9]

T. Cochrane and Z.Y. Zheng, On upper bounds of Chalk and Hua for exponential sums, Proc. Amer. Math. Soc. 129, 2505-2516 (2001).

Crossref

Google Scholar

[10]

T. Cochrane and Z.Y. Zheng, A survey on pure and mixed exponential sums modulo prime powers, Number Theory for the Millennium (M.A. Bennett et al., eds.), vol. 1, pp. 271-300, A.K. Peters, Natick, MA, 2002.

Google Scholar

[11]

S.D. Cohen, H. Niederreiter, I.E. Shparlinski and M. Zieve, Incomplete character sums and a special class of permutations, J. Théorie des Nombres Bordeaux 13, 53-63 (2001).

Crossref

Google Scholar

[12]

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer-Verlag, New York, 2001.

Google Scholar

[13]

J. Eichenauer-Herrmann, E. Herrmann and S. Wegenkittl, A survey of quadratic and inversive congruential pseudorandom numbers, Monte Carlo and Quasi-Monte Carlo Methods 1996 (H. Niederreiter et al., eds.), Lect. Notes in Stat., vol. 127, pp. 66-97, Springer-Verlag, New York, 1998.

Google Scholar

[14]

G. Everest and T. Ward, Heights of Polynomials and Entropy in Algebraic Dynamics, Springer-Verlag, London, 1999.

Crossref

Google Scholar

[15]

M. Flahive and H. Niederreiter, On inversive congruential generators for pseudo-random numbers, Finite Fields, Coding Theory, and Advances in Communications and Computing (G.L. Mullen and P.J.-S. Shiue, eds.), pp. 75-80, Marcel Dekker, New York, 1993.

Google Scholar

[16]

P. Flajolet and A.M. Odlyzko, Random mapping statistics, Advances in Cryptology - EUROCRYPT '89 (J.-J. Quisquater and J. Vandewalle, eds.), Lect. Notes in Comp. Sci., vol. 434, pp. 329-354, Springer-Verlag, Berlin, 1990.

Digital Library

Google Scholar

[17]

L. Flatto, Z-numbers and β-transformations, Symbolic Dynamics and Its Applications, Contemporary Math., vol. 135, pp. 181-201, Amer. Math. Soc., Providence, RI, 1992.

Google Scholar

[18]

L. Flatto, J.C. Lagarias and B. Poonen, The zeta function of the beta transformation, Ergodic Theory Dynam. Systems 14, 237-266 (1994).

Crossref

Google Scholar

[19]

J.B. Friedlander, J. Hansen and I.E. Shparlinski, Character sums with exponential functions, Mathematika 47, 75-85 (2000).

Crossref

Google Scholar

[20]

J.B. Friedlander, J. Hansen, and I.E. Shparlinski, On the distribution of the power generator modulo a prime power, Proc. DIMACS Workshop on Unusual Applications of Number Theory 2000, Amer. Math. Soc., Providence, RI (to appear).

Google Scholar

[21]

J.B. Friedlander, S.V. Konyagin and I.E. Shparlinski, Some doubly exponential sums over Z_m, Acta Arith. 105, 349-370 (2002).

Crossref

Google Scholar

[22]

J.B. Friedlander, D. Lieman and I.E. Shparlinski, On the distribution of the RSA generator, Sequences and Their Applications (C. Ding, T. Helleseth and H. Niederreiter, eds.), pp. 205-212, Springer-Verlag, London, 1999.

Google Scholar

[23]

J.B. Friedlander, C. Pomerance and I.E. Shparlinski, Period of the power generator and small values of Carmichael's function, Math. Comp. 70, 1591-1605 (2001).

Digital Library

Google Scholar

[24]

J.B. Friedlander and I.E. Shparlinski, On the distribution of the power generator, Math. Comp. 70, 1575-1589 (2001).

Digital Library

Google Scholar

[25]

S. Gao, Elements of provable high orders in finite fields, Proc. Amer. Math. Soc. 127, 1615-1623 (1999).

Crossref

Google Scholar

[26]

F. Griffin, H. Niederreiter and I.E. Shparlinski, On the distribution of nonlinear recursive congruential pseudorandom numbers of higher orders, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (M. Fossorier et al., eds.), Lect. Notes in Comp. Sci., vol. 1719, pp. 87-93, Springer-Verlag, Berlin, 1999.

Digital Library

Google Scholar

[27]

J. Gutierrez and D. Gomez-Perez, Iterations of multivariate polynomials and discrepancy of pseudorandom numbers, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (S. Boztas and I.E. Shparlinski, eds.), Lect. Notes in Comp. Sci., vol. 2227, pp. 192-199, Springer-Verlag, Berlin, 2001.

Digital Library

Google Scholar

[28]

J. Gutierrez, H. Niederreiter and I.E. Shparlinski, On the multidimensional distribution of inversive congruential pseudorandom numbers in parts of the period, Monatsh. Math. 129, 31-36 (2000).

Crossref

Google Scholar

[29]

K. Huber, On the period length of generalized inversive pseudorandom number generators, Applicable Algebra Engrg. Comm. Comput. 5, 255-260 (1994).

Crossref

Google Scholar

[30]

A. Katok and B. Hasselblatt, Introduction to the Modern Theory of Dynamical Systems, Cambridge University Press, Cambridge, 1995.

Crossref

Google Scholar

[31]

A. Klapper, The distribution of points in orbits of PGL.(GF(q)) acting on GF(qⁿ), Finite Fields, Coding Theory, and Advances in Communications and Computing (G.L. Mullen and P.J.-S. Shiue, eds.), pp. 430-431, Marcel Dekker, New York, 1993.

Google Scholar

[32]

D.E. Knuth, The Art of Computer Programming, vol. 2, 3rd ed., Addison-Wesley, Reading, MA, 1998.

Digital Library

Google Scholar

[33]

J.C. Lagarias, Pseudorandom number generators in cryptography and number theory, Cryptology and Computational Number Theory (C. Pomerance, ed.), Proc. Symp. in Appl. Math., vol. 42, pp. 115-143, Amer. Math. Soc., Providence, RI, 1990.

Google Scholar

[34]

J.C. Lagarias, Number theory and dynamical systems, The Unreasonable Effectiveness of Number Theory, Proc. Symp. in Appl. Math., vol. 46, pp. 35-72, Amer. Math. Soc., Providence, RI, 1992.

Google Scholar

[35]

J.C. Lagarias, H.A. Porta and K.B. Stolarsky, Asymmetric tent map expansions. I. Eventually periodic points, J. London Math. Soc. 47, 542-556 (1993).

Crossref

Google Scholar

[36]

J.C. Lagarias, H.A. Porta and K.B. Stolarsky, Asymmetric tent map expansions. II. Purely periodic points, Illinois J. Math. 38, 574-588 (1994).

Crossref

Google Scholar

[37]

R. Lidl, G.L. Mullen and G. Turnwald, Dickson Polynomials, Longman, Harlow, 1993.

Google Scholar

[38]

R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 1997.

Digital Library

Google Scholar

[39]

C.J. Moreno and O. Moreno, Exponential sums and Goppa codes: I, Proc. Amer. Math. Soc. 111, 523-531 (1991).

Google Scholar

[40]

P. Morton, Periods of maps on irreducible polynomials over finite fields, Finite Fields Appl. 3, 11-24 (1997).

Digital Library

Google Scholar

[41]

P. Morton, Arithmetic properties of periodic points of quadratic maps. II, Acta Arith. 87, 89-102 (1998).

Crossref

Google Scholar

[42]

P. Morton and J.H. Silverman, Rational periodic points of rational functions, Internat. Math. Res. Notices 2, 97-110 (1994).

Crossref

Google Scholar

[43]

P. Morton and J.H. Silverman, Periodic points, multiplicities, and dynamical units, J. Reine Angew. Math. 461, 81-122 (1995).

Google Scholar

[44]

P. Morton and F. Vivaldi, Bifurcations and discriminants for polynomial maps, Nonlinearity 8, 571-584 (1995).

Crossref

Google Scholar

[45]

W. Narkiewicz, Polynomial Mappings, Lect. Notes in Math., vol. 1600, Springer-Verlag, Berlin, 1995.

Google Scholar

[46]

H. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84, 957-1041 (1978).

Crossref

Google Scholar

[47]

H. Niederreiter, The probabilistic theory of linear complexity, Advances in Cryptology - EUROCRYPT '88 (C.G. Günther, ed.), Lect. Notes in Comp. Sci., vol. 330, pp. 191-209, Springer-Verlag, Berlin, 1988.

Digital Library

Google Scholar

[48]

H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992.

Digital Library

Google Scholar

[49]

H. Niederreiter, New developments in uniform pseudorandom number and vector generation, Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (H. Niederreiter and P.J.-S. Shiue, eds.), Lect. Notes in Stat., vol. 106, pp. 87-120, Springer-Verlag, New York, 1995.

Google Scholar

[50]

H. Niederreiter, Design and analysis of nonlinear pseudorandom number generators, Monte Carlo Simulation (G.I. Schuëller and P.D. Spanos, eds.), pp. 3-9, A.A. Balkema Publishers, Rotterdam, 2001.

Google Scholar

[51]

H. Niederreiter and I.E. Shparlinski, On the distribution and lattice structure of nonlinear congruential pseudorandom numbers, Finite Fields Appl. 5, 246-253 (1999).

Digital Library

Google Scholar

[52]

H. Niederreiter and I.E. Shparlinski, On the distribution of pseudorandom numbers and vectors generated by inversive methods, Applicable Algebra Engrg. Comm. Comput. 10, 189-202 (2000).

Crossref

Google Scholar

[53]

H. Niederreiter and I.E. Shparlinski, Exponential sums and the distribution of inversive congruential pseudorandom numbers with prime-power modulus, Acta Arith. 92, 89-98 (2000).

Crossref

Google Scholar

[54]

H. Niederreiter and I.E. Shparlinski, On the distribution of inversive congruential pseudorandom numbers in parts of the period, Math. Comp. 70, 1569-1574 (2001).

Digital Library

Google Scholar

[55]

H. Niederreiter and I.E. Shparlinski, Recent advances in the theory of nonlinear pseudorandom number generators, Monte Carlo and Quasi-Monte Carlo Methods 2000 (K.-T. Fang, F.J. Hickernell and H. Niederreiter, eds.), pp. 86-102, Springer-Verlag, Berlin, 2002.

Google Scholar

[56]

H. Niederreiter and I.E. Shparlinski, On the average distribution of inversive pseudorandom numbers, Finite Fields Appl. 8, 491-503 (2002).

Digital Library

Google Scholar

[57]

H. Niederreiter and I.E. Shparlinski, On the distribution of power residues and primitive elements in some nonlinear recurring sequences, Bull. Lond. Math. Soc. (to appear).

Google Scholar

[58]

H. Niederreiter and A. Winterhof, Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators, Acta Arith. 93, 387-399 (2000).

Crossref

Google Scholar

[59]

H. Niederreiter and A. Winterhof, On the distribution of compound inversive congruential pseudorandom numbers, Monatsh. Math. 132, 35-48 (2001).

Crossref

Google Scholar

[60]

H. Niederreiter and A. Winterhof, On the lattice structure of pseudorandom numbers generated over arbitrary finite fields, Applicable Algebra Engrg. Comm. Comput. 12, 265-272 (2001).

Crossref

Google Scholar

[61]

H. Niederreiter and A. Winterhof, On a new class of inversive pseudorandom numbers for parallelized simulation methods, Periodica Math. Hungarica 42, 77-87 (2001).

Crossref

Google Scholar

[62]

H. Niederreiter and A. Winterhof, On the distribution of points in orbits of PGL(2, q) acting on GF(qⁿ), preprint, 2002.

Google Scholar

[63]

A.G. Postnikov, Ergodic Problems in the Theory of Congruences and of Diophantine Approximations, Proc. Steklov Inst. Math., vol. 82, Amer. Math. Soc., Providence, RI, 1967.

Google Scholar

[64]

C. Robinson, Dynamical Systems: Stability, Symbolic Dynamics, and Chaos, CRC Press, Boca Raton, FL, 1999.

Google Scholar

[65]

J. Schmeling, Symbolic dynamics for β-shifts and self-normal numbers, Ergodic Theory Dynam. Systems 17, 675-694 (1997).

Crossref

Google Scholar

[66]

K. Schmidt, Dynamical Systems of Algebraic Origin, Progress in Math., vol. 128, Birkhäuser Verlag, Basel, 1995.

Google Scholar

[67]

I.E. Shparlinski, Exponential sums in coding theory, cryptology and algorithms, Coding Theory and Cryptology (H. Niederreiter, ed.), pp. 323-383, World Scientific Publ., Singapore, 2002.

Google Scholar

[68]

J.H. Silverman, The field of definition for dynamical systems on P., Compositio Math. 98, 269-304 (1995).

Google Scholar

[69]

J.H. Silverman, The space of rational maps on P., Duke Math. J. 94, 41-77 (1998).

Crossref

Google Scholar

[70]

S.B. Stečkin, An estimate of a complete rational trigonometric sum (Russian), Trudy Mat. Inst. Steklov. 143, 188-207 (1977).

Google Scholar

[71]

G.J. Wirsching, The Dynamical System Generated by the 3n + 1 Function, Lect. Notes in Math., vol. 1681, Springer-Verlag, Berlin, 1998.

Google Scholar

Cited By

View all

Ostafe APelican EShparlinski I(2010)On pseudorandom numbers from multivariate polynomial systemsFinite Fields and Their Applications10.1016/j.ffa.2010.05.00216:5(320-328)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1016/j.ffa.2010.05.002
Ostafe A(2010)Multivariate permutation polynomial systems and nonlinear pseudorandom number generatorsFinite Fields and Their Applications10.1016/j.ffa.2009.12.00316:3(144-154)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.1016/j.ffa.2009.12.003
Ibeas Martín Á(2008)On the period of the Naor--Reingold sequenceInformation Processing Letters10.1016/j.ipl.2008.05.025108:5(304-307)Online publication date: 1-Nov-2008
https://dl.acm.org/doi/10.1016/j.ipl.2008.05.025
Show More Cited By

Recommendations

Hidden oscillations in dynamical systems
Proceedings of the 15th WSEAS international conference on Systems

The classical attractors of Lorenz, Rossler, Chua, Chen, and other widely-known attractors are those excited from unstable equilibria. From computational point of view this allows one to use numerical method, in which after transient process a ...
Hidden oscillations in dynamical systems

The classical attractors of Lorenz, Rössler, Chua, Chen, and other widely-known attractors are those excited from unstable equilibria. From computational point of view this allows one to use standard numerical method, in which after transient process a ...
Analysing Dynamical Systems
SIMULTECH 2017: Proceedings of the 7th International Conference on Simulation and Modeling Methodologies, Technologies and Applications

Ordinary differential equations arise in a variety of applications, including e.g. climate systems, and can exhibit complicated dynamical behaviour. Complete Lyapunov functions can capture this behaviour by dividing the phase space into the chain-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

AAECC'03: Proceedings of the 15th international conference on Applied algebra, algebraic algorithms and error-correcting codes

May 2003

265 pages

ISBN:3540401113

Editors:
Marc Fossorier
University of Hawaii, Department of Electrical Engineering, Honolulu, HI
,
Tom Høholdt
The Technical University of Denmark, Department of Mathematics, Lyngby, Denmark
,
Alain Poli
IRIT, Université Paul Sabatier, Toulouse cédex, France

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 12 May 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ostafe APelican EShparlinski I(2010)On pseudorandom numbers from multivariate polynomial systemsFinite Fields and Their Applications10.1016/j.ffa.2010.05.00216:5(320-328)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1016/j.ffa.2010.05.002
Ostafe A(2010)Multivariate permutation polynomial systems and nonlinear pseudorandom number generatorsFinite Fields and Their Applications10.1016/j.ffa.2009.12.00316:3(144-154)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.1016/j.ffa.2009.12.003
Ibeas Martín Á(2008)On the period of the Naor--Reingold sequenceInformation Processing Letters10.1016/j.ipl.2008.05.025108:5(304-307)Online publication date: 1-Nov-2008
https://dl.acm.org/doi/10.1016/j.ipl.2008.05.025
Gutierrez JWinterhof A(2008)Exponential sums of nonlinear congruential pseudorandom number generators with Rédei functionsFinite Fields and Their Applications10.1016/j.ffa.2007.03.00414:2(410-416)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1016/j.ffa.2007.03.004
Blackburn SGomez-Perez DGutierrez JShparlinski I(2006)Reconstructing noisy polynomial evaluation in residue ringsJournal of Algorithms10.1016/j.jalgor.2004.07.00261:2(47-59)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1016/j.jalgor.2004.07.002
Gomez DGutierrez JIbeas A(2005)Cryptanalysis of the quadratic generatorProceedings of the 6th international conference on Cryptology in India10.1007/11596219_10(118-129)Online publication date: 10-Dec-2005
https://dl.acm.org/doi/10.1007/11596219_10

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

Hidden oscillations in dynamical systems

Hidden oscillations in dynamical systems

Analysing Dynamical Systems

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations