Daily Archives: 2012/06/09

Lester Hill’s “The checking of the accuracy …”, part 7

Posted on by

Backstory: Lester Saunders Hill wrote unpublished notes, about 40 pages long, probably in the mid- to late 1920s. They were titled “The checking of the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields”. In the 1960s this manuscript was given to David Kahn by Hill’s widow. The notes were typewritten, but mathematical symbols, tables, insertions, and some footnotes were often handwritten. I thank Chris Christensen, the National Cryptologic Museum, and NSA’s David Kahn Collection, for their help in obtaining these notes. Many thanks also to Rene Stein of the NSA Cryptologic Museum library and David Kahn for permission to publish this transcription. Comments by transcriber will look his this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the seventh section of his paper. I hope to post more later. (Part 6 is here.)


Section 7: The general form of reference matrix

Let a_1, a_2, \dots a_n be n different elements of our finite field F, and let a_i be different from the zero element of F. Then we shall emply a reference matrix of the form

Q = \left( \begin{array}{cccc} a_1 & a_2 & \dots & a_{n} \\ a_1^2 & a_2^2 & \dots & a_{n}^2 \\ \vdots & & & \vdots \\ a_1^q & a_2^q & \dots & a_{n}^q \\ \end{array} \right)

or of the form

Q' = \left( \begin{array}{cccc} 1 & 1 & \dots & 1 \\ a_1 & a_2 & \dots & a_{n} \\ a_1^2 & a_2^2 & \dots & a_{n}^2 \\ \vdots & & & \vdots \\ a_1^{q-1} & a_2^{q-1} & \dots & a_{n}^{q-1} \\ \end{array} \right) \, .

The actual procedure involved, and the real equivalence for checking purposes, of Q and Q', will presently be illustrated. We note here merely that each of the matrices Q, Q' is of index q. Let us examine Q'. A similar argument will be applicable to Q.

Suppose, for argument, that Q' contains a vanishing q-rowed determinant. Without loss of generality, we suppose that it is

Q' = \left| \begin{array}{cccc} 1 & 1 & \dots & 1 \\ a_1 & a_2 & \dots & a_{q} \\ a_1^2 & a_2^2 & \dots & a_{q}^2 \\ \vdots & & & \vdots \\ a_1^{q-1} & a_2^{q-1} & \dots & a_{q}^{q-1} \\ \end{array} \right| \, .
Since this determinant is equal to zero, Lemma 4 guarantees the existence, in our field F, of the elements

\lambda_1, \lambda_2, \dots \lambda_q,

not all equal to zero, for which we may write

\lambda_1 + \lambda_2 a_i +\lambda_3 a_i^2 + \dots + \lambda_q a_q^{q-1} = 0,
(i=1,2, \dots, q). The a_i being, as assumed, all different, this implies that the equation

\lambda_1 + \lambda_2 x +\lambda_3 x^2 + \dots + \lambda_q x^{q-1} = 0,

has q different roots in F, an implication which contradicts Lemma 5.

Thus Q' contains no vanishing q-rowed determinant, and if of index q. In the same way, Q may be shown to be of index q. But unless these matrices are constructed with care, they will, of course, generally contain vanishing determinants of various orders less than q. We defer for the moment the further consideration of this matter.

Lester Hill’s “The checking of the accuracy …”, part 6

Posted on by

Backstory: Lester Saunders Hill wrote unpublished notes, about 40 pages long, probably in the mid- to late 1920s. They were titled “The checking of the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields”. In the 1960s this manuscript was given to David Kahn by Hill’s widow. The notes were typewritten, but mathematical symbols, tables, insertions, and some footnotes were often handwritten. The manuscript is being LaTeXed “as we speak”. I thank Chris Christensen, the National Cryptologic Museum, and NSA’s David Kahn Collection, for their help in obtaining these notes. Many thanks also to Rene Stein of the NSA Cryptologic Museum library and David Kahn for permission to publish this transcription. Comments by transcriber will look his this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the sixth section of his paper. I hope to post more later. (Part 5 is here.)


Section 6: Arbitrary distrbution of errors affecting the f_i and the c_j

It is highly desirable, although not strictly necessary, to fashion the reference matrix Q in such a manner that every determinant contained in it, of every order, be different from zero.

Reference matrices of a practical type, and without a vanishing determinant of any order, may be construted in certain finite fields F by very direct methods which can be more easily illustrated than described. It will be expedient at this poin, even at the expense of breaking the continuity of our discussion, to introduce concrete examples of operations in finite fields, and to show how reference matrices be conveniently set up in particular cases. The desirability of contriving that such matrices contain no vanishing determinant can then be brought out more effectively. The examination of arbitrary distributions of errors among the n+q elements of a telegraphic sequence

