January 1971 - Vol. 14 No. 1
Features
Signature simulation and certain cryptographic codes
Three cyphers allegedly authored by Thomas Jefferson Beale in 1822 have been the subject of intensive study for over 100 years. Generations of cryptanalysts have expended untold man-years, thus far without success, attempting to decode them; vast armies of fortune hunters and treasure seekers have devoted Herculean labors to digging up the rolling hills of Virginia trying to locate the promised bonanza. The history of pertinent activities would fill volumes, yet serious students of cryptography have always had nagging doubts about the cyphers' authenticity. It has been alleged that the “known solution” to Cypher Number Two: 115, 73, 24, 818, 37, 52, 49, … (“I have deposited in the County of Bedford about four miles from Buford's in an excavation or vault…”) with the aid of an unsanitized version of the Declaration of Independence was merely a superb, imaginative, and grandiose hoax perpetrated ages ago for whatever reasons.
Modern computer technology could obviously perform signature analyses on the Beale cyphers and could also, in fact, simulate the process of encoding itself so as to yield new clues and deeper insights into their construction. For the benefit of the uninitiated, the encoding method used in the second cypher employs a specified document whose words are simply numbered consecutively, and first letters of these words are sought out at random to match the letters of the cleartext or message. The sequence of numbers corresponding to these matches is then written down as the final code. While primitive, the process has the advantage of relative security until the source document becomes known; at that moment the cypher can be decoded even by second graders.
The work now completed with the help of our UNIVAC 1108 includes numerous analytical studies of the Beale cyphers and various types of simulations. For example, we have turned the entire process of simulated encoding by various schemes over to the machine and analyzed the signatures of these synthetic codes; we have also encoded various messages by hand, using different texts and a variety of methods to obtain their signatures. These simulations provide convincing evidence that the signatures are both process and data dependent; they indicate also very strongly that Mr. Beale's cyphers are for real and that it is merely a matter of time before someone finds the correct source document and locates the right vault in the Commonwealth of Virginia.
Pattern width at a given angle
That the pattern feature “width as a function of angle” possesses several possible interpretations is demonstrated in this paper, which is a review of the width concept in pattern recognition and the geometrical concept itself.
The object of the work is to clarify how the word description can be made precise so that computer algorithms for feature extraction may be obtained; the focus is on theoretical subject matter. The results consist of a set-theoretic definition of width-at-angle, a theorem relating it to the pattern boundary radius vector, and descriptions of alternate widths. All widths are calculated for an illustrative example; graphical and tabular comparisons are given. Substantial variation in width-at-angle magnitude is found. The principal conclusion is that the set-theoretic width-at-angle is a useful pattern feature when it can be easily computed. Further investigation of the information contained in only part of a width function is recommended for cases where computation of width-at-angle is difficult.
The reconstruction of binary patterns from their projections
Given the horizontal and vertical projections of a finite binary pattern f, can we reconstruct the original pattern f? In this paper we give a characterization of patterns that are reconstructable from their projections. Three algorithms are developed to reconstruct both unambiguous and ambiguous patterns. It is shown that an unambiguous pattern can be perfectly reconstructed in time m × n and that a pattern similar to an ambiguous pattern can also be constructed in time m × n, where m, n are the dimensions of the pattern frame.
A language for treating geometric patterns in a two-dimensional space
In this paper CADEP, a problem-oriented language for positioning geometric patterns in a two-dimensional space, is presented.
Although the language has been specifically designed for the automatic generation of integrated circuit masks, it turns out to be well suited also for such other placement problems as architecture design, urban planning, logical and block diagram representation.
The design criteria, the structure, and the specific features of CADEP are illustrated.
Construction of rational and negative powers of a formal series
Some methods are described for the generation of fractional and negative powers of any formal series, such as Poisson series or Chebyshev series. It is shown that, with the use of the three elementary operations of addition, subtraction, and multiplication, all rational (positive and negative) powers of a series can be constructed. There are basically two approaches: the binomial theorem and the iteration methods. Both methods are described here, and the relationship between them is pointed out. Some well-known classical formulas are obtained as particular cases, and it is shown how the convergence properties of these formulas can be improved with very little additional computations. Finally, at the end of the article, some numerical experiments are described with Chebyshev series and with Fourier series.
Comments on prevention of system deadlocks
Habermann's method of deadlock prevention is discussed, where deadlock is defined as a system state from which resource allocations to certain processes are not possible. It is shown that the scheduler may introduce “artificial” deadlocks which Habermann's method does not prevent. Permanent blocking is the situation where certain processes never receive their resource requests. It is shown that deadlock prevention does not necessarily eliminate permanent blocking. A method of preventing permanent blocking is given.
A proof is given of the correctness of the algorithm “Find.” First, an informal description is given of the purpose of the program and the method used. A systematic technique is described for constructing the program proof during the process of coding it, in such a way as to prevent the intrusion of logical errors. The proof of termination is treated as a separate exercise. Finally, some conclusions relating to general programming methodology are drawn.
Further evidence for the analysis of algorithms for the zero-one programming problem
The purpose of this note is to report computational experience additional to that recently summarized by Gue et al., with two algorithms for the zero-one linear programming problem. An error in Gue's paper is corrected. The utility of one of the algorithms as a suboptimizer is indicated.
Minit algorithm for linear programming
In his Certification of Algorithm 245 [1], Ralph L. London exhibits a common confusion between an algorithm, its representation, and its implementation on a processor—a code. In the present state of the art we can attempt, in general, to prove an algorithm and to test a code. For example, London states that “… the algorithm TREESORT 3 [2] is proved to perform properly its claimed task of sorting an array M[1:n] into ascending order.” While this is true of the algorithm, it is not true of the code unless we place restrictions on the array elements. The trouble arises in this example from the finite precision of processors; the Boolean expression A ≥ B (real A, B) will usually be implemented as A - B ≥ 0, which can fail due to floating point overflow or underflow.
Comment on London’s certification of algorithms 245
In his Certification of Algorithm 245 [1], Ralph L. London exhibits a common confusion between an algorithm, its representation, and its implementation on a processor—a code. In the present state of the art we can attempt, in general, to prove an algorithm and to test a code. For example, London states that “… the algorithm TREESORT 3 [2] is proved to perform properly its claimed task of sorting an array M[1:n] into ascending order.” While this is true of the algorithm, it is not true of the code unless we place restrictions on the array elements. The trouble arises in this example from the finite precision of processors; the Boolean expression A ≥ B (real A, B) will usually be implemented as A - B ≥ 0, which can fail due to floating point overflow or underflow.
Comment on the conversion of decision tables to computer programs
In their article [2] C. R. Muthukrishnan and V. Rajaraman have developed two excellent algorithms for conversion of limited entry and mixed entry decision tables to computer programs. I must, however, take issue with their contention that “…in general, the conditions may be very complicated and a compile time analysis will not be possible.” They then cite the following example in Figure 1(b).
