Tag Archives: Lester Hill

Hill verses Hamming

Posted on by

It’s easy to imagine the 19th century Philadelphia wool dealer Frank J. Primrose as a happy man. I envision him shearing sheep during the day, while in the evening he brings his wife flowers and plays games with his little children until bedtime. However, in 1887 Frank J. Primrose was not a happy man. This is because in June of that year, he had telegraphed his agent in Kansas instructions to buy a certain amount of wool. However, the telegraph operator made a single mistake in transmitting his message and Primrose unintentionally bought far more wool than he could possibly sell. Ordinarily, such a small error has little consequence, because errors can often be detected from the context of the message. However, this was an unusual case and the mistake cost him about a half-million dollars in today’s money. He promptly sued and his case eventually made its way to the Supreme Court. The famous 1894 United States Supreme Court case Primrose v. Western Union Telegraph Company decided that the telegraph company was not liable for the error in transmission of a message.

Thus was born the need for error-correcting codes.


Introduction

Lester Hill is most famously known for the Hill cipher, frequently taught in linear algebra courses today. We describe this cryptosystem in more detail in one of the sections below, but here is the rough idea. In this system, developed and published in the 1920’s, we take a k\times k matrix K, composed of integers between 0 and 25, and encipher plaintext p by p\longmapsto c=Kp, where the arithmetical operations are performed mod 26. Here K is the key, which should be known only to the sender and the intended receiver, and c is the ciphertext transmitted to the receiver.

On the other hand, Richard Hamming is known for the Hamming codes, also frequently taught in a linear algebra course. This will be describes in more detail in one of the sections below, be here is the basic idea. In this scheme, developed in the 1940’s, we take a k\times k matrix G over a finite field F, constructed in a very particular way, and encode a message m by m\longmapsto c=mG, where the arithmetical operations are performed in F. The matrix G is called the generator matrix and c is the codeword transmitted to the receiver.

Here, in a nutshell, is the mystery at the heart of this post.

These schemes of Hill and Hamming, while algebraically very similar, have quite different aims. One is intended for secure communication, the other for reliable communication. However, in an unpublished paper [H5], Hill developed a hybrid encryption/error-detection scheme, what we shall call “Hill codes” (described in more detail below).

Why wasn’t Hill’s result published and therefore Hill, more than Hamming, known as a pioneer of error-correcting codes?

Perhaps Hill himself hinted at the answer. In an overly optimistic statement, Hill wrote (italics mine):

Further problems connected with checking operations in finite fields will be treated in another paper. Machines may be devised to render almost quite automatic the evaluation of checking elements c_1,\dots,c_q according to any proposed reference matrix of the general type described in Section 7, whatever the finite field in which the operations are effected. Such machines would enable us to dispense entirely with tables of any sort, and checks could be determined with great speed. But before checking machines could be seriously planned, the following problem — which is one, incidentally, of considerable interest from the standpoint of pure number theory — would require solution.

– Lester Hill, [H5]

By my interpretation, this suggests Hill wanted to answer the question below before moving on. As simple looking as it is, this problem is still, as far as I know, unsolved at the time of this writing.

Question 1 (Hill’s Problem):
Given k and q, find the largest r such that there exists a k\times r van der Monde matrix with the property that every square submatrix is non-singular.

Indeed, this is closely related to the following related question from MacWilliams-Sloane [MS77], also still unsolved at this time. (Since Cauchy matrices do give a large family of matrices with the desired property, I’m guessing Hill was not aware of them.)

Question 2: Research Problem (11.1d)
Given k and q, find the largest r such that there exists a k\times r matrix having entries in GF(q) with the property that every square submatrix is non-singular.

In this post, after brief biographies, an even more brief description of the Hill cipher and Hamming codes is given, with examples. Finally, we reference previous blog posts where the above-mentioned unpublished paper, in which Hill discovered error-correcting codes, is discussed in more detail.


Short biographies

Who is Hill? Recent short biographies have been published by C. Christensen and his co-authors. Modified slightly from [C14] and [CJT12] is the following information.

Lester Sanders Hill was born on January 19, 1890 in New York. He graduated from Columbia University in 1911 with a B. A. in Mathematics and earned his Master’s Degree in 1913. He taught mathematics for a few years at Montana University, then at Princeton University. He served in the United States Navy Reserves during World War I. After the WWI, he taught at the University of Maine and then at Yale, from which he earned his Ph.D. in mathematics in 1926. His Ph.D. advisor is not definitely known at this writing but I think a reasonable guess is Wallace Alvin Wilson.

