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

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 eighth section of his paper. I hope to post more later. (Part 7 is here.)

Section 8: Examples of finite fields

The reader is probably accustomed to the congruence notation in dealing with finite fields. It may therefore be helpful to insert here two simple examples of finite fields, and to employ, in these concrete cases, the notations of the present paper rather than those of ordinary number theory.

Example: A small field in which the number \Gamma is not prime.

Let the elements of the field be the symbols or marks

0, 1, a,b,c,d,e,f,g;
and let us define, by means of two appended tables, the field of operations of addition and multiplcation in such a manner that the marks 0, 1 represent respectively the zero and the unit elements of the field.

These tables are

\begin{tabular}{r|*{9}{r}}  \multicolumn{1}{c|}  +&0&1&a&b&c&d&e&f&g\\\hline  {}0&0&1&a&b&c&d&e&f&g\\  {}1&1&a&0&c&d&b&f&g&e\\  {}a&a&0&1&d&b&c&g&e&f\\  {}b&b&c&d&e&f&g&1&a&0\\  {}c&c&d&b&f&g&e&a&0&1\\  {}d&d&b&c&g&e&f&0&1&a\\  {}e&e&f&g&1&a&0&c&d&b\\  {}f&f&g&e&a&0&1&d&b&c\\  {}g&g&e&f&0&1&a&b&c&d\\  \end{tabular}

\begin{tabular}{r|*{9}{r}}  \multicolumn{1}{c|}  {*}&0&1&a&b&c&d&e&f&g\\\hline  {}0&0&0&0&0&0&0&0&0&0\\  {}1&0&1&a&b&c&d&e&f&g\\  {}a&0&a&1&e&g&f&b&d&c\\  {}b&0&b&e&a&d&g&1&c&f\\  {}c&0&c&g&d&e&1&f&a&b\\  {}d&0&d&f&g&1&b&c&e&a\\  {}e&0&e&b&1&f&c&a&g&d\\  {}f&0&f &d&c&a&e&g&b&1\\  {}g&0&g&c&f&b&a&d&1&e\\  \end{tabular}

Denoting by x an arbitrary element of this field, we see that negatives and reciprocals of the elements of the field are as shown in the scheme:

\begin{tabular}{r|rrrrrrrrr}  x & 0&1&a&b&c&d&e&f&g\\ \hline  -x &0&a&1&e&g&f&b&d&c\\ \hline  1/x & - &1&a&e&d&c&b&g&f \\  \end{tabular}

The use of notations is easily illustrated. Thus, for example, we note that the determinant

\Delta = \left|  \begin{array}{ccc}  f & b & g \\  1 & f & a \\  d & e & 1 \\  \end{array}  \right| \, .
of the system of equations

\begin{array}{r}  fx+by+gz = 0\\  x+fy+az=0\\  dx+ey+z=0  \end{array}
vanishes. For, expanding the determinant by the elements of its first row, we obtain

\begin{array}{lcr}  \Delta &= & f(f-ea) - b(1-da)+g(e-fd) \\  &= & f(f+e)+e(1+d)+g(e+b) \\  &= & fc+eb+g(0) =fc+eb=a+1 = 0.  \end{array}
Hence the system has solutions other than x=y=z=0. By the usual methods, it is quickly found that one solution is (x=d, y=1, z=0). The general solution is (x=\lambda d, y=\lambda, z=0), where \lambda denotes an element of the field.

For further practice, we note that the system of equations

\begin{array}{rl}  bx+gy &= d\\  ax+ez & = 0\\  ex+fy+az &= f \\  \end{array}
has exactly one solution. It may be found by the standard method employing quotients of determinants [What we call today Cramer’s rule – wdj.]. or as follows:

[11 lines of hand calculations are omitted. – wdj]

The solution is x=y=f, z=c.
\Box

As noted in Section 1, the number \Gamma of the elements of a finite algebraic field is either a prime integer greater than 1, or a positive integral power of such an integer. In the present example, we have \Gamma = 9= 3^2. It may be observed in passing that if \lambda is any element of a finite field for which

\Gamma = 2^n,\ \ \ \ \ n\geq 1,
that is, for which \Gamma is a power of 2, then in that field \lambda = -\lambda.

Example: A small field in which the number \Gamma of elements is prime.

Let f_0, f_1, \dots f_{p-1} be p symbols or marks, and let p be a prime integer. We readily define a finite algebraic field of which the elements are the f_i. To this end, we regard $f_i$ as associated with the integer i which we shall call the “affix” of the mark f_i. Understanding that of course 0 is the “smallest integer” in any set of non-negative integers which includes 0, we now define as follows:

