A recipe for an unpredictable random number generator

In this work we present a model for computing the random processes in digital computers which solves the problem of periodic sequences and hidden errors produced by correlations. We show that systems with noninvertible non-linearities can produce unpredictable sequences of independent random numbe...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Condensed Matter Physics
Datum:	2006
Hauptverfasser:	Garcıa-Nustes, M.A., Trujillo, L., Gonzalez, J.A.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Інститут фізики конденсованих систем НАН України 2006
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/121323
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	A recipe for an unpredictable random number generator / M.A. Garcıa-Nustes, L. Trujillo, J.A. Gonzalez// Condensed Matter Physics. — 2006. — Т. 9, № 2(46). — С. 367–372. — Бібліогр.: 20 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-121323
record_format	dspace
spelling	Garcıa-Nustes, M.A. Trujillo, L. Gonzalez, J.A. 2017-06-14T05:54:12Z 2017-06-14T05:54:12Z 2006 A recipe for an unpredictable random number generator / M.A. Garcıa-Nustes, L. Trujillo, J.A. Gonzalez// Condensed Matter Physics. — 2006. — Т. 9, № 2(46). — С. 367–372. — Бібліогр.: 20 назв. — англ. 1607-324X PACS: 05.10.-a, 05.40.a, 05.40.Fb, 07.05.Tp DOI:10.5488/CMP.9.2.367 https://nasplib.isofts.kiev.ua/handle/123456789/121323 In this work we present a model for computing the random processes in digital computers which solves the problem of periodic sequences and hidden errors produced by correlations. We show that systems with noninvertible non-linearities can produce unpredictable sequences of independent random numbers. We illustrate our results with some numerical calculations related to random walks simulations. en Інститут фізики конденсованих систем НАН України Condensed Matter Physics A recipe for an unpredictable random number generator Припис для непередбаченого генератора випадкових чисел Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	A recipe for an unpredictable random number generator
spellingShingle	A recipe for an unpredictable random number generator Garcıa-Nustes, M.A. Trujillo, L. Gonzalez, J.A.
title_short	A recipe for an unpredictable random number generator
title_full	A recipe for an unpredictable random number generator
title_fullStr	A recipe for an unpredictable random number generator
title_full_unstemmed	A recipe for an unpredictable random number generator
title_sort	recipe for an unpredictable random number generator
author	Garcıa-Nustes, M.A. Trujillo, L. Gonzalez, J.A.
author_facet	Garcıa-Nustes, M.A. Trujillo, L. Gonzalez, J.A.
publishDate	2006
language	English
container_title	Condensed Matter Physics
publisher	Інститут фізики конденсованих систем НАН України
format	Article
title_alt	Припис для непередбаченого генератора випадкових чисел
description	In this work we present a model for computing the random processes in digital computers which solves the problem of periodic sequences and hidden errors produced by correlations. We show that systems with noninvertible non-linearities can produce unpredictable sequences of independent random numbers. We illustrate our results with some numerical calculations related to random walks simulations.
issn	1607-324X
url	https://nasplib.isofts.kiev.ua/handle/123456789/121323
citation_txt	A recipe for an unpredictable random number generator / M.A. Garcıa-Nustes, L. Trujillo, J.A. Gonzalez// Condensed Matter Physics. — 2006. — Т. 9, № 2(46). — С. 367–372. — Бібліогр.: 20 назв. — англ.
work_keys_str_mv	AT garcıanustesma arecipeforanunpredictablerandomnumbergenerator AT trujillol arecipeforanunpredictablerandomnumbergenerator AT gonzalezja arecipeforanunpredictablerandomnumbergenerator AT garcıanustesma pripisdlâneperedbačenogogeneratoravipadkovihčisel AT trujillol pripisdlâneperedbačenogogeneratoravipadkovihčisel AT gonzalezja pripisdlâneperedbačenogogeneratoravipadkovihčisel AT garcıanustesma recipeforanunpredictablerandomnumbergenerator AT trujillol recipeforanunpredictablerandomnumbergenerator AT gonzalezja recipeforanunpredictablerandomnumbergenerator
first_indexed	2025-11-24T15:48:08Z
last_indexed	2025-11-24T15:48:08Z
_version_	1850473148782215168
fulltext	Condensed Matter Physics 2006, Vol. 9, No 2(46), pp. 367–372 A recipe for an unpredictable random number generator M.A.Garcı́a-Ñustes, L.Trujillo, J.A.González Centro de Fı́sica, Instituto Venezolano de Investigaciones Cientı́ficas (IVIC), A.P 21827, Caracas 1020–A, Venezuela Received February 27, 2006, in final form April 19, 2006 In this work we present a model for computing the random processes in digital computers which solves the problem of periodic sequences and hidden errors produced by correlations. We show that systems with non- invertible non-linearities can produce unpredictable sequences of independent random numbers. We illustrate our results with some numerical calculations related to random walks simulations. Key words: random number generator, independent random numbers PACS: 05.10.-a, 05.40.a, 05.40.Fb, 07.05.Tp Many challenging problems in computational physics are associated with reliable realizations of randomness (e.g. Monte Carlo simulations). In a typical 32-bit format a maximum of 232 floating point numbers can be represented. Therefore, a recursive function Xn+1 =f(Xn, Xn−1, . . . , Xn−r+1) acting on these numbers generates a sequence X0, X1, X2, . . . , XN−1 which should repeat itself. It is known that for any recursive function, a digital computer can only generate periodic sequences of numbers [1–7]. These generators are not unpredictable. Definition of truly unpredictable process: The next values are not determined by the pre- vious values. A process Xn = P (θTZn) is said to be unpredictable if for any string of values X0, X1, X2, . . . , Xm of length m + 1, generated using some θ = θ1, there are other values of θ for which function Xn = P (θTZn) generates exactly the same string of numbers X0, X1, X2, . . . , Xm, but the next value Xm+1 is different, where m is any integer. Note that this kind of process cannot be expressed as a map of type Xn+1 = f(Xn, Xn−1, . . . , Xn−r+1) [8–10]. All the known generators (in some specific physical calculations) give rise to incorrect results because they deviate from randomness [2,4,5,7]. It is trivial that any periodic process is not unpre- dictable. Suppose that mT is the period of the sequence generated. Given any string of mT values: Xs, Xs+1, . . . , XmT−1; the next value XmT is always known because the process is periodic. On the other hand, for any generator of type Xn+1 = f(Xn, Xn−1, . . . , Xn−r+1), given any string of r values: Xs, Xs+1, . . . , Xs+r−1; the next value Xs+r is always determined by the previous r values. Thus it is not unpredictable. So the subsequences must be correlated. An example of this can be found in [5], where the authors have shown that using common pseudo random number generators, the produced random walks present symmetries, meaning that the generated numbers are not independent. On the other hand, the logarithmic plot of the mean distance 〈d〉 versus the number of steps N is not a straight line (as expected theoretically, 〈d〉 ∼ N1/2) after N > 105 (in fact, it is a rapidly decaying function). Here d is defined as the end to end mean-square distance from the origin of the random walk as a function of the number of steps. Other papers on the effect of the pseudorandom number generator on random walk simulations are as follows [11–13]. In the following, we shall show that using non-invertible nonlinear functions, we can create an unpredictable random number generator which does not contain visible correlations while simu- lating a random walk with the length 109. Let us investigate the following function[8–10]: Xn = P (θ TZn), (1) c© M.A.Garcı́a-Ñustes, L.Trujillo, J.A.González 367 M.A.Garcı́a-Ñustes, L.Trujillo, J.A.González where P (t) is a periodic function, θ is a real number, T is the period of the function P (t), and Z is a noninteger real number. Let Z be a rational number expressed as Z = p/q, where p and q are relative prime numbers. Now let us define the following family of sequences X(k,m,s) n = P [ T (θ0 + qmk) ( q p )s ( p q )n] , (2) where k, m and s are non-negative integers. Parameter k distinguishes different sequences. For all sequences parametrized by k, the strings of m + 1 values Xs, Xs+1, Xs+2, . . . , Xs+m are the same. This is because X(k,m,s) n = P [ Tθ0 ( q p )s ( p q )n + Tkpn−sq(m−n+s) ] = P [ Tθ0 ( q p )s ( p q )n] for all s 6 n 6 m + s. Note that the number k p(n−s)q(m−n+s) is an integer for s 6 n 6 m + s. So we can have an infinite number of sequences that share the same string of m + 1 values. Nevertheless, the next value X (k,m,s) s+1 = P [ T θ0 ( q p )s ( p q )(s+1) + T kp(m+1) q ] is uncertain. In general X (k,m,s) s+1 can take q different values. In addition, the value X (k,m,s) s−1 , X (k,m,s) s−1 = P [ T θ0 ( q p )s ( p q )(s−1) + T kq(m+1) p ] , is also undetermined from the values of the string Xs, Xs+1, Xs+2, . . . , Xs+m. There can be p different possible values. In the case of a generic irrational Z, there are infinite possibilities for the future and for the past. From the observation of the string Xs, Xs+1, Xs+2, . . . , Xs+m, there is no method for determining the next and the previous values of the sequence. But this is not the only feature of these functions. It can be shown that there are no statistical correlations between Xm and Xn if m 6= n, and that they are also independent in the sense that their probability densities satisfy the relationship P (Xn, Xm) = P (Xn)P (Xm) [14,15]. Moreover, we shall show that, given the function (1), any string of sequences Xs, Xs+1, . . . , Xs+r constitutes a set of statistically independent random variables. Without loss of generality, we assume that P (t) has zero mean and can be expressed using the following Fourier representation P (t) = ∑ ∞ k=−∞ akeiπkt. We can calculate the r-order correlation functions [14,15]: E(Xn1 · · ·Xnr ) = ∫ X dθP (TθZn1) · · ·P (TθZnr) = ∞ ∑ k1=−∞ · · · ∞ ∑ kr=−∞ ak1 · · · akr ∫ 1 0 dθ exp {iπ(k1Z n1 + · · · + krZ nr)Tθ} = ∞ ∑ k1=−∞ · · · ∞ ∑ kr=−∞ ak1 · · · akr δ(k1Z n1 + · · · + krZ nr , 0), (3) where the coefficients ki can be different integers, and δ(n, m) = 1 if n = m or δ(n, m) = 0 if n 6= m. When all ni are even, the following equation is satisfied E(Xn1 s Xn2 s+1 · · ·Xnr s+r) = E(Xn1 s )E(Xn2 s+1) · · ·E(Xnr s+r). (4) The main problem in this equation is when one of the numbers ni is odd. In this case, the correlations E(Xn1 s Xn2 s+1 · · ·Xnr s+r) should be zero. A nonzero correlation in equation (4) exists 368 Unpredictable random number generator only for the sets (n1, n2, . . . , nr) that satisfy the equation k1Z n1 + · · · + krZ nr = 0. For a typical real number Z, this equation is never satisfied. If we use non-invertible nonlinear functions, type of (1), we can implement a Truly Random Number Generator (TRNG). In this case, we propose the following function Xn = [θsZ n] mod 1. (5) Function (5) is an example of the general case Xn = P [θTZn] studied in this paper. We have shown that the subsequences Xs, Xs+1, . . . , Xs+r constitute a set of statistically independent ran- dom variables. The particular case of function (5) is well-known to produce uniformly distributed numbers [8–10]. Now we shall formulate a central limit theorem. Using theorems proved in previous studies [14–19] and the results obtained from this paper, we obtain the following formula: If Z is a generic real number and Xn = 2(Yn − 1/2), Yn = [θZn] mod 1, then lim r→∞ P { α < X1 + X2 + · · ·Xr√ r < β } = 1√ π ∫ β α e−ξ2 dξ. (6) The Gaussian distribution of the sums is correct even for other functions Xn = P [θZn], where P (t) is periodic. This has been shown in numerical simulations [14]. The numbers Xn = [θZn] mod 1 are uniformly distributed[8–10]. We can simulate different stochastic processes (with different distributions) using different functions Xn = P [θTZn]. As ρ(Xn) = 1, ρ(Xn+1) = 1, ρ(Xn, Xn+1) = 1, it is trivial that they are independent. It is interesting to check the theoretical predictions using numerical simulations of the behavior of different stochastic processes. For instance, let us study the function Un = cos[2πθZn]. (7) All the moments and higher-order correlations can be exactly calculated [14,15]: For odd m: E(Um n ) = 0. (8) If any ni is odd, then E(Un0 s Un1 s+1 · · ·Unr s+r) = 0. (9) Suppose now that all ni are even: E(Un0 s Un1 s+1 · · ·Unr s+r) = 2−(n0+n1+···+nr) ( n0 n0 2 ) ( n1 n1 2 ) · · · ( nr nr 2 ) , (10) E(Un0 s ) = 2−n0 ( n0 n0 2 ) , (11) E(Un1 s+1) = 2−n1 ( n1 n1 2 ) , . . . , (12) E(Unr s+r) = 2−nr ( nr nr 2 ) . (13) Note that the condition for independence is satisfied E(Un0 s Un1 s+1 · · ·Unr s+r) = E(Un0 s )E(Un1 s+1) · · ·E(Unr s+r), (14) for all integers n0, n1, . . . nr. We have performed extensive numerical simulations that confirm the values of these moments and the independent conditions. An additional checking is as follows. 369 M.A.Garcı́a-Ñustes, L.Trujillo, J.A.González −1 −0.5 0 0.5 1 0 500 1000 1500 2000 2500 3000 3500 4000 4500 U n ρ( U n) −1 −0.5 0 0.5 1 0 500 1000 1500 2000 2500 3000 3500 4000 4500 U n+1 ρ( U n+ 1) (a) (b) Figure 1. Probability densities for random variables Un = cos[2πθZn] and Vn = Un+1. (a) ρ(U) = (π √ 1 − U2) −1 ; (b) ρ(V ) = (π √ 1 − V 2) −1 . Figure 2. Probability density ρ(Un, Un+1), when Un = cos[2πθZn]. Here ρ(U, V ) = (π2 � (1 − U2)(1 − V 2)) −1 . The probability density of Un is ρ(U) = (π √ 1 − U2) −1 . Define Vn = Un+1. The probability density of Vn is ρ(V ) = (π √ 1 − V 2) −1 . We have checked both theoretically and numerically that ρ(U, V ) = (π2 √ (1 − U2)(1 − V 2)) −1 , that is ρ(U, V ) = ρ(U)ρ(V ). This can be observed in figure 1 and figure 2. In order to avoid computation problems, we have used the following procedure. We change parameter θ after each set of M values of Xn, where M is the maximum number for which there are no overflow problems, such that the next value of Xn+1 is obtained with the new θ. Let us define θs = A(Cs + Xs) + 0.1, (15) where Cs is a sequence obtained using the digits of the Champernowne’s number [20] (i.e., 0.1234567891011 . . .): C0 = 0.123456 , C1 = 0.234567, C2 = 0.345678, C3 = 0.456789, C4 = 0.567891, and so on. This sequence is nonperiodic. Index s is the order number of θ, such that s = 0 corresponds to the θ used for the first set of M sequence values X1, X2, . . . , XM ; s = 1 for the second set XM+1, XM+2, . . . , X2M , and so on. X0 represents the TRNG’s seed. Using this method we have generated a very long sequence of random numbers without com- putational problems. To test function (5) as a truly random number generator, we have implemented a random walk 370 Unpredictable random number generator simulation program in C++. We have made a sampling test of a random walk with N = 109 steps with 100 realizations with different initial seeds. The mean distance 〈d〉 was being calculated every 1000 steps of the random walk. The Champernowne sequence of numbers used in the generator was produced previously by a short C++ program, who created a sequence of a maximum of 40000 Champernowne’s numbers. If a larger amount of values to Cs is necessary, it can be obtained using a segment code that has 40 thousand values already stored in Cs and mixing them, e.g. the algorithm takes the first value of the series C1, the third C3 and so on, and adds them at the end of the series, obtaining Cs+1 = C1, Cs+2 = C3,. . . ; if more values are necessary, this procedure or cycle is repeated but now skipping two values C1, C3, C5,. . . three values C1, C4, C7 and so on. In this way, we can make the Cs sequence as large as we wish. We present a logarithmic plot of the mean distance 〈d〉 versus the number of steps N with N = 109 steps with A = 6.9109366 and Z = π/2 (See figure 3). We can verify that there is no deviation from the theoretical straight line, even for N � 105 steps, which is a very good test of the reliability of the Random Number Generator used in the random walk simulations. 10 0 10 2 10 4 10 6 10 8 10 10 10 0 10 1 10 2 10 3 10 4 10 5 log(N) lo g< d> (a) 10 1 10 2 10 3 10 4 10 5 10 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 lo g< d> log (N) (b) Figure 3. Logarithmic plot of the mean distance 〈d〉 versus the number of steps N = 109 steps. (a) for generator (5); (b) the same simulation for a generator of type Xn+1 = aXn mod T . We have presented a random number generator based on the properties of non-invertible trans- formations of truncated exponential functions. The obtained random process is unpredictable in the sense that the next values are not determined by the previous values. We have applied this gen- erator to the numerical simulation of statistically independent random variables. In the simulation of a random walk with the length 109, the random process does not contain visible correlations. References 1. Ferrenberg A.M., Landau D.P., Wong Y.J., Phys. Rev. Lett., 1992, 69, 3382. 2. Grassberger P., Phys. Lett. A, 1993, 181, 43. 3. Vattulainen I., Ala-Nissila T., Kankaala K., Phys. Rev. Lett., 1994, 73, 2513. 4. D’Souza R.M., Bar-Yam Y., Kardar M., Phys. Rev. E, 1998, 57, 5044. 5. Nogués J., Costa-Krämer J.L., Rao K.V., Physica A, 1998, 250, 327. 6. L’Ecuyer P., Oper. Res., 1999, 47, 159. 7. Bauke H., Mertens S., J. Stat. Phys., 2004, 114, 1149. 8. González J.A., Reyes L.I., Suárez J.J., Guerrero L.E., Gutiérrez G., Phys. Lett. A, 2002, 295, 25. 9. González J.A., Reyes L.I., Suárez J.J., Guerrero L.E., Gutiérrez G., Physica D, 2003, 178, 26. 10. Trujillo L., Suárez J.J., González J.A., Europhys. Lett., 2004, 66, 638. 11. Grassberger P., J. Phys. A: Math. Gen., 1993, 26, 2769. 12. Shchur L.N., Heringa J.R., Blöte H.W.J., Physica A, 1997, 241, 579. 13. Shchur L.N., Comput. Phys. Comm., 1999, 121, 83. 371 M.A.Garcı́a-Ñustes, L.Trujillo, J.A.González 14. González J.A., Trujillo L., Acta Physica Pol. B, 2005, 37, 2394. 15. González J.A., Trujillo L., J. Phys. Soc. Japan, 2006, 75, 023002. 16. Kac M., Stud. Mathematica, 1936, 6 , 46. 17. Kac M., Steinhaus H., Stud. Mathematica, 1936, 6, 59. 18. Kac M., Steinhaus H., Stud. Mathematica, 1936, 6, 89. 19. Kac M., Steinhaus H., Stud. Mathematica, 1937, 7, 1. 20. Champernowne D.G., J. London Math. Soc., 1933, 8, 254. �� .�.��i�-��, �.�� !i"#, $.�.�#%��&�� '()+ ,i-./., 0()(12(3414/.5 I)1.2 )62/78.9 :713i:;()4,<7=. 1/+.)4/6 21827, >6+6/61 1020–?, 0()(12(36 @ABCDEFG 27 HIAGJG 2006 B., K GLAEAGMFGDN KCJHOPi – 19 QKiAFO 2006 B. 0 Ri5 +7S7i T. <+7<7)2UT7 T7:(34 8.<6:/78.9 <+7R(1i8 8 V.1378.9 /7T<’W(+69, X/6 8.+i=2U <+7-S3(T2 1<+.V.)().9 /7+(3XRiXT. <(+i7:.V).9 <713i:78)71(5 i <+.9786).9 <7T.37/. Y. <7/6-2UT7,Z7 1.1(T. - )(-87+7).T. )(3i)i5)71XT. T7;24 <7+7:;286. )(<(+(:S6V286)i <713i:78)71i)(-63(;).9 8.<6:/78.9 V.1(3. [6=i +(-2346. i3W1+2W41X 7SV.13())XT., <78’X-6).T. - 1.T2-3XRiUW 8.<6:/78.9 S32/6)4. \]^_`ai b]`ac: defeghijg klmhnojklp qlres, fethseufi klmhnojki qlrsh PACS: 05.10.-a, 05.40.a, 05.40.Fb, 07.05.Tp 372

A recipe for an unpredictable random number generator

Institution

Ähnliche Einträge