300 Chapter 7.Random Numbers random floating-point number.They are not very random for that purpose;see Knuth [1].Examples of acceptable uses of these random bits are:(i)multiplying a signal randomly by +1 at a rapid"chip rate,"so as to spread its spectrum uniformly (but recoverably)across some desired bandpass,or (ii)Monte Carlo exploration of a binary tree,where decisions as to whether to branch left or right are to be made randomly. Now we do not want you to go through life thinking that there is something special about the primitive polynomial of degree 18 used in the above examples. (We chose 18 because 218 is small enough for you to verify our claims directly by numerical experiment.)The accompanying table [2]lists one primitive polynomial 81 for each degree up to 100.(In fact there exist many such for each degree.For example,see $7.7 for a complete table up to degree 10.) CITED REFERENCES AND FURTHER READING ICAL Knuth,D.E.1981,Seminumerical Algorithms,2nd ed.,vol.2 of The Art of Computer Programming (Reading,MA:Addison-Wesley).pp.29ff.[1] Horowitz,P.,and Hill,W.1989,The Art of Electronics,2nd ed.(Cambridge:Cambridge University RECIPES Press),5s9.32-9.37. Tausworthe,R.C.1965,Mathematics of Computation,vol.19,pp.201-209. Watson,E.J.1962,Mathematics of Computation,vol.16,pp.368-369.[2] Press. 7.5 Random Sequences Based on Data Encryption SCIENTIFIC to dir In Numerical Recipes'first edition,we described how to use the Data Encryption Standard (DES)[1-3]for the generation of random numbers.Unfortunately,when implemented in software in a high-level language like C,DES is very slow,so excruciatingly slow,in fact,that our previous implementation can be viewed as more mischievous than useful.Here we give 。a a much faster and simpler algorithm which,though it may not be secure in the cryptographic sense,generates about equally good random numbers. DES,like its progenitor cryptographic system LUCIFER,is a so-called"block product cipher"[4].It acts on 64 bits of input by iteratively applying (16 times,in fact)a kind of highly Fuurggoglrion Numerical Recipes 10621 43106 nonlinear bit-mixing function.Figure 7.5.1 shows the flow of information in DES during this mixing.The function g,which takes 32-bits into 32-bits,is called the"cipher function." Meyer and Matyas [4]discuss the importance of the cipher function being nonlinear,as well (outside as other design criteria. DES constructs its cipher function g from an intricate set of bit permutations and table North Software. lookups acting on short sequences of consecutive bits.Apparently,this function was chosen to be particularly strong cryptographically (or conceivably as some critics contend,to have an exquisitely subtle cryptographic flaw!).For our purposes,a different function g that can be rapidly computed in a high-level computer language is preferable.Such a function may weaken the algorithm cryptographically.Our purposes are not,however,cryptographic:We want to find the fastest g,and smallest number of iterations of the mixing procedure in Figure 7.5.1,such that our output random sequence passes the standard tests that are customarily applied to random number generators.The resulting algorithm will not be DES,but rather a kind of "pseudo-DES,"better suited to the purpose at hand. Following the criterion,mentioned above,that g should be nonlinear,we must give the integer multiply operation a prominent place in g.Because 64-bit registers are not generally accessible in high-level languages,we must confine ourselves to multiplying 16-bit operands300 Chapter 7. Random Numbers Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). random floating-point number. They are not very random for that purpose; see Knuth [1]. Examples of acceptable uses of these random bits are: (i) multiplying a signal randomly by ±1 at a rapid “chip rate,” so as to spread its spectrum uniformly (but recoverably) across some desired bandpass, or (ii) Monte Carlo exploration of a binary tree, where decisions as to whether to branch left or right are to be made randomly. Now we do not want you to go through life thinking that there is something special about the primitive polynomial of degree 18 used in the above examples. (We chose 18 because 218 is small enough for you to verify our claims directly by numerical experiment.) The accompanying table [2] lists one primitive polynomial for each degree up to 100. (In fact there exist many such for each degree. For example, see §7.7 for a complete table up to degree 10.) CITED REFERENCES AND FURTHER READING: Knuth, D.E. 1981, Seminumerical Algorithms, 2nd ed., vol. 2 of The Art of Computer Programming (Reading, MA: Addison-Wesley), pp. 29ff. [1] Horowitz, P., and Hill, W. 1989, The Art of Electronics, 2nd ed. (Cambridge: Cambridge University Press), §§9.32–9.37. Tausworthe, R.C. 1965, Mathematics of Computation, vol. 19, pp. 201–209. Watson, E.J. 1962, Mathematics of Computation, vol. 16, pp. 368–369. [2] 7.5 Random Sequences Based on Data Encryption InNumerical Recipes’ first edition, we described how to use the Data Encryption Standard (DES) [1-3] for the generation of random numbers. Unfortunately, when implemented in software in a high-level language like C, DES is very slow, so excruciatingly slow, in fact, that our previous implementation can be viewed as more mischievous than useful. Here we give a much faster and simpler algorithm which, though it may not be secure in the cryptographic sense, generates about equally good random numbers. DES, like its progenitor cryptographic system LUCIFER, is a so-called “block product cipher” [4]. It acts on 64 bits of input by iteratively applying (16 times, in fact) a kind of highly nonlinear bit-mixing function. Figure 7.5.1 shows the flow of information in DES during this mixing. The function g, which takes 32-bits into 32-bits, is called the “cipher function.” Meyer and Matyas [4] discuss the importance of the cipher function being nonlinear, as well as other design criteria. DES constructs its cipher function g from an intricate set of bit permutations and table lookups acting on short sequences of consecutive bits. Apparently, this function was chosen to be particularly strong cryptographically (or conceivably as some critics contend, to have an exquisitely subtle cryptographic flaw!). For our purposes, a different function g that can be rapidly computed in a high-level computer language is preferable. Such a function may weaken the algorithm cryptographically. Our purposes are not, however, cryptographic: We want to find the fastest g, and smallest number of iterations of the mixing procedure in Figure 7.5.1, such that our output random sequence passes the standard tests that are customarily applied to random number generators. The resulting algorithm will not be DES, but rather a kind of “pseudo-DES,” better suited to the purpose at hand. Following the criterion, mentioned above, that g should be nonlinear, we must give the integer multiply operation a prominent place in g. Because 64-bit registers are not generally accessible in high-level languages, we must confine ourselves to multiplying 16-bit operands