Sum: The sum of the marks f_i and f_j is given by the formula

f_i+f_j = f_k,
where k is the smallest non-negative integer satisfying

i+j\equiv k \pmod{p}.

Product: The product of the marks f_i and f_j is given by the formula

f_if_j = f_h,
where h is the smallest non-negative integer satisfying

ij\equiv h \pmod{p}.

With the operations of addition and multiplication thus defined, our set of p marks constitutes, as is well-known, an algebraic field. We call a field of this type a “primary” field.
\Box

In a primary field, an addition table would never be required. For we note that, if

f_{j_1}, f_{j_2}, \dots, f_{j_t},
are t elements of our field then

\sum_{i=1}^t f_{j_i} = f_k,
where k is the smallest non-negative integer satisfying the congruence

\sum_{i=1}^t j_i \equiv k\ \pmod{p}\ .

Naturally, a similar statement holds for the product. We have

\prod_{i=1}^t f_{j_i} = f_h,
where h is the smallest non-negative integer satisfying the congruence

\prod_{i=1}^t j_i \equiv h\ \pmod{p}\ .

In the foregoing definitions, any of the terms of a sum, or of the factors of a product, may, of course, be equal.

When dealing with a primary field, we may obviously replace the marks of the fields by their affixes. We do this in the example which follows.

Example: Let the marks of a finite field be

0,1,2,\dots, 21, 22,
the field containing p=23 elements. An addition table is not needed. The multiplication table is as follows:

\begin{tabular}{l|rrrrrrrrrrrrrrrrrrrrrr}  \ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ \hline  1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\  2 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 \\  3 & 3 & 6 & 9 & 12 & 15 & 18 & 21 & 1 & 4 & 7 & 10 & 13 & 16 & 19 & 22 & 2 & 5 & 8 & 11 & 14 & 17 & 20 \\  4 & 4 & 8 & 12 & 16 & 20 & 1 & 5 & 9 & 13 & 17 & 21 & 2 & 6 & 10 & 14 & 18 & 22 & 3 & 7 & 11 & 15 & 19 \\  5 & 5 & 10 & 15 & 20 & 2 & 7 & 12 & 17 & 22 & 4 & 9 & 14 & 19 & 1 & 6 & 11 & 16 & 21 & 3 & 8 & 13 & 18 \\  6 & 6 & 12 & 18 & 1 & 7 & 13 & 19 & 2 & 8 & 14 & 20 & 3 & 9 & 15 & 21 & 4 & 10 & 16 & 22 & 5 & 11 & 17 \\  7 & 7 & 14 & 21 & 5 & 12 & 19 & 3 & 10 & 17 & 1 & 8 & 15 & 22 & 6 & 13 & 20 & 4 & 11 & 18 & 2 & 9 & 16 \\  8 & 8 & 16 & 1 & 9 & 17 & 2 & 10 & 18 & 3 & 11 & 19 & 4 & 12 & 20 & 5 & 13 & 21 & 6 & 14 & 22 & 7 & 15 \\  9 & 9 & 18 & 4 & 13 & 22 & 8 & 17 & 3 & 12 & 21 & 7 & 16 & 2 & 11 & 20 & 6 & 15 & 1 & 10 & 19 & 5 & 14 \\  10 & 10 & 20 & 7 & 17 & 4 & 14 & 1 & 11 & 21 & 8 & 18 & 5 & 15 & 2 & 12 & 22 & 9 & 19 & 6 & 16 & 3 & 13 \\  11 & 11 & 22 & 10 & 21 & 9 & 20 & 8 & 19 & 7 & 18 & 6 & 17 & 5 & 16 & 4 & 15 & 3 & 14 & 2 & 13 & 1 & 12 \\  12 & 12 & 1 & 13 & 2 & 14 & 3 & 15 & 4 & 16 & 5 & 17 & 6 & 18 & 7 & 19 & 8 & 20 & 9 & 21 & 10 & 22 & 11 \\  13 & 13 & 3 & 16 & 6 & 19 & 9 & 22 & 12 & 2 & 15 & 5 & 18 & 8 & 21 & 11 & 1 & 14 & 4 & 17 & 7 & 20 & 10 \\  14 & 14 & 5 & 19 & 10 & 1 & 15 & 6 & 20 & 11 & 2 & 16 & 7 & 21 & 12 & 3 & 17 & 8 & 22 & 13 & 4 & 18 & 9 \\  15 & 15 & 7 & 22 & 14 & 6 & 21 & 13 & 5 & 20 & 12 & 4 & 19 & 11 & 3 & 18 & 10 & 2 & 17 & 9 & 1 & 16 & 8 \\  16 & 16 & 9 & 2 & 18 & 11 & 4 & 20 & 13 & 6 & 22 & 15 & 8 & 1 & 17 & 10 & 3 & 19 & 12 & 5 & 21 & 14 & 7 \\  17 & 17 & 11 & 5 & 22 & 16 & 10 & 4 & 21 & 15 & 9 & 3 & 20 & 14 & 8 & 2 & 19 & 13 & 7 & 1 & 18 & 12 & 6 \\  18 & 18 & 13 & 8 & 3 & 21 & 16 & 11 & 6 & 1 & 19 & 14 & 9 & 4 & 22 & 17 & 12 & 7 & 2 & 20 & 15 & 10 & 5 \\  19 & 19 & 15 & 11 & 7 & 3 & 22 & 18 & 14 & 10 & 6 & 2 & 21 & 17 & 13 & 9 & 5 & 1 & 20 & 16 & 12 & 8 & 4 \\  20 & 20 & 17 & 14 & 11 & 8 & 5 & 2 & 22 & 19 & 16 & 13 & 10 & 7 & 4 & 1 & 21 & 18 & 15 & 12 & 9 & 6 & 3 \\  21 & 21 & 19 & 17 & 15 & 13 & 11 & 9 & 7 & 5 & 3 & 1 & 22 & 20 & 18 & 16 & 14 & 12 & 10 & 8 & 6 & 4 & 2 \\  22 & 22 & 21 & 20 & 19 & 18 & 17 & 16 & 15 & 14 & 13 & 12 & 11 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1  \end{tabular}