In 1927, he accepted a position with the faculty of Hunter College in New York City, and he remained there, with one exception, until his resignation in 1960 due to illness. The one exception was for teaching at the G.I. University in Biarritz in 1946, during which time he may have been reactivated as a Naval Reserves officer. Hill died January 9, 1961.

Thanks to an interview that David Kahn had with Hill’s widow reported in [C14], we know that Hill loved to read detective stories, to tell jokes and, while not shy, enjoyed small gatherings as opposed to large parties.

Who is Hamming? His life is much better known and details can be readily found in several sources.

Richard Wesley Hamming was born on February 11, 1915, in Chicago. Hamming earned a B.S. in mathematics from the University of Chicago in 1937, a masters from the University of Nebraska in 1939, and a PhD in mathematics (with a thesis on differential equations)
from the University of Illinois at Urbana-Champaign in 1942. In April 1945 he joined the Manhattan Project at the Los Alamos Laboratory, then left to join the Bell Telephone Laboratories in 1946. In 1976, he retired from Bell Labs and moved to the Naval Postgraduate School in Monterey, California, where he worked as an Adjunct Professor
and senior lecturer in computer science until his death on January 7, 1998.

Hill’s cipher

The Hill cipher is a polygraphic cipher invented by Lester S. Hill in 1920’s. Hill and his colleague Wisner from Hunter College filed a patent for a telegraphic device encryption and error-detection device which was roughly based on ideas arising from the Hill cipher. It appears nothing concrete became of their efforts to market the device to the military, banks or the telegraph company (see Christensen, Joyner and Torres [CJT12] for more details). Incidently, Standage’s excellent book [St98] tells the amusing story of the telegraph company’s failed attempt to add a relatively simplistic error-detection to telegraph codes during that time period.

Some books state that the Hill cipher never saw any practical use in the real world. However, research by historians F. L. Bauer and David Kahn uncovered the fact that the Hill cipher saw some use during World War II encrypting three-letter groups of radio call signs [C14]. Perhaps insignificant, at least compared to the practical value of Hamming codes, none-the-less, it was a real-world use.

The following discussion assumes an elementary knowledge of matrices. First, each letter is first encoded as a number, namely

A \leftrightarrow 0, B \leftrightarrow 1, \dots, Z \leftrightarrow 25. The subset of the integers \{0, 1, \dots , 25\} will be denoted by Z/26Z. This is closed under addition and multiplication (mod 26), and sums and products (mod 26) satisfy the usual associative and distributive properties. For R = Z/26Z, let GL(k,R) denote the set of invertible matrix transformations T:R^k\to R^k (that is, one-to-one and onto linear functions).


The construction

Suppose your message m consists of n capital letters, with no spaces. This may be regarded an n-tuple M with elements in R = Z/26Z. Identify the message M as a sequence of column vectors {\bf p}\in R^k. A key in the Hill cipher is a k\times k matrix K, all of whose entries are in R, such that the matrix K is invertible. It is important to keep K and k secret.

The encryption is performed by computing {\bf c} = K{\bf p}, and rewriting the resulting vector as a string over the same alphabet. Decryption is performed similarly by computing {\bf p} = K^{-1} {\bf c}..

Example 1: Suppose m is the message “BWGN”. Transcoding into numbers, the plaintext is rewritten p_0=1, p_1=22, p_2=6, p_3=13. Suppose the key is
K=\left(\begin{array}{rr} 1 & 3 \\ 5 & 12 \end{array}\right).
Using Hill’s encryption above gives c_0=7,c_1=3,c_2=24,c_3=3. (Verification is left to the reader as an exercise.)

Security concerns: For example, this cipher is linear and can be broken by a known plaintext attack.


Hamming codes

Richard Hamming is a pioneer of coding theory, introducing the binary
Hamming codes in the late 1940’s. In the days when an computer error could crash the computer and force the programmer to retype his punch cards, Hamming, out of frustration, designed a system whereby the computer could automatically correct certain errors. The family of codes named after him can easily correct one error.


Hill’s unpublished paper

While he was a student at Yale, Hill published three papers in Telegraph and Telephone Age [H1], [H2], [H3]. In these papers Hill described a mathematical method for checking the accuracy of telegraph communications. There is some overlap with these papers and [H5], so it seems likely to me that Hill’s unpublished paper [H5] dates from this time (that is, during his later years at Yale or early years at Hunter).

