Hill verses Hamming

Posted on 2016/08/05 by wdjoyner

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 2015/01/30 by wdjoyner

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 $i$ th 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 2014/09/30 by wdjoyner

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 9

Posted on 2013/05/27 by wdjoyner

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 2012/10/06 by wdjoyner

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 3

Posted on 2012/06/05 by wdjoyner

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

Section 3: Preliminary characterization of checking procedure

Our problem is to provide convenient and practical accuracy checks upon a sequence of $n$ elements $f_1$ , $f_2$ , $\dots$ , $f_n$ in a finite algebraic field $F$ .

To fix the ideas, let us assume that we are to employ $q$ -element checks $c_1$ , $c_2$ , $\dots$ , $c_q$ upon the sequence $f_1$ , $f_2$ , $\dots$ , $f_n$ . The checks are to be determined by means of a fixed reference matrix

$Q = \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 elements of $F$ , the matrix having been suitably constructed according to criteria which will be developed in the following pages. We send, in place of the simple sequence $f_1$ , $f_2$ , $\dots$ , $f_n$ , the amplified sequence

$f_1, f_2, \dots, f_n, c_1, c_2, \dots, c_q$
consisting of the “operand” sequence and the “checking” sequence. The checking sequence contains $q$ elements of $F$ as follows:

$c_j = \sum_{i=1}^n k_{ji}f_i,$

for $j = 1, 2, \dots, q$ . Considerations of telegraphic economy dictate the assumption, made throughout the paper, that $q\leq n$ .

Before laying down specifications for the reference matrix $Q$ , we define a matrix of “index” $q$ as one in which no $q$ -rowed determinant vanishes.

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

Posted on 2012/06/03 by wdjoyner

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

Secton 2: Lemmas concerning algebraic fields

Familiarity with primary notions in the theory of finite algebraic fields, and of their algebraic extensions, will naturally be assumed here. Reference is made, however, to Steinitz [St], Dickson [D], Scorza [Sc]. But several points which will be needed very frequently in the following pages are summarized here in a series of lemmas. These lemmas assert properties of any algebraic field, whether it be finite or not.

Lemma 1:
Let $F$ denote an algebraic field. Let the coeefficients $a_{ij}$ in the system of equations

$\begin{array}{c} a_{11}x_1 +a_{12}x_2 +\dots + a_{1n}x_n=0\\ a_{21}x_1 +a_{22}x_2 +\dots + a_{2n}x_n=0\\ \vdots \\ a_{n1}x_1 +a_{n2}x_2 +\dots + a_{nn}x_n=0, \\ \end{array}$

be elements of $F$ . Let $\Delta$ denote the value, in $F$ , of the determinant

$\begin{array}{|ccc|} a_{11} & \dots & a_{1n} \\ \vdots && \\ a_{n1} & \dots & a_{nn} \\ \end{array} \, .$
The system of equations has a solution other than

$x_1 = x_2 = \dots = x_n = 0$

if and only if $\Delta =0$ .

Lemma 2:
Let $F$ denote an algebraic field. Let the coeefficients in the system of equations

$\begin{array}{c} a_{11}x_1 +a_{12}x_2 +\dots + a_{1n}x_n=0\\ a_{21}x_1 +a_{22}x_2 +\dots + a_{2n}x_n=0\\ \vdots \\ a_{k1}x_1 +a_{k2}x_2 +\dots + a_{kn}x_n=0, \\ \end{array}$

be elements of $F$ , and let $k$ be less than $n$ . Then the system of equations certainly has a solution other than
$x_1 = x_2 = \dots = x_n = 0\, .$

Lemma 3:
Let $F$ denote an algebraic field. Let the $a_{ij}$ and the $c_i$ denote elements of $F$ and let at least one of the $c_i$ be different from zero. Consider the determinant

$\Delta = \begin{array}{|ccc|} a_{11} & \dots & a_{1n} \\ \vdots && \\ a_{n1} & \dots & a_{nn} \\ \end{array} \, .$
If $\Delta \not=0$ (Footnote: The case $\Delta = 0$ does not concern us.) then the system of equations

$\begin{array}{c} a_{11}x_1 +a_{12}x_2 +\dots + a_{1n}x_n=0\\ a_{21}x_1 +a_{22}x_2 +\dots + a_{2n}x_n=0\\ \vdots \\ a_{n1}x_1 +a_{n2}x_2 +\dots + a_{nn}x_n=0, \\ \end{array}$

has one and only one solution.

Evidently, when solutions exist for the systems of equations considered in the forgoing three lemmas, such solutions lie entirely in the field $F$ .

The lemma which follows is particularly useful. It is an immediate corollary of Lemma 1.

Lemma 4:
Let $F$ denote an algebraic field. Let the $a_{ij}$ denote elements of $F$ . Then if