Products in which 0 is a factor all vanish, and therefore not shown in the table.

In any algebraic field, the elements \lambda and \mu are negatives — \lambda = -\mu, \mu = -\lambda — when \lambda+\mu=0. In the present example, therefore, two marks i and j are negatives if

i+j\equiv 0 \pmod{23},
where i,j are momentarily regarded as ordinary integers of familiar arithmetic.

Negatives, reciprocals, squares and cubes are shown by the scheme:

\begin{array}{l|rrrrrrrrrrrrrrrrrrrrrrr}  x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ \hline  -x & 0 & 22 & 21 & 20 & 19 & 18 & 17 & 16 & 15 & 14 & 13 & 12 & 11 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline  1/x & - & 1 & 12 & 8 & 6 & 14 & 4 & 10 & 3 & 18 & 7 & 21 & 2 & 16 & 5 & 20 & 13 & 19 & 9 & 17 & 15 & 11 & 22 \\ \hline  x^2 & 0 & 1 & 4 & 9 & 16 & 2 & 13 & 3 & 18 & 12 & 8 & 6 & 6 & 8 & 12 & 18 & 3 & 13 & 2 & 16 & 9 & 4 & 1 \\ \hline  x^3 & 0 & 1 & 8 & 4 & 18 & 10 & 9 & 21 & 6 & 16 & 11 & 20 & 3 & 12 & 7 & 17 & 2 & 14 & 13 & 5 & 19 & 15 & 22  \end{array}
This field will be called F-23. We shall use it in illustrating our checking operations.

Familiarity with the notations here employed may be gained by working out several exercises of simple type. Thus, the reader may note that the polynomial in F-23

x^3+x^2+13x-8,
has the three roots x=5,6,11, so that we may write

x^3+x^2+13x-8 = (x+18)(x+17)(x+12).

He may make the important observation that no two different elements of F-23 have the same cube, and that this was to be expected. For the equation

x^3-\lambda^3 = 0,
where \lambda denotes any element (other than 0) of F-23, can be written

(x-\lambda)(x^2+\lambda x + \lambda^2)=0,
the factor x^2+\lambda x + \lambda^2 being irreducible in F-23. The fact that

x^2+\lambda x + \lambda^2
has no root in F-23 may be shown by “completing the square”, and thus noting that the roots would have to be of the form

-\frac{\lambda}{2}(1\pm \sqrt{-3})=-\frac{\lambda}{2}(1\pm \sqrt{20}).
But reference to the scheme of squares given above discloses that 20 is not the square of an element in F-23.
\Box

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