In [H5], Hill describes a family of linear block codes over a finite field and an algorithm for error-detection (which can be easily extended to error-correction). In it, he states the construction of what I’ll call the “Hill codes,” (defined below), gives numerous computational examples, and concludes by recording Hill’s Problem (stated above as Question 1). It is quite possibly Hill’s best work.

Here is how Hill describes his set-up.

Our problem is to provide convenient and practical accuracy checks upon
a sequence of n elements f_1, f_2, \dots, f_r in a finite algebraic
field F. We send, in place of the simple sequence f_1, f_2, \dots, f_r, the amplified sequence f_1, f_2, \dots, f_r, c_1, c_2, \dots, c_k
consisting of the “operand” sequence and the “checking” sequence.

– Lester Hill, [H5]

Then Hill continues as follows. Let F=GF(p) denote the finite field having p elements, where p>2 is a prime number. The checking sequence contains k elements of F as follows:
c_j = \sum_{i=1}^r a_{i}^jf_i,
for j = 1, 2, \dots, k. The checks are to be determined by means of a
fixed matrix
A = \left( \begin{array}{cccc} a_{1} & a_{2} & \dots & a_{r} \\ a_{1}^2 & a_{2}^2 & \dots & a_{r}^2 \\ \vdots & & & \vdots \\ a_{1}^k & a_{2}^k & \dots & a_{r}^k \\ \end{array} \right)
of elements of F, the matrix having been constructed according to the criteria in Hill’s Problem above. In other words, if the operand sequence (i.e., the message) is the vector {\bf f} = (f_1, f_2, \dots, f_r), then the amplified sequence (or codeword in the Hill code) to be transmitted is

{\bf c} = {\bf f}G,
where G = \left( I_r, A \right) and where I_r denotes the
r\times r identity matrix. The Hill code is the row space of G.

We conclude with one more open question.

Question 3:
What is the minimum distance of a Hill code?

The minimum distance of any Hamming code is 3.

Do all sufficiently long Hill codes have minimum distance greater than 3?


Summary

Most books today (for example, the excellent MAA publication written by Thompson [T83]) date the origins of the theory of error-correcting codes to the late 1940s, due to Richard Hamming. However, this paper argues that the actual birth is in the 1920s due to Lester Hill. Topics discussed include why Hill’s discoveries weren’t publicly known until relatively recently, what Hill actually did that trumps Hamming, and some open (mathematical) questions connected with Hill’s work.

For more details, see these previous blog posts.

Acknowledgements: Many thanks to Chris Christensen and Alexander Barg for
helpful and encouraging conversations. I’d like to explicitly credit Chris Christensen, as well as historian David Kahn, for the original discoveries of the source material.


Bibliography

[C14] C. Christensen, Lester Hill revisited, Cryptologia 38(2014)293-332.

[CJT12] ——, D. Joyner and J. Torres, Lester Hill’s error-detecting codes, Cryptologia 36(2012)88-103.

[H1] L. Hill, A novel checking method for telegraphic sequences, Telegraph and
Telephone Age (October 1, 1926), 456 – 460.

[H2] ——, The role of prime numbers in the checking of telegraphic communications, I, Telegraph and Telephone Age (April 1, 1927), 151 – 154.

[H3] ——, The role of prime numbers in the checking of telegraphic
communications, II, Telegraph and Telephone Age (July, 16, 1927), 323 – 324.

[H4] ——, Lester S. Hill to Lloyd B. Wilson, November 21, 1925. Letter.

[H5] ——, Checking the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields, undated and unpublished notes, 40 pages.
(hill-error-checking-notes-unpublished)

[MS77] F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.

[Sh] A. Shokrollahi, On cyclic MDS codes, in Coding Theory and Cryptography: From Enigma and Geheimschreiber to Quantum Theory, (ed. D. Joyner), Springer-Verlag, 2000.

[St98] T. Standage, The Victorian Internet, Walker & Company, 1998.

[T83] T. Thompson, From Error-Correcting Codes Through Sphere Packings to Simple Groups, Mathematical Association of America, 1983.

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

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 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.

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

Posted on by

The field F_{101}