f_1, f_2, \dots, f_n, c_1, c_2, \dots, c_q

can be deferred, therefore, until later.

But, before going into details, we will describe the general form of reference matrix to be employed in all cases.

Lester Hill’s “The checking of the accuracy …”, part 5

Posted on by

Backstory: Lester Saunders Hill wrote unpublished notes, about 40 pages long, probably in the mid- to late 1920s. They were titled “The checking of the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields”. In the 1960s this manuscript was given to David Kahn by Hill’s widow. The notes were typewritten, but mathematical symbols, tables, insertions, and some footnotes were often handwritten. The manuscript is being LaTeXed “as we speak”. I thank Chris Christensen, the National Cryptologic Museum, and NSA’s David Kahn Collection, for their help in obtaining these notes. Many thanks also to Rene Stein of the NSA Cryptologic Museum library and David Kahn for permission to publish this transcription. Comments by transcriber will look his this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the fifth section of his paper. I hope to post more later. (Part 4 is here.)


Section 5: The error distribution with at least q errors \epsilon_i

Let the sequence (footnote: Arbitrary error distributions will be considered later. Cf. sections 15-18.)

f_1, f_2, \dots, f_n,\ c_1, c_2, \dots, c_q
be transmitted in the form

f_1', f_2', \dots, f_n',\ c_1', c_2', \dots, c_q' \, ,
containing t\geq q errors which affect the f_i, and h\geq 0 errors which affect the c_j.

Let t=q+s. Then, to avoid discussing again the case already considered, we assume that at least one of the two integers s, h
is greater than 0.

Let the errors among the c_j be \delta_{j_1}, \delta_{j_2}, \dots , \delta_{j_h}, affecting the c_{j_1}, c_{j_2}, \dots , c_{j_h}. Without loss in generality, we may assume that the t errors affecting the f_i are \epsilon_1, \epsilon_2, \dots, \epsilon_t, so that the first t of the f_i are transmitted in error.

Suppose that the mutilated sequence is in full check. Then:

\sum_{i=1}^t k_{ji}(f_i+\epsilon_i)+\sum_{i=t+1}^n k_{ji}f_i =c_j+\delta_j

or

\sum_{i=1}^n k_{ji}f_i+\sum_{i=1}^t k_{ji}\epsilon_i =c_j+\delta_j

whence

\sum_{i=1}^t k_{ji}\epsilon_i=\delta_j

where j=1,2,\dots, q and where \delta_j in c_j and may, of course, be
equal to 0.

It follows that

\sum_{i=1}^q k_{ji}\epsilon_i = \delta_j - \sum_{i=1}^t k_{ji}\epsilon_i = b_j = \phi_j(\epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_j),
where j=1,2,\dots, q and where \phi_j denotes a polynomial in the errors \epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_j.

The index of the reference matrix being q, the determinant

\left| \begin{array}{cccc} k_{11} & k_{12} & \dots & k_{1n} \\ k_{21} & k_{22} & \dots & k_{2n} \\ \vdots & & & \vdots \\ k_{q1} & k_{q2} & \dots & k_{qn} \\ \end{array} \right|

of the systems of equations

\sum_{i=1}^q k_{ji}\epsilon_i = b_j \ \ \ \ \ \ \ \ \ \ (j=1,2,\dots, q)

is not zero. Hence if all the $b_j$ are equal to zero, Lemma 1 demands that all the \epsilon_i, for i=1, 2, \dots, q, be equal to zero, contrary to hypothesis.

If at least one of the b_j is different from 0, Lemma 3 shows that \epsilon_{1}, \epsilon_{2}, \dots , \epsilon_q are uniquely determined as functions of the b_j, and therefore as functions of \epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_1, \delta_2, \dots, \delta_q:

\epsilon_i = \xi_i (\epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_1, \delta_2, \dots, \delta_q),\ \ \ \ \ \ \ \ \ \ (j=1,2,\dots, q)

the functions \xi_i being, of course, rational functions. But, by assumption, all of the $\delta_j$, except \delta_{j_1}, \dots, \delta_{j_h}, vanish. Hence \epsilon_i (i=1,2,\dots, q) is a rational function of \epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_{j_1}, \delta_{j_2}, \dots, \delta_{j_h}.

We conclude that if the mutilated message, containing t+h errors, is to check up, so that the presence of error can escape detection, q of the errors must be carefully adjusted as rational functions of the remaining t+h-q errors.