$\begin{array}{|ccc|} a_{11} & \dots & a_{1n} \\ \vdots && \\ a_{n1} & \dots & a_{nn} \\ \end{array} =0, \, .$

we can determine at least one sequence of elements $\lambda_1$ , $\lambda_2$ , $\dots$ , $\lambda_n$ , which are not necessarily distinct but certainly are not all equal to zero, such that

$\begin{array}{c} a_{11}\lambda_1 +a_{21}\lambda_2 +\dots + a_{n1}\lambda_n=0\\ a_{12}\lambda_1 +a_{22}\lambda_2 +\dots + a_{n2}\lambda_n=0\\ \vdots \\ a_{1n}\lambda_1 +a_{2n}\lambda_2 +\dots + a_{nn}\lambda_n=0. \\ \end{array}$

Lemma 5:
The algebraic equation of $ $n$ th degree

$a_0x^n + a_1 x^{n-1} + \dots + a_{n-1}x+a_n=0,$

with coefficients in the algebraic field $F$ , can not have more than $n$ roots in $F$ .

Most of the considerations of the present paper will depend, more or less directly, upon these five lemmas.

References:

[D] L. E. Dickson, Linear groups with an exposition of the Galois field theory, B. G. Teubner, Leipzig, 1901. Available here:
http://archive.org/details/lineargroupswith00dickuoft

[Sc] G. Scorza, Corpi numerici e algebre, Giuseppe Principato, 1921.

[St] E. Steinitz, Algebraische theorie der korper, Journal fur die reine und angew. Mathamtik 137(1910)167-308.

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

Posted on 2012/05/30 by wdjoyner

Backstory: Lester Saunders Hill wrote an unpublished notes, 40 pages, undated but probably written in mid- to late 1920s, titled “The checking of the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields”. In the 1960s this was given to David Kahn by Hill’s widow. These notes were typewritten, but mathematical symbols, tables, insertions, and some footnotes were often handwritten. These notes are 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 introductory first section of his paper. I hope to post more later.

Section 1: The problem considered

The forms of code in current use for the economical transmittal of cable and radio messages employ, almost uniformly, the so-called ”pronounceable” combinations. Pronounceability is estimated in terms of letter groups which commonly occur in one or more of eight designated ”telegraphic” languages: English, French, Spanish, etc. International regulations have, in fact, prescribed a system, of charges according to which a secret five-letter word is regarded, in the word count, as one-half of a telegraphic word, or as a full telegraphic word, according to as it is, or is not, pronounceable.

There is now descernible a definite tendancy to abandon this quite arbitrary pronounceability rule, which has heretofore hampered the development of code and cipher communication. And it seems not unlikely that, at some early session of the Interbational Telegraph Congress, all secret five-letter combinations will be placed upon the same basis with respect to transmittal charges.

A mathematical problem of considerable scientific and practical interest arises in this connection. Messages written in pronounceable code or cipher contain within themselves certain checks upon the accuracy of their telegraphic transmittal. But sequences of unpronounceable groups will generally be quite arbitrary, and no such internal check will ordinarily be available. The outstanding requirement is some device capable of protecting totally unrestricted sequences, in a telegraphically economical way, against the hazards of faulty transmittal.

Let the finite set $C$ of signs (letters, numerals, etc) upon which a given system of communication is based – plain-language, code, or cipher system – be placed in correspondence with the elements of a finite algebraic field $F$ . Then the problem of checking sequences of signs in $C$ becomes that of checking sequences of elements in $F$ . As well-known, if we denote by $\Gamma$ the number of elements, including the zero and unit elements, of a finite field $F$ , then $\Gamma$ is one of the numbers:

$2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, \dots ,$

that is to say, $\Gamma$ is of the form $\Gamma = p^r$ , where $p$ denotes a prime positive integer greater than $1$ and $r$ denotes a positive integer. Conversely, if $\Gamma$ is an integer of this form, we can very easily set up finite algebraic fields with $\Gamma$ elements. In devising a scheme of checks for messages based upon the system $C$ of communications with $n$ distinct signs, we should normally work with a field $F$ the number, $\Gamma$ , of whose elements differs as little as possible form $n$ . But this is not essential.

Our problem, viewed form the standpoint of mathematics, is simply that of providing economical and rigorous checks, easily applied in a practical way, upon the accuracy of transmittal of arbitrary sequences of elements in a finite algebraic field.

The method suggested will be applicable to telegraphic messages of any type: plain-language, code, cipher, cipher-code. It will, however, undoubtedly, be found susceptible of fundamental improvement in many respects; and it will probably yield to other, and more definitely practical, procedures that may subsequently be constructed be upon a basis of number-theoretical operations. The present paper will have served its purpose if it succeeds in directing attention to certain hitherto neglected practical possibilites inherent in elementary algebraic manipulations.

Yet Another Mathblog

Tag Archives: error-detecting codes