All essential points connected with the checking of telegraphic sequences by the methods proposed in this paper may be fully illustrated in one finite field. For our purposes, perhaps the most useful field is F_{101}, to which we shall confine our attention in the following sections. The elements of the field F_{101} are the one hundred and one marks\footnote{Hill actually uses the symbol X in place of 100.} 0, 1, 2, \dots, 100. The operations of addition and multiplication are effected as explained in a previous example; and are abbreviated as suggested. To determine sums and products, we regard the marks of the field momentarily as integers of elementary arithmetic. Thus we have

\sum_1^n f_i = f_h,\ \ \ \ \ \ (\prod_1^n f_i = f_k),

the f_i being n marks of F_{101}, distinct or not, if, when the f_i are momentarily regarded as integers of elementary arithmetic, the congruence

\sum_1^n f_i \equiv f_h \pmod{101},\ \ \ \ \ \ (\prod_1^n f_i \equiv f_k \pmod{101}),

holds. It will not be possible to provide a full multiplication table for the field F_{101}. But the following special table will be found convenient.

\begin{array}{r|rrr} x & x^2 & 1/x & -x\\ 1 & 1 & 1 & 100 \\ 2 & 4 & 51 & 99 \\ 3 & 9 & 34 & 98 \\ 4 & 16 & 76 & 97 \\ 5 & 25 & 81 & 96 \\ 6 & 36 & 17 & 95 \\ 7 & 49 & 29 & 94 \\ 8 & 64 & 38 & 93 \\ 9 & 81 & 45 & 92 \\ 10 & 100 & 91 & 91 \\ 11 & 20 & 46 & 90 \\ 12 & 43 & 59 & 89 \\ 13 & 68 & 70 & 88 \\ 14 & 95 & 65 & 87 \\ 15 & 23 & 27 & 86 \\ 16 & 54 & 19 & 85 \\ 17 & 87 & 6 & 84 \\ 18 & 21 & 73 & 83 \\ 19 & 58 & 16 & 82 \\ 20 & 97 & 96 & 81 \\ 21 & 37 & 77 & 80 \\ 22 & 80 & 23 & 79 \\ 23 & 24 & 22 & 78 \\ 24 & 71 & 80 & 77 \\ 25 & 19 & 97 & 76 \\ 26 & 70 & 35 & 75 \\ 27 & 22 & 15 & 74 \\ 28 & 77 & 83 & 73 \\ 29 & 33 & 7 & 72 \\ 30 & 92 & 64 & 71 \\ 31 & 52 & 88 & 70 \\ 32 & 14 & 60 & 69 \\ 33 & 79 & 49 & 68 \\ \end{array}

\begin{array}{r|rrr} x & x^2 & 1/x & -x\\ 34 & 45 & 3 & 67 \\ 35 & 13 & 26 & 66 \\ 36 & 84 & 87 & 65 \\ 37 & 56 & 71 & 64 \\ 38 & 30 & 8 & 63 \\ 39 & 6 & 57 & 62 \\ 40 & 85 & 48 & 61 \\ 41 & 65 & 69 & 60 \\ 42 & 47 & 89 & 59 \\ 43 & 31 & 47 & 58 \\ 44 & 17 & 62 & 57 \\ 45 & 5 & 9 & 56 \\ 46 & 96 & 11 & 55 \\ 47 & 88 & 43 & 54 \\ 48 & 82 & 40 & 53 \\ 49 & 78 & 33 & 52 \\ 50 & 76 & 99 & 51 \\ 51 & 76 & 2 & 50 \\ 52 & 78 & 68 & 49 \\ 53 & 82 & 61 & 48 \\ 54 & 88 & 58 & 47 \\ 55 & 96 & 90 & 46 \\ 56 & 5 & 92 & 45 \\ 57 & 17 & 39 & 44 \\ 58 & 31 & 54 & 43 \\ 59 & 47 & 12 & 42 \\ 60 & 65 & 32 & 41 \\ 61 & 85 & 53 & 40 \\ 62 & 6 & 44 & 39 \\ 63 & 30 & 93 & 38 \\ 64 & 56 & 30 & 37 \\ 65 & 84 & 14 & 36 \\ 66 & 13 & 75 & 35 \\ \end{array}

