April 1978 - Vol. 21 No. 4
Features
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.
A technique for isolating differences between files
A simple algorithm is described for isolating the differences between two files. One application is the comparing of two versions of a source program or other file in order to display all differences. The algorithm isolates differences in a way that corresponds closely to our intuitive notion of difference, is easy to implement, and is computationally efficient, with time linear in the file length. For most applications the algorithm isolates differences similar to those isolated by the longest common subsequence. Another application of this algorithm merges files containing independently generated changes into a single file. The algorithm can also be used to generate efficient encodings of a file in the form of the differences between itself and a given “datum” file, permitting reconstruction of the original file from the diference and datum files.
Optimal conversion of extended-entry decision tables with general cost criteria
A general dynamic programming algorithm for converting limited, extended, or mixed entry decision tables to optimal decision trees is presented which can take into account rule frequencies or probabilities, minimum time and/or space cost criteria, common action sets, compressed rules and ELSE rules, sequencing constraints on condition tests, excludable combinations of conditions, certain ambiguities, and interrupted rule masking.
List processing in real time on a serial computer
A real-time list processing system is one in which the time required by the elementary list operations (e.g. CONS, CAR, CDR, RPLACA, RPLACD, EQ, and ATOM in LISP) is bounded by a (small) constant. Classical implementations of list processing systems lack this property because allocating a list cell from the heap may cause a garbage collection, which process requires time proportional to the heap size to finish. A real-time list processing system is presented which continuously reclaims garbage, including directed cycles, while linearizing and compacting the accessible cells into contiguous locations to avoid fragmenting the free storage pool. The program is small and requires no time-sharing interrupts, making it suitable for microcode. Finally, the system requires the same average time, and not more than twice the space, of a classical implementation, and those space requirements can be reduced to approximately classical proportions by compact list representation. Arrays of different sizes, a program stack, and hash linking are simple extensions to our system, and reference counting is found to be inferior for many applications.
Secure communications over insecure channels
According to traditional conceptions of cryptographic security, it is necessary to transmit a key, by secret means, before encrypted massages can be sent securely. This paper shows that it is possible to select a key over open communications channels in such a fashion that communications security can be maintained. A method is described which forces any enemy to expend an amount of work which increases as the square of the work required of the two communicants to select the key. The method provides a logically new kind of protection against the passive eavesdropper. It suggests that further research on this topic will be highly rewarding, both in a theoretical and a practical sense.
Assembling code for machines with span-dependent instructions
Many modern computers contain instructions whose lengths depend on the distance from a given instance of such an instruction to the operand of that instruction. This paper considers the problem of minimizing the lengths of programs for such machines. An efficient solution is presented for the case in which the operand of every such “span-dependent” instruction is either a label or an assembly-time expression of a certain restricted form. If this restriction is relaxed by allowing these operands to be more general assembly-time expressions, then the problem is shown to be NP-complete.
A data structure for manipulating priority queues
A data structure is described which can be used for representing a collection of priority queues. The primitive operations are insertion, deletion, union, update, and search for an item of earliest priority.
Economical encoding of commas between strings
A method for insertion of delimiters between strings without using new symbols is presented. As the lengths of the strings increase, the extra cost, in terms of prolongation, becomes vanishingly small compared to the lengths of the strings.
Generating beta variates with nonintegral shape parameters
A new rejection method is described for generating beta variates. The method is compared with previously published methods both theoretically and through computer timings. It is suggested that the method has advantages in both speed and programming simplicity over previous methods, especially for “difficult” combinations of parameter values.