It is easy to measure the chance that mere accidents of erroneous telegraphic transmittal might effect this adjustment. Let \Gamma denote the total number of elements in the finite algebraic field F which we are dealing. When an error is made in transmitting a sequence of elements of F, the error may evidently have any one of \Gamma -1 values — an error with the value 0 being no real error at all. It is therefore clear that our set of t+h errors will enjoy only 1 chance in (\Gamma -1)^q of being accidentally adjusted so as to escape detection.


When t=q+s errors occur among the f_i and h errors occur among the c_j in the transmittal of the sequence f_1, f_2, \dots, f_n,\ c_1, c_2, \dots, c_q, the errors being all of accidental telegraphic origin, the presence of error will infallibly be disclosed if h=s=0; and will enjoy a 1-in-(\Gamma -1)^q of escaping disclosure if either of the two integers h, s is greater than 0.

This statement summarizes the results of the present section and those of section 4.

Lester Hill’s “The checking of the accuracy …”, part 4

Posted on by

Backstory: Lester Saunders Hill wrote unpublished notes, about 40 pages long, probably in the mid- to late 1920s. They were titled “The checking of the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields”. In the 1960s this manuscript was given to David Kahn by Hill’s widow. The notes were typewritten, but mathematical symbols, tables, insertions, and some footnotes were often handwritten. The manuscript is being LaTeXed “as we speak”. I thank Chris Christensen, the National Cryptologic Museum, and NSA’s David Kahn Collection, for their help in obtaining these notes. Many thanks also to Rene Stein of the NSA Cryptologic Museum library and David Kahn for permission to publish this transcription. Comments by transcriber will look his this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the fourth section of his paper. I hope to post more later. (Part 3 is here.)


Section 4: Index of the reference matrix Q

There will be considerable advantage in employing a reference matrix Q of index q.

Consider the sequence f_1, f_2, \dots, f_n, c_1, c_2, \dots, c_q which is to be transmitted.
Errors may be made in transmittal, and the sequence may come through in the form

f_1', f_2', \dots, f_n', c_1', c_2', \dots, c_q'\, ,

where f_i'=f_i+\epsilon_i, c_j' = c_j + \delta_j, where i = 1, 2, \dots, n, j = 1, 2, \dots, q, the errors \epsilon_i and \delta_j being, of course, elements of the finite field F. If f_i (resp., c_j) is correctly transmitted then the error \epsilon_i (resp., c_j) vanishes, and f_i'=f_i (resp., c_j'=c_j).

Let us consider what happens when out sequence is mutilated to the extent of q errors, all of which affect the f_i (the c_j being supposed correctly transmitted).

There is no real loss of generality if we assume that the errors affect the first q of the
f_i, the errors being \epsilon_1, \epsilon_2, \dots, \epsilon_q. Since the c_j have been correctly transmitted, the mutilated message can not be in check unless

c_j = \sum_{i=1}^q k_{ji}(f_i+\epsilon_i) +\sum_{i=q+1}^n k_{ji}f_i =\sum_{i=1}^n k_{ji}f_i + \sum_{i=1}^q k_{ji}\epsilon_i.

But we recall that, by definition, c_j =\sum_{i=1}^n k_{ji}f_i. Hence the message will fail to check, and the presence of error will be disclosed, unless the q errors \epsilon_i satisfy the system of equations

\sum_{i=1}^q k_{ji}\epsilon_i = 0

for j = 1, 2, \dots, q, of which the determinant is

\Delta = \begin{array}{|cccc|} k_{11} & k_{12} & \dots & k_{1q} \\ k_{21} & k_{22} & \dots & k_{2q} \\ \vdots & & & \vdots \\ k_{q1} & k_{q2} & \dots & k_{qq} \\ \end{array} \, . \ \ \ \ \ \ \ \ (S)

But our matrix is supposed to be of index q, so that $\Delta \not=0$. It follows, by Lemma 1, that the system (S) has no solution other than \epsilon_i=0, for i=1,2,\dots, q. Hence q errors, confined to the f_i, can not escape disclosure if the reference matrix Q is of index q. By the same argument, applied a fortiori, a set of less than q errors, confined to the f_i, will certainly be disclosed when Q is of index q.

If the reference matrix Q is of index q, we can make the following statement:


Whenever the sequence f_1, f_2, \dots, f_n, c_1, c_2, \dots, c_q is transmitted with errors not affecting the c_i, and not more than q in number, the presence of error will infallibly be disclosed.

We shall hereafter understand that Q is of index q.