\begin{array}{r|rrr} x & x^2 & 1/x & -x\\ 67 & 45 & 98 & 34 \\ 68 & 79 & 52 & 33 \\ 69 & 14 & 41 & 32 \\ 70 & 52 & 13 & 31 \\ 71 & 92 & 37 & 30 \\ 72 & 33 & 94 & 29 \\ 73 & 77 & 18 & 28 \\ 74 & 22 & 86 & 27 \\ 75 & 70 & 66 & 26 \\ 76 & 19 & 4 & 25 \\ 77 & 71 & 21 & 24 \\ 78 & 24 & 79 & 23 \\ 79 & 80 & 78 & 22 \\ 80 & 37 & 24 & 21 \\ 81 & 97 & 5 & 20 \\ 82 & 58 & 85 & 19 \\ 83 & 21 & 28 & 18 \\ 84 & 87 & 95 & 17 \\ 85 & 54 & 82 & 16 \\ 86 & 23 & 74 & 15 \\ 87 & 95 & 36 & 14 \\ 88 & 68 & 31 & 13 \\ 89 & 43 & 42 & 12 \\ 90 & 20 & 55 & 11 \\ 91 & 100 & 10 & 10 \\ 92 & 81 & 56 & 9 \\ 93 & 64 & 63 & 8 \\ 94 & 49 & 72 & 7 \\ 95 & 36 & 84 & 6 \\ 96 & 25 & 20 & 5 \\ 97 & 16 & 25 & 4 \\ 98 & 9 & 67 & 3 \\ 99 & 4 & 50 & 2 \\ 100 & 1 & 100 & 1 \end{array}

Squares, reciprocals, negatives

Using the scheme of reciprocals shown in this Table, we may easily perform an rational operations in F_{101}.

Example:

Suppose, for example, that we wish to solve the system of equations:

36x-79y=52,\ \ \ 90x+85y = 98.

They may be written

x-79y/36 = 13/9,\ \ \ \ x+17y/18 = 49/45

and the fractions are quickly evaluated. Thus: -79/36 = 96. Determining the fractions in this manner, we write the two equations in the form:

x+96y=80,\ \ \ \ x+29y=37,

whence y=73 and x=41

The modulus 101 is very convenient to work with. The residue, modulo 101, of any integer is immediately obvious, at sight of the integer, and is therefore obtained without computation.

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

Posted on by

Construction of finite fields for use in checking

Let F_\Gamma denote a finite algebraic field with \Gamma elements. It is well-known that, for a given \Gamma, all fields F_\Gamma are “simply isomorphic”, and therewith, for our purposes, identical. We shall consequently refer, without restraint, to ”the field F_\Gamma.”

If p is a prime positive integer greater than 1, F_p is called, according to the terminology of Section 8, Example 2, a ”primary” field. Explicit addition tables, as was noted in section 8, are hardly required in deal ing with primary fields. The most useful of these fields, in telegraphic checking, are probably F_{23}, F_{29}, F_{31}, and F_{101}. The field F_{101} will be considered in detail in what follows.

The number of elements in a non-primary finite algebraic field
is a power of a prime. If we have

q=p^k
where p and k are positive integers greater than 1, and p is prime, the non-primary field F_q may be constructed very easily by algebraic extension of the field F_p. Explicit addition table is needed when working with a non-primary field. Otherwise, checking operations are exactly the same as in primary fields.

Example: The field F_3 with the elements (marks) 0,1,2, has the tables

\begin{array}{r|*{3}{r}} \multicolumn{1}{c|} +&0&1&2\\\hline {}0&0&1&2\\ {}1&1&2&0\\ {}2&2&0&1\\ \end{array}
\begin{array}{r|*{3}{r}} \multicolumn{1}{c|} \cdot &0&1&2\\\hline {}0&0&0&0\\ {}1&0&1&2\\ {}2&0&2&1\\ \end{array}

By adjoining a root of the equation x^2=2, an equation which is irreducible in F_3, we easily obtain the field F_9 with marks

\alpha j+\beta
where \alpha and \beta denote elements of F_3. The marks of F_9 are thus

0,1,2,j,j+1,j+2,2j,2j+1,2j+2.
These marks (elements) are combined, in the rational field operations of F_9, according to the reduction formula j^2=2. If we label the marks of F_9 as follows

\begin{array}{ccccccccc} 0 & 1 & 2 & j & j+1& j+2& 2j& 2j+1& 2j+2\\ 0 & 1 & a & b & c & d & e & f & g\\ \end{array}
the addition and multiplication tables of the field are given as in
Section 8, Example 1.

In a like manner, F_{27} can be obtained from F_3 by adjunction of a root of the equation x^3=x+1, which is irreducible in F_3 and F_9. The marks (elements) of F_{27} are

\alpha j^2+\beta j+\gamma,
where \alpha,\beta,\gamma are elements of F_3. They are combined, in the rational operations of F_{27} according to the reduction formula j^3=j+1.

Example: The field F_2 with the elements (marks) 0,1, has the tables

\begin{array}{r|*{2}{r}} \multicolumn{1}{c|} + &0&1\\ \hline {}0&0&1\\ {}1&1&0\\ \end{array}
\begin{array}{r|*{2}{r}} \multicolumn{1}{c|} \cdot &0&1\\ \hline {}0&0&0\\ {}1&0&1\\ \end{array}

By adjunction of a root of the equation x^5=x^2+1, which is irreducible in the fields F_2, F_4, F_8 and F_{16}, we easily obtain the field F_{32}. The marks of F_{32} are

\alpha j^4+\beta j^3+\gamma j^2+\delta j+\epsilon,
where \alpha,\beta,\gamma, \delta,\epsilon are elements of F_2; and these 32 marks are combined, in the rational operations of F_{32}, according to the reduction formula j^5=j^2+1.

Example: The field F_5 with the elements (marks) 0,1,2,3,4, has the tables

\begin{array}{r|*{5}{r}} \multicolumn{1}{c|} +&0&1&2&3&4\\\hline {}0&0&1&2&3&4\\ {}1&1&2&3&4&0\\ {}2&2&3&4&0&1\\ {}3&3&4&0&1&2\\ {}4&4&0&1&2&3\\ \end{array}
\begin{array}{r|*{5}{r}} \multicolumn{1}{c|} \cdot &0&1&2&3&4\\\hline {}0&0&0&0&0&0\\ {}1&0&1&2&3&4\\ {}2&0&2&4&1&3\\ {}3&0&3&1&4&2\\ {}4&0&4&3&2&1\\ \end{array}

By adjoining a root of the equation x^2=2, which is irreducible in F_{5}, we readily obtain the field F_{25}. The marks of F_{25} are

\alpha j+\beta ,
where \alpha,\beta are elements of F_5; and these 25 marks are combined, in the rational operations of F_{25}, according to the reduction formula j^2=2.

Of the non-primary fields, F_{25}, F_{27}, F_{32} are probably those which are most amenable to practical application in telegraphic checking.

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

Posted on by

We may inquire into the possibility of undisclosed errors occurring in the transmittal of the sequence:

\begin{array}{ccccccccccccccc} f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8 & f_9 & f_{10} & f_{11} & f_{12} & c_1 & c_2 & c_3 \\ 5 & 17 & 13 & 21 & 0 & 8 & 6 & 0 & 11 & 0 & 11 & 11 & 6 & 15 & 2 \\ X & T & Y & P & V & Z & R & V & H & V & H & H & R & I & F \\ \end{array}

Invoking the theorem established in sections 4 and 5, and formulated at the close of section 5, we may assert:

  • (1) If not more than three errors are made in transmitting the fifteen letters of the sequence, and if the errors made affect the f_i only, the c_j being correctly transmitted, then the presence of error is certain to be disclosed.
  • (2) If not more than three errors are made, all told, but at least three of them affect the f_i, then the presence of error will enjoy only a

    1-{\rm in}-22^3\ \ \ \ \ (1-{\rm in}-10648)
    chance of escaping disclosure.

These assertions result at once from the theorem referred to. But a closer study of the reference matrix employed in this example permits us to replace them by the following more satisfactory statements:

  • (1′)
    If errors occur in not more than three of the fifteen elements of the sequence f_1f_2\dots f_{12}c_1 c_2 c_3, and if at least one of the particular elements f_{11}f_{12}c_2 is correctly transmitted, the presence of error will certainly be disclosed. But if exactly three errors are made, affecting presicely the elements f_{11}f_{12}c_2, the presence of error will enjoy a 1-in-22^2 (1-in-484) chance of escaping disclosure.
  • (2′)
    If more than three errors are made, then whatever the distribution of errors among the fifteen elements of the sequence, the presence of error will enjoy only a
    1-in-22^3 (1-in-10648) chance of escaping disclosure.

Assertions of this kind will be carefully established below, when a more important finite field is under consideration. The argument then made will be applicable in the case of any finite field. But it is worthwhile here to look more carefully into the exceptional distribution of errors which is italicized in (1′). This will help us note any weakness that ought to be avoided in the construction of reference matrices.

Suppose that exactly three errors are made, affecting precisely f_{11}f_{12}c_2. If the mutilated message is to check up, and the errors to escape disclosure, we must have (for error notations, see sections 4,5):

