Quasi-Random Number Sequences from a Long-Period TLP Generator with Remarks on Application to Cryptography

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quasi-Random Number Sequences from a Long-Period TLP Generator with Remarks on Application to Cryptography

Full text

Pdf (1.18 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 11 , Issue 4 (December 1979) table of contents

Pages: 357 - 370

Year of Publication: 1979

ISSN:0360-0300

Authors

Herbert S. Bright	Computation Planning, Inc, 7840 Aberdeen Road, Bethesda, Maryland
Richard L. Enison	COMPLAN Fellow, Department of Mathematics, University of California, Berkeley, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 38, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/356789.356795 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BRIG76	BRIGHT, H. S, AND ENISON, R. L "Cryptography using modular software elements," in Proc. AFIPS NCC'76, Vo\|. 45, AFIPS Press, Arhngton, Va., pp. 113- 123.
	BRIG77	BRIGHT, H.S. "Cryptanalytic attack and defense," Cryptolog~a 1, 4 (Oct. 1977), 366-370 (text of COMPLAN TN-913-14, Sept. 25, 1977 version).
	BRIG79	BRIGHT, H. S "High-speed indirect cryption," to appear in Cryptologta (text of COMPLAN TN-913-35, Oct. 5, 1979 version).
	CARR70	CARROLL, J. M, AND MCLELLAND, P. M. "Fast infinite-key privacy transformation for resource-sharing systems," in Proc. 1970 AFIPS Fall Jt. Computer Conf., Vol. 87, AFIPS Press, Arlington, Va, pp. 223-230.
	CHAI74	Gregory J. Chaitin, Information-Theoretic Limitations of Formal Systems, Journal of the ACM (JACM), v.21 n.3, p.403-424, July 1974 [doi>10.1145/321832.321839]
	COMP76	COMPLAN. TLP sequence as key stream for Vernam cryptlon, Tech. Note TN-913-8d, Aug. 26, 1976.
	COMP77a	COMPLAN. c r y p t o p a k@ software package technwal description, March 17, 1977 version (references a i fa b i t@ TD, April 13, 1976 version).
	COMP77b	COMPLAN. One.way keyed and keyless ctphers; nonreproduc~ble cipher, Tech. Note TN-913-24, Feb. 28, 1977.
	COMP78	COMPLAN Some considerations in the design and implementations of the QIK- CRYPT@ algorithm, Tech. Note TN-913- 33, July 28, 1978.
	COOL65	COOLEY, J W., AND TUKE~, J.W. "An algorithm for the machine calculation of complex Fourier series," Math Comput. 19 (1965), 297-301.
	COVE60	R. R. Coveyou, Serial Correlation in the Generation of Pseudo-Random Numbers, Journal of the ACM (JACM), v.7 n.1, p.72-74, Jan. 1960 [doi>10.1145/321008.321018]
	COVE67	R. R. Coveyou , R. D. Macpherson, Fourier Analysis of Uniform Random Number Generators, Journal of the ACM (JACM), v.14 n.1, p.100-119, Jan. 1967 [doi>10.1145/321371.321379]
	ENIS76	ENISON, R. L., AND BRIGHT, H. S. "Preliminary statistical testing of a 64-bit Tausworthe-Lewis-Payne quaslrandom number generator of Mersenne exponent degree," Proc. 9th Interface Syrup Computer Sctence and Statistics, David C. Hoaghn and Roy E Welsch, Eds, Prindle, Weber and Schmidt, Boston, 1976, pp 208-211.
	GAIT77a	GAIT, J "A new nonhnear pseudorandora number generator," IEEE Trans. Soflw. Eng. SE-3, 5 (Sept. 1977), 359-363.
	GAIT77b	GAIT, J. Nat. Bur. Stand., personal communication, Feb. 28, 1977.
	GREE59	Bert F. Green, Jr. , J. E. Keith Smith , Laura Klem, Empirical Tests of an Additive Random Number Generator, Journal of the ACM (JACM), v.6 n.4, p.527-537, Oct. 1959 [doi>10.1145/320998.321006]
	GREE61	GREE~S~RG~R, M. "An a priori determination of serial correlation in computer generated random numbers," Math. Cornput. 15 (1961), 383-389.
	GRUE51	GRUENBERGER, F., ANY MARK, A M. "The d2 test for random digits," MTAC 5 (1951), 109-110
	INGE76	INGEr~AaSSON, i "Analysis of secret functions with application to computer cryptography," in Proc. AFIPS NCC '76, Vol. 45, AFIPS Press, Arlington, Va., pp. 125-127.
	JUNC53	JUNCOSA, M. L. Random number generation on the BRL h~gh speed computing machine, BRL Rep. 855, 1953. We also reference telephone and written discusslons of congruentlal generators during Dec. 1975 and Feb. 1976.
	KNUT65	KNUTH, D "Construction of a random sequence," BIT 5 (1965), 246-250.
	KNUT69	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	LEHM51	LEHMER, D.H. "Mathematical methods in large-scale computing units," Ann. Comput. Lab. Harvard U. 26 (1951), 141- 146; see also LEHM76.
	LEHM76	LEHMER, D. H Private communication, Feb. 12, 1976. Prof. Lehmer also showed analytically that the maximum distance one has been from the starting point is, for a congruential generator, independent of the number of steps, but increases monotone with period, and that for a Brownian motion the distance increases monotone with number of steps. He suggested that, m practice, such testmg should examine a small part of the path of a sequence of long period. We hope that he will be able to perform experiments of this type using a polyprocessor machine having the enormous power that will be required for practical results
	LEWI73a	LEWIS, P. A. W., GOODMAN, A. S, AND MILLER, J. M "A pseudo-random number generator for the system/360," IBM Syst. J. 8 (1973), 456-468.
	LEWI73b	T. G. Lewis , W. H. Payne, Generalized Feedback Shift Register Pseudorandom Number Algorithm, Journal of the ACM (JACM), v.20 n.3, p.456-468, July 1973 [doi>10.1145/321765.321777]
	LIND70	LINDGREN, B. W., AND MCELRATH, G. W. Introductmn to Probab~hty and Stat~stws, 3rd. ed., McMillan, New York, 1970, p 170.
	MACL65	M. Donald MacLaren , George Marsaglia, Uniform Random Number Generators, Journal of the ACM (JACM), v.12 n.1, p.83-89, Jan. 1965 [doi>10.1145/321250.321257]
	MARS68	MARSAGLIA, G. "Random numbers fall mainly in the planes," Proc. Nat. Acad. Sct. 6 (1968), 25-28.
	MART66	MARTIN-LOF, P. "The definition of random sequences," Inf Control 9 (1966), 602-619.
	MOSH54	Jack Moshman, The Generation of Pseudo-Random Numbers on a Decimal Calculator, Journal of the ACM (JACM), v.1 n.2, p.88-91, April 1954 [doi>10.1145/320772.320775]
	NBS77	Data encryptmn standard, FIPS Publ. 46, Jan 1977, pp. 7-18.
	SHAN49	SHANNON, C.E. "Communication theory of secrecy systems," Bell Syst Tech. J 10 (1949), 656-715.
	TAUS65	TAUSWORTHE, R.C. "Random numbers generated by linear recurrence modulo two," Math Comput. 19 (1965), 201-209. We also reference telephone discussions and correspondence on primitive trinomials Jan. 9 and Jan. 12, 1976.
	THOM01	THOMAS, W. I. Am J. Socml 6 (1901), 750-763.
	TOOT71	J. P. R. Tootill , W. D. Robinson , A. G. Adams, The Runs Up-and-Down Performance of Tausworthe Pseudo-Random Number Generators, Journal of the ACM (JACM), v.18 n.3, p.381-399, July 1971 [doi>10.1145/321650.321655]
	TOOT73	J. P. R. Tootill , W. D. Robinson , D. J. Eagle, An Asymptotically Random Tausworthe Sequence, Journal of the ACM (JACM), v.20 n.3, p.469-481, July 1973 [doi>10.1145/321765.321778]
	TUCK71	TUCKERMAN, B. "The 24th Mersenne prime," Proc Nat. Acad. Sct USA 68, 10 (Oct. 1971), 2319-2320 On the next three Mersenne primes, see news notes in Sct. Am. 240, 1 (Jan. 1979) 85, 88 (25th); 241, 3 (Sept. 1979), 32 (26th and 27th).
	VERN26	VERNAM, G S. "Cipher printing telegraph systems for secret wtre and radio telegraphic communications," J. AIEE 45 (Jan. 1926), 109-115.
	WHIT68	John RB Whittlesey, A comparison of the correlational behavior of random number generators for the IBM 360, Communications of the ACM, v.11 n.9, p.641-644, Sept. 1968 [doi>10.1145/364063.364095]
	ZIER69	ZIERLER, N. "Primitive trinomials whose degree ts a Mersenne exponent," Inf. Control 15 (1969), 67-69; see also ZIERLER, N., AND J. BRILLHART, "On primitive tnnomials (rood 2)," pt. 1, Inf. Control 13 (1968), 541-554, pt. 2, Inf Control 14 (1969), 566- 569

CITED BY 6

	Bruce Jay Collings , G. Barry Hembree, Initializing generalized feedback shift register pseudorandom number generators, Journal of the ACM (JACM), v.33 n.4, p.706-711, Oct. 1986
	M. Fushimi , S. Tezuka, The k-distribution of generalized feedback shift register pseudorandom numbers, Communications of the ACM, v.26 n.7, p.516-523, July 1983
	Brad C. Johnson, Radix-b extensions to some common empirical tests for pseudorandom number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.6 n.4, p.261-273, Oct. 1996
	Salvatore Filippone , Paolo Santangelo , Marcello Vitaletti, A vectorized long-period shift-register random number generator, Proceedings of the 1990 conference on Supercomputing, p.676-684, October 1990, New York, New York, United States
	Daniel Guinier, A fast and portable uniform quasi-random generator of very large period based ona generalized multi-moduli congruential method, ACM SIGSIM Simulation Digest, v.19 n.3, p.27-33, Sept. 1988
	D. Guinier, A fast uniform astronomical random number generator, ACM SIGSAC Review, v.7 n.1, p.1-12, Spring 1989