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

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 like this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the 13th section of his paper. I hope to post more later. (Part 12 is here.)


Reference matrices and table

We now turn our attention to the construction of reference matrices for checking in the field F_{101}. Our object is merely to give an account of problems arising. Hence the purposes of this paper will be served if we choose small illustrative matrices.

With

a_1 = 3, \ a_2 = 4, \ a_3 = 5, \ a_4 = 6, \ a_5 = 8, \ a_6 = 25, \ a_7 = 35, \ a_8 = 15, \ a_9 = 42, \ a_{10} = 1,

consider the reference matrix:

A = \left( \begin{array}{cccc} a_1 & a_2 & \dots & a_{10} \\ a_1^2 & a_2^2 & \dots & a_{10}^2 \\ \vdots & & & \vdots \\ a_1^5 & a_2^5 & \dots & a_{10}^5 \\ \end{array} \right) = \left(\begin{array}{rrrrrrrrrr} 3 & 4 & 5 & 6 & 8 & 25 & 35 & 15 & 42 & 1 \\ 9 & 16 & 25 & 36 & 64 & 19 & 13 & 23 & 47 & 1 \\ 27 & 64 & 24 & 14 & 7 & 71 & 51 & 42 & 55 & 1 \\ 81 & 54 & 19 & 84 & 56 & 58 & 68 & 24 & 88 & 1 \\ 41 & 14 & 95 & 100 & 44 & 36 & 57 & 57 & 60 & 1 \end{array}\right) .

A q-element check, q\leq 5, on the sequence f_1, f_2, \dots, f_n of n elements in F_{101}, n\leq 10, is given by

c_j = \sum_{i=1}^n a_i^j f_i,\ \ \ \ \ (j=1,2,\dots, q).
This check, being based upon the matrix A, will be called a check of “type A”.

With

b_1 = 3, \ b_2 = 4, \ b_3 = 5, \ b_4 = 6, \ b_5 = 8, \  b_6 = 25, \  b_7 = 35, \ b_8 = 1, \
consider the matrix:

B = \left(  \begin{array}{cccc}  b_1 & b_2 & \dots & b_{8} \\  b_1^2 & b_2^2 & \dots & b_{8}^2 \\  \vdots & & & \vdots \\  b_1^5 & b_2^5 & \dots & b_{8}^5 \\  \end{array}  \right)  =  \left(\begin{array}{rrrrrrrrrr}  3 & 4 & 5 & 6 & 8 & 25 & 35 & 1 \\  9 & 16 & 25 & 36 & 64 & 19 & 13 & 1 \\  27 & 64 & 24 & 14 & 7 & 71 & 51 & 1 \\  81 & 54 & 19 & 84 & 56 & 58 & 68 & 1 \\  41 & 14 & 95 & 100 & 44 & 36 & 57 & 1  \end{array}\right)
which is evidently a submatrix of $latex A$. We can obtain a $latex q$-element check, $latex q\leq 5$, on the sequence $latex f_1, f_2, \dots, f_n$, $latex n\leq 8$, taking

c_j = \sum_{i=1}^n b_i^j f_i,\ \ \ \ \ (j=1,2,\dots, q).
This check will be called a check of “type $latex B$”, since it is based upon the matrix $latex B$.

Table 4 below enables us to evaluate easily the checks of types A and B. Table 4 contains nine rows of one hundred columns each. [Note: I have omitted all but the first $14$ columns, for brevity. – wdj.] The ith row shows the products of all non-zero elements of F_{101} by a_i ($i=1,2,\dots, 9$), where the a_i‘s are given above.

\begin{array}{r|rrrrrrrrrrrrrrrrrrrrrrrr}    & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline  1 & 3 & 6 & 9 & 12 & 15 & 18 & 21 & 24 & 27 & 30 & 33 & 36 & 39 & 42 \\  2 & 4 & 8 & 12 & 16 & 20 & 24 & 28 & 32 & 36 & 40 & 44 & 48 & 52 & 56 \\  3 & 5 & 10 & 15 & 20 & 25 & 30 & 35 & 40 & 45 & 50 & 55 & 60 & 65 & 70 \\  4 & 6 & 12 & 18 & 24 & 30 & 36 & 42 & 48 & 54 & 60 & 66 & 72 & 78 & 84 \\  5 & 8 & 16 & 24 & 32 & 40 & 48 & 56 & 64 & 72 & 80 & 88 & 96 & 3 & 11 \\  6 & 25 & 50 & 75 & 100 & 24 & 49 & 74 & 99 & 23 & 48 & 73 & 98 & 22 & 47 \\  7 & 35 & 70 & 4 & 39 & 74 & 8 & 43 & 78 & 12 & 47 & 82 & 16 & 51 & 86 \\  8 & 15 & 30 & 45 & 60 & 75 & 90 & 4 & 19 & 34 & 49 & 64 & 79 & 94 & 8 \\  9 & 42 & 84 & 25 & 67 & 8 & 50 & 92 & 33 & 75 & 16 & 58 & 100 & 41 & 83 \\  \end{array}
Caption: A table of products with the a_i‘s.

Table 4 can be replaced by a highly convenient mechanical device, which greatly facilitates the rapid determination of the c_j‘s. But we are here only concerned with the mathematical description of checking operations, and not with devices to affect their practical application.

One thought on “Lester Hill’s “The checking of the accuracy …”, part 12

  1. Pingback: Lester Hill’s “The checking of the accuracy …”, part 13 | Yet Another Mathblog

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s