11\epsilon_{11}+12\epsilon_{12}=0,\ \ \ 11^2\epsilon_{11}+12^2\epsilon_{12}=\delta_2,\ \ \ 11^3\epsilon_{11}+12^3\epsilon_{12}=0.
These equations may be written:

11\epsilon_{11}+12\epsilon_{12}=0,\ \ \ 6\epsilon_{11}+6\epsilon_{12}=\delta_2,\ \ \ 20\epsilon_{11}+3\epsilon_{12}=0.
But 11\epsilon_{11}=-12\epsilon_{12} can be written 11\epsilon_{11}=11\epsilon_{12}, or \epsilon_{11}=\epsilon_{12}.
Etc. In this way, we find that the errors can escape disclosure if and only if

\epsilon_{11}=\epsilon_{12},\ \ \ {\rm and}\ \ \ \delta_{2}=12\epsilon_{11}.
The error \epsilon_{11} can be made quite arbitrarily. But then the values of \epsilon_{12} and \delta_2 are then completely determined. There is evidently a 1-in-484 chance – and no more – that the errors will fall out just right.

The trouble arises from the vanishing, in our reference matrix, of the two-rowed
determinant

\big{|} \begin{array}{cc} 11 & 12 \\ 11^3 & 12^3 \end{array} \big{|} .
Note that

\big{|} \begin{array}{cc} 11 & 12 \\ 11^3 & 12^3 \end{array} \big{|} = 11\cdot 12\cdot \big{|} \begin{array}{cc} 1 & 1 \\ 11^2 & 12^2 \end{array} \big{|} = 17 \big{|} \begin{array}{cc} 1 & 1 \\ 11^2 & 12^2 \end{array} \big{|} =0,
since 11^2=12^2.

From the fact that \big{|} \begin{array}{cc} 11 & 12 \\ 11^3 & 12^3 \end{array} \big{|} is the only vanishing determinant of any order in the matrix employed, all other assertions made in (1′) and (2′) are readily justified. This will be made clear in the following sections.

It will be advantageous, as shown more completely in subsequent sections, to employ reference matrices which contain the smallest possible number of vanishing determinants of any orders.

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

Posted on by

Introductory example of checking

We may use the field F_{23} as the basis for a simple illustrative exercise in the actual procedure of checking. The general of the operations involved will thus be made clear, so far as modus operandi is concerned, and we shall be enabled to discuss more easily the pertinent mathematical details.

It is easy to set up telegraphic codes of high capacity using combinations of four letters each which are not required to be pronounceable. In fact, a sufficiently high capacity may be obtained when only
twenty-three letters of the alphabet are used at all. Hence we can omit any three letters whose Morse equivalents (dot-dash) are most frequently used. Let us suppose that we have before us a code of this kind which employs the letters

A\ \ B\ \ C\ \ E\ \ F\ \ G\ \ H\ \ I\ \ J\ \ L\ \ M\ \ N\ \ P\ \ Q\ \ R\ \ S\ \ T\ \ U\ \ V\ \ W\ \ X\ \ Y\ \ Z
and avoids, for reasons stated of for some good reason, the three letters

D\ \ K\ \ O\, .

Suppose that, by prearrangement with telegraphic correspondents, the letters used are paired in
an arbitrary, but fixed, way with the thwenty-three elements of F_{23}.
Let the pairings be, for instance:

\begin{tabular}{ccccccccccccccccccccccc} A & B & C & E & F & G & H & I & J & L & M & N & P & Q & R & S & T & U & V & W & X & Y & Z \\ \hline 4 & 7 & 9 & 14& 2 & 1 & 11 & 15 & 10 & 3 & 19 & 18 & 21 & 16 & 6 & 20 & 17 & 12 & 0 & 22 & 5 & 13 & 8 \\ \end{tabular}
or, in numerical arrangement:

