W. H. Payne – Communications of the ACM

Research and Advances Apr 1 1978

Orderly enumeration of nonsingular binary matrices applied to text encryption

Nonsingular binary matrices of order N, i.e., nonsingular over the field {0, 1}, and an initial segment of the natural numbers are placed in one-to-one correspondence. Each natural number corresponds to two intermediate vectors. These vectors are mapped into a nonsingular binary matrix. Examples of complete enumeration of all 2 × 2 and 3 × 3 nonsingular binary matrices were produced by mapping the intermediate vectors to the matrices. The mapping has application to the Vernam encipherment method using pseudorandom number sequences. A bit string formed from bytes of text of a data encryption key can be used as a representation of a natural number. This natural number is transformed to a nonsingular binary matrix. Key leverage is obtained by using the matrix as a “seed” in a shift register sequence pseudorandom number generator.

Computing Applications

Author Archives

Research and Advances Mar 1 1973

Graduate education: the Ph.D. glut

[Two years ago the author was elected by the Washington State University faculty to a three-year term as a faculty representative to a Graduate Studies Committee charged “to examine and evaluate proposed changes in the policy of the Graduate School.” After his experiences and considerable study, the author says he feels compelled to express his observations and opinions to his fellow members of the Association for Computing Machinery.]

Research and Advances Jan 1 1970

Fortran Tausworthe pseudorandom number generator

Intermediate computations in an “Extremely Portable Random Number Generator” by J. B. Kruskal [Comm. ACM 12, 2 (Feb. 1969), 93-94] exceed 15 bits plus sign. This is a severe limitation since the majority of small computers uses a 16 bit (15 bits plus sign) word or less. ASA standard FORTRAN compilers for these machines are readily available. Fortunately, a linearly recurring sequence generator [2] can be written in somewhat “portable” ASA Standard FORTRAN which will produce maximum length [2** (word size of computer - 1) -1] pseudorandom numbers for common 12, 16, 18, 24, and 32 bit computers, to mention only a few. Following Kendall's algorithm and notation presented by Whittlesey for a p-bit computer: p = 12, N = 11, M = 2; p = 16, N = 15, M = 1, 4, or 7; p = 18, N = 17, M = 3, 5, or 6; p = 24, N = 23, M = 5 or 9; and p = 32, N = 31, M = 3, 6, 7, or 13.

Research and Advances Feb 1 1969

Coding the Lehmer pseudo-random number generator

An algorithm and coding technique is presented for quick evaluation of the Lehmer pseudo-random number generator modulo 2 ** 31 - 1, a prime Mersenne number which produces 2 ** 31 - 2 numbers, on a p-bit (greater than 31) computer. The computation method is extendible to limited problems in modular arithmetic. Prime factorization for 2 ** 61 - 2 and a primitive root for 2 ** 61 - 1, the next largest prime Mersenne number, are given for possible construction of a pseudo-random number generator of increased cycle length.

Computing Applications

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved