Abstract
Sequences, which are generated by deterministic algorithms so as to simulate truly random sequences are said to be pseudorandom (PR). A pseudorandom sequence in the unit interval [0, 1) is called a sequence of pseudorandom numbers (PRNs).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
H. Aly and A. Winterhof, “On the linear complexity profile of nonlinear congruential pseudorandom number generators with Dickson polynomials”, Des. Codes Cryptogr., to appear.
H. Aly and A. Winterhof, “On the k-error linear complexity over Fp of Legendre and Sidelnikov sequences”, preprint 2005.
P. Beelen and J.M. Doumen, “Pseudorandom sequences from elliptic curves”, Finite fields with applications to coding theory, cryptography and related areas (Oaxaca, 2001), Springer, Berlin, 37–52 (2002).
T. Beth and Z.D. Dai, “On the complexity of pseudo-random sequences—or: If you can describe a sequence it can’t be random”, Advances in cryptology—EUROCRYPT ′89 (Houthalen, 1989), Lecture Notes in Comput. Sci., Vol. 434, 533–543 (1990).
S.R. Blackburn, T. Etzion and K.G. Paterson, “Permutation polynomials, de Bruijn sequences, and linear complexity”, J. Combin. Theory Ser. A, Vol. 76, 55–82 (1996).
S.R. Blackburn, D. Gomez-Perez, J. Gutierrez and I. Shparlinski, “Predicting the inversive generator”, Lecture Notes in Comput. Sci., Vol. 2898, 264–275 (2003).
S.R. Blackburn, D. Gomez-Perez, J. Gutierrez and I. Shparlinski, “Predicting nonlinear pseudorandom number generators”, Math. Comp., Vol. 74, 1471–1494 (2005).
J. Bourgain, “Mordell’s exponential sum estimate revisited”, J. Amer. Math. Soc., Vol. 18, 477–499 (2005).
N. Brandstätter, T. Lange and A. Winterhof, “On the non-linearity and sparsity of Boolean functions related to the discrete logarithm”, preprint 2005.
N. Brandstätter and A. Winterhof, “Some notes on the two-prime generator”, IEEE Trans. Inform. Theory, Vol. 51, 3654–3657 (2005).
N. Brandstätter and A. Winterhof, “Nonlinearity of binary sequences with small autocorrelation”, Proceedings of the Second International Workshop on Sequence Design and its Applications in Communications (IWSDA ′05), to appear.
N. Brandstätter and A. Winterhof, “Linear complexity profile of binary sequences with small correlation measure”, preprint 2005.
T.W Cusick, C. Ding and A. Renvall, Stream ciphers and number theory, Revised edition. North-Holland Mathematical Library, 66. Elsevier Science B.V, Amsterdam, 2004.
C. Ding, G. Xiao and W. Shan, The stability theory of stream ciphers, Lecture Notes in Computer Science, Vol. 561, Springer-Verlag, Berlin 1991.
G. Dorfer, W Meidl and A. Winterhof, “Counting functions and expected values for the lattice profile at n”, Finite Fields Appl., Vol. 10, 636–652 (2004).
G. Dorfer and A. Winterhof, “Lattice structure and linear complexity profile of nonlinear pseudorandom number generators”, Appl. Algebra Engrg. Comm. Comput., Vol. 13, 499–508 (2003).
J. Eichenauer, H. Grothe, J. Lehn and A. Topuzoğlu, “A multiple recursive nonlinear congruential pseudo random number generator”, Manuscripta Math., Vol. 59, 331–346 (1987).
J. Eichenauer and J. Lehn, “A nonlinear congruential pseudorandom number generator”, Statist. Hefte, Vol. 27, 315–326 (1986).
J. Eichenauer-Herrmann, “Statistical independence of a new class of inversive congruential pseudorandom numbers”, Math. Comp., Vol. 60, 375–384 (1993).
Y.-C. Eun, H.-Y. Song and M.G. Kyureghyan, “One-error linear complexity over Fp of Sidelnikov sequences”, Sequences and Their Applications SETA 2004, Lecture Notes in Comput. Sci., Vol. 3486, 154–165 (2005).
M. Flahive and H. Niederreiter, “On inversive congruential generators for pseudorandom numbers”, Finite fields, coding theory, and advances in communications and computing (Las Vegas, NV, 1991), Lecture Notes in Pure and Appl. Math., Vol. 141, 75–80 (1993).
É. Fouvry, P. Michel, J. Rivat and A. Sárközy, “On the pseudorandomness of the signs of Kloosterman sums”, J. Aust. Math. Soc., Vol. 77, 425–436 (2004).
J.B. Friedlander, C. Pomerance and I. Shparlinski, “Period of the power generator and small values of Carmichael’s function”, Math. Comp., Vol. 70, 1591–1605 (2001).
J.B. Friedlander, C. Pomerance and I. Shparlinski, “Corrigendum to: Period of the power generator and small values of Carmichael’s function”, Math. Comp., Vol. 71, 1803–1806 (2002).
J.B. Friedlander and I. Shparlinski, “On the distribution of the power generator”, Math. Comp., Vol. 70, 1575–1589 (2001).
R.A. Games and A.H. Chan, “A fast algorithm for determining the complexity of a binary sequence with period 2n, IEEE Trans. Inform. Theory, Vol. 29, 144–146 (1983).
M.Z. Garaev, F. Luca, I. Shparlinski and A. Winterhof, “On the lower bound of the linear complexity over Fp of Sidelnikov sequences”, preprint 2005.
D. Gomez-Perez, J. Gutierrez and I. Shparlinski, “Exponential sums with Dickson polynomials”, Finite Fields Appl., Vol. 12, 16–25 (2006).
F. Griffin, H. Niederreiter and I. Shparlinski, “On the distribution of nonlinear recursive congruential pseudorandom numbers of higher orders”, Applied algebra, algebraic algorithms and error-correcting codes (Honolulu, HI, 1999), Lecture Notes in Comput. Sci., Vol. 1719, 87–93 (1999).
F. Griffin and I. Shparlinski, “On the linear complexity profile of the power generator”, IEEE Trans. Inform. Theory, Vol. 46, 2159–2162 (2000).
J. Gutierrez and D. Gomez-Perez, “Iterations of multivariate polynomials and discrepancy of pseudorandom numbers”, Applied algebra, algebraic algorithms and error-correcting codes (Melbourne, 2001), Lecture Notes in Comput. Sci., Vol. 2227, 192–199 (2001).
J. Gutierrez, I. Shparlinski and A. Winterhof, “On the linear and nonlinear complexity profile of nonlinear pseudorandom number-generators”, IEEE Trans. Inform. Theory, Vol. 49, 60–64 (2003).
K. Gyarmati, “On a family of pseudorandom binary sequences”, Period. Math. Hungar., Vol. 49, 45–63 (2004).
F. Hess and I. Shparlinski, “On the linear complexity and multidimensional distribution of congruential generators over elliptic curves”, Des. Codes and Cryptogr., Vol. 35, 111–117 (2005).
D. Jungnickel, Finite fields. Structure and arithmetics, Bibliographisches Institut, Mannheim, 1993.
A. Klapper, “The vulnerability of geometric sequences based on fields of odd characteristic”, J. Cryptology, Vol. 7, 33–51 (1994).
N. Koblitz, Algebraic Aspects of Cryptography, Springer-Verlag, Berlin Heidelberg, 1998.
D.R. Kohel and I. Shparlinski, “On exponential sums and group generators for elliptic curves over finite fields”, Algorithmic number theory (Leiden, 2000), Lecture Notes in Comput. Sci., Vol. 1838, 395–404 (2000).
S. Konyagin, T. Lange and I. Shparlinski, “Linear complexity of the discrete logarithm”, Des. Codes Cryptogr., Vol. 28, 135–146 (2003).
T. Lange and I. Shparlinski, “Certain exponential sums and random walks on elliptic curves”, Canad. J. Math., Vol. 57, 338–350 (2005).
R. Lidl, G.L. Mullen and G. Turnwald, Dickson polynomials, Pitman Monographs and Surveys in Pure and Applied Mathematics, 65. Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1993.
J.L. Massey and S. Serconek, “Linear complexity of periodic sequences: a general theory”, Advances in cryptology—CRYPTO ′96 (Santa Barbara, CA), Lecture Notes in Comput. Sci., Vol. 1109,358–371 1996.
C. Mauduit and A. Sárközy, “On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol”, Acta Arith., Vol. 82, 365–377 (1997).
W. Meidl, “How many bits have to be changed to decrease the linear complexity?”, Des. Codes Cryptogr., Vol. 33, 109–122 (2004).
W. Meidl, “Linear complexity and k-error linear complexity for pn-periodic sequences”, Coding, cryptography and combinatorics, Progr. Comput. Sci. Appl. Logic, Vol. 23, 227–235 (2004).
W. Meidl and A. Winterhof, “Lower bounds on the linear complexity of the discrete logarithm in finite fields”, IEEE Trans. Inform. Theory, Vol. 47, 2807–2811 (2001).
W. Meidl and A. Winterhof, “Linear complexity and polynomial degree of a function over a finite field”, Finite fields with applications to coding theory, cryptography and related areas (Oaxaca, 2001), Springer, Berlin, 229–238 (2002).
W. Meidl and A. Winterhof, “On the linear complexity profile of explicit nonlinear pseudorandom numbers”, Inform. Process. Lett., Vol. 85, 13–18 (2003).
W. Meidl and A. Winterhof, “On the linear complexity profile of some new explicit inversive pseudorandom numbers”, J. Complexity, Vol. 20, 350–355 (2004).
W. Meidl and A. Winterhof, “On the autocorrelation of cyclotomic generators”, Finite fields and applications, Lecture Notes in Comput. Sci., Vol. 2948, 1–11 (2004).
W. Meidl and A. Winterhof, “Some notes on the linear complexity of Sidelnikov-Lempel-Cohn-Eastman sequences”, Designs, Codes and Cryptography, to appear.
W. Meidl and A. Winterhof, “On the linear complexity profile of nonlinear pseudorandom number generators with Rédei functions”, Finite Fields Appl., to appear.
H. Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, Vol. 63. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992.
H. Niederreiter, “Constructions of (t, m, s)-nets”, Monte Carlo and quasi-Monte Carlo methods 1998 (Claremont, CA), Springer, Berlin, 70–85 (2000).
H. Niederreiter, “Linear complexity and related complexity measures for sequences”, Progress in cryptology—INDOCRYPT 2003, Lecture Notes in Comput. Sci., Vol. 2904, 1–17 (2003).
H. Niederreiter, “Constructions of (t, m, s)-nets and (t, s)-sequences”, Finite Fields Appl., Vol. 11, 578–600 (2005).
H. Niederreiter and I. Shparlinski, “On the distribution and lattice structure of nonlinear congruential pseudorandom numbers”, Finite Fields Appl., Vol. 5, 246–253 (1999).
H. Niederreiter and I. Shparlinski, “On the distribution of inversive congruential pseudorandom numbers in parts of the period”, Math. Comp., Vol. 70, 1569–1574 (2001).
H. Niederreiter and I. Shparlinski, “Recent advances in the theory of nonlinear pseudorandom number generators”, Monte Carlo and quasi-Monte Carlo methods, 2000 (Hong Kong), Springer, Berlin, 86–102 (2002).
H. Niederreiter and I. Shparlinski, “On the average distribution of inversive pseudorandom numbers”, Finite Fields Appl., Vol. 8, 491–503 (2002).
H. Niederreiter and A. Winterhof, “Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators”, Acta Arith., Vol. 93, 387–399 (2000).
H. Niederreiter and A. Winterhof, “On the distribution of some new explicit nonlinear congruential pseudorandom numbers”, Sequences and Their Applications SETA 2004, Lecture Notes in Comput. Sci., Vol. 3486, 266–274, (2005).
R. Nöbauer, “Rédei-Permutationen endlicher Körper”, Contributions to general algebra, 5 (Salzburg, 1986), Hölder-Pichler-Tempsky, Vienna, 235–246 (1987).
W.M. Schmidt, Equations over finite fields. An elementary approach, Lecture Notes in Mathematics, Vol. 536, 1976.
I. Shparlinski, “On the linear complexity of the power generator”, Des. Codes Cryptogr., Vol. 23, 5–10 (2001).
I. Shparlinski, Cryptographic applications of analytic number theory. Complexity lower bounds and pseudorandomness, Progress in Computer Science and Applied Logic, 22. Birkhäuser Verlag, Basel, 2003.
I. Shparlinski and A. Winterhof, “On the linear complexity of bounded integer sequences over different moduli”, Inform. Process. Lett., Vol. 96, 175–177 (2005).
V.M. Sidel’nikov, “Some k-valued pseudo-random sequences and nearly equidistant codes”, Problems of Information Transmission, Vol. 5, 12–16 (1969); translated from Problemy Peredači Informacii, Vol. 5, 16–22 (1969), (Russian).
M. Stamp and C.F. Martin, “An algorithm for the k-error linear complexity of binary sequences with period 2n, IEEE Trans. Inform. Theory, Vol. 39, 1398–1401 (1993).
A. Tietäväinen, “Vinogradov’s method and some applications”, Number theory and its applications (Ankara, 1996), Lecture Notes in Pure and Appl. Math., Vol. 204, 261–282 (1999).
A. Topuzoğlu and A. Winterhof, “On the linear complexity profile of nonlinear congruential pseudorandom number generators of higher orders”, Appl. Algebra Engrg. Comm. Comput, Vol. 16, 219–228 (2005).
A. Topuzoğlu and A. Winterhof, “On the distribution of inversive congruential pseudorandom number generators of higher orders with largest possible period”, preprint 2006.
R.J. Turyn, “The linear generation of Legendre sequence”, J. Soc. Indust. Appl. Math., Vol. 12, 115–116 (1964).
I.M. Vinogradov, Elements of number theory, Dover Publications, Inc., New York, 1954.
Y. Wang, “Linear complexity versus pseudorandomness: on Beth and Dai’s result”, Advances in cryptology—ASIACRYPT′99 (Singapore), Lecture Notes in Comput. Sci., Vol. 1716, 288–298 (1999).
A. Winterhof, “A note on the linear complexity profile of the discrete logarithm in finite fields”, Coding, cryptography and combinatorics, Progr. Comput. Sci. Appl. Logic, Vol. 23, 359–367 (2004).
A. Winterhof, “On the distribution of some new explicit inversive pseudorandom numbers and vectors”, Proceedings MC2QMC 2004, to appear.
G. Xiao and S. Wei, “Fast algorithms for determining the linear complexity of period sequences”, Progress in cryptology — INDOCRYPT 2002. Third international conference on cryptology in India, Hyderabad, India, December 16–18, 2002, Lect. Notes in Comput. Sci., Vol. 2551, 12–21, (2002).
G. Xiao, S. Wei, K.Y. Lam and K. Imamura, “A fast algorithm for determining the linear complexity of a sequence with period pn over GF(q)”, IEEE Trans. Inform. Theory, Vol. 46, 2203–2206 (2000).
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer
About this chapter
Cite this chapter
Topuzoğlu, A., Winterhof, A. (2006). PSEUDORANDOM SEQUENCES. In: Garcia, A., Stichtenoth, H. (eds) Topics in Geometry, Coding Theory and Cryptography. Algebra and Applications, vol 6. Springer, Dordrecht . https://doi.org/10.1007/1-4020-5334-4_4
Download citation
DOI: https://doi.org/10.1007/1-4020-5334-4_4
Publisher Name: Springer, Dordrecht
Print ISBN: 978-1-4020-5333-7
Online ISBN: 978-1-4020-5334-4
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)