\begin{tabular}{ccccccccccccccccccccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ \hline V & G & F & L& A & X & R & B & Z & C & J & H & U & Y & E & I & Q & T & N & M & S & P & W \\ \end{tabular}

A four-letter group (code word), such as EZRA or XTYP, will indicate a definite entry of a specific page of a definite code volume, several such volumes being perhaps employed in the code. An entry will, in general, be a phrase of sentence, or a group of phrases or sentences, commonly occurring in the class of messages for which the code has been constructed.

Suppose that we have agreed to provide, in our messages, three-letter checks upon groups of twelve letters; in other words, to check in one operation a sequence of three four-letter code words. The twelve letters of the three code words are thus expanded to fifteen; but we send just three telegraphic words — three combinations of five letters, each of which is, in general, unpronounceable.

For illustration, let the first three code words of a message be:

XTYP\ \ \ \ VZRV\ \ \ \ HVHH
The corresponding sequence of paired elements in F_{23} is:

5 \ \ 17\ \ 13\ \ 21\ \ 0\ \ 8\ \ 6\ \ 0\ \ 11\ \ 0\ \ 11\ \ 11.
This is our operand sequence f_i:

f_1 = 5,\ \ f_2=17,\ \ f_3=13,\ \ f_4=21,\ \ f_5=0,\ \dots,\ ,f_{12}=11.

Let us determine the checking matrix c_1, c_2, c_3 by using as reference matrix

\left( \begin{array}{cccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ 1^2 & 2^2 & 3^2 & 4^2 & 5^2 & 6^2 & 7^2 & 8^2 & 9^2 & 10^2 & 11^2 & 12^2 \\ 1^3 & 2^3 & 3^3 & 4^3 & 5^3 & 6^3 & 7^3 & 8^3 & 9^3 & 10^3 & 11^3 & 12^3 \\ \end{array} \right)
Thus the c_j are to be

c_j = \sum_{i=1}^{12} i^jf_i\ \ \ \ (j = 1,2,3),

or

c_1 = \sum_{i=1}^{12} if_i.\ \ \ c_2 = \sum_{i=1}^{12} i^2f_i.\ \ \ c_3 = \sum_{i=1}^{12} i^3f_i.

Referring to the multiplication table of F_{23}, we easily compute the c_j.

For the first element 5, of the operant sequence f_i, write

\begin{tabular}{ccc} 5 & 5 & 5\\ \end{tabular}

For the second element 17 place a sheet of paper (or a ruler) under the second row
of the multiplication table, and in that row read: 11 in column 17, 22 in column 11, 21 in column 22. we now have a second line for the tabular scheme:

\begin{tabular}{ccc} 5 & 5 & 5\\ 11 & 22 & 21 \\ \end{tabular}

For the third element 13 place a sheet of paper (or a ruler) under the third row
of the multiplication table, and in that row read: 16 in column 13, 2 in column 16, 6 in column 2. We now have the scheme:

\begin{tabular}{ccc} 5 & 5 & 5\\ 11 & 22 & 21 \\ 16 & 2 & 6 \\ \end{tabular}

The fifth, eighth, and tenth rows of the table will not be used, since
f_5=f_8=f_{10}=0. The complete scheme is readily found to be:

\begin{tabular}{cccc} 5 & 5 & 5 & \\ 11 & 22 & 21 & \\ 16 & 2 & 6 & \\ 15 & 14 & 10 & \\ 2 & 12 & 3 & \\ 19 & 18 & 11 & \\ 7 & 17 & 15 & \\ 6 & 20 & 13 & \\ 17 & 20 & 10 & \\ \hline 98 & 130 & 94 & sum in ZZ\\ 6 & 15 & 2 & sum in F-23\\ \end{tabular}

We have c_1=6, c_2=15, c_2=2.

We transmit, of course, the sequence of letters paired, in our system of communications, with the elements of the sequence,

f_1\ f_2\ \dots f_{12}\ c_1\ c_2 \ c_3.

Thus we transmit the sequence of letters: XTYP VZRV HVHH RIF; but we may conveniently agree to transmit it in the arrangement:

XTYPR\ \ \ VZRVI\ \ \ HVHHF ,

or in some other arrangement which employs only three telegraphic words (unpronounceable five letter groups).

We could have used other reference matrices, but we shall not stop to discuss this point. We may remark, however, that if the matrix

\left( \begin{array}{cccccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ 1^2 & 2^2 & 3^2 & 4^2 & 5^2 & 6^2 & 7^2 & 8^2 & 9^2 & 10^2 & 11^2 & 12^2 \\ \end{array} \right)

had been adopted, the checking elements would have been

c_1 = \sum_{i=1}^{12} f_i.\ \ \ c_2 = \sum_{i=1}^{12} if_i.\ \ \ c_3 = \sum_{i=1}^{12} i^2f_i;

and their evaluation would have been accomplished with equal
ease by means of the multiplication table of F_{23}.

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

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 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

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.