#### by A. A. Albert

#### 1. Introduction

The idea of connecting cryptography with mathematics is not new, but it has not been exploited in the literature of either subject to the extent of the present paper. Our topic should be a timely one not only because of the present public interest in anything connected with our war effort, but also because of the current ever increasing use by scientists1 of the concepts of modern abstract algebra.

We shall present here a mathematical formulation of a general theory
of cryptology2
with detailed application to cryptography. In this, we
shall see that cryptography is more than a subject permitting
mathematical formulation, for indeed it would not be an exaggeration
to state that *abstract* cryptography is *identical* with
abstract mathematics.

Our formulation will permit a rapid presentation of the methods of cryptography in common use, and we shall show that all of these methods are very special cases of the so-called *algebraic* cipher systems. These latter cipher systems are entirely practical in the simple cases, and we hope that our presentation will destroy the belief of many cryptologists that
they are “only practical providing a machine is used.”3

#### 2. Cryptography as a theory of non-singular mappings

The function concept has been described frequently as a unifying concept for collegiate mathematics. Elementary functions are usually given by formulas __\( y = f(x) \)__, but this sort of definition is not always possible and only makes sense in an environment in which the necessary additional assumptions are presupposed for all the functions considered. Let us then formulate the concept in complete general terms.

Consider a set __\( \mathcal{M} \)__ consisting of *any objects whatever* and call these objects the *quantities* of __\( \mathcal{M} \)__. (They might be numbers or physical objects or even mathematical concepts!) We let __\( x \)__ be a symbol which is permitted, during our discussion, to represent any quantity of __\( \mathcal{M} \)__, so that we call __\( x \)__ a *variable* whose *range* is __\( \mathcal{M} \)__. Let __\( \mathcal{N} \)__ be a second set of quantities and set up a correspondence
__\begin{equation}
x \mapsto S(x)
\label{eq-01}
\end{equation}__
(read __\( x \)__ goes to __\( S(x) \)__) whereby every __\( x \)__ in __\( \mathcal{M} \)__ determines a unique __\( S(x) \)__ in __\( \mathcal{N} \)__. Then the symbol __\( u = S(x) \)__ is a second variable, with __\( \mathcal{N} \)__ as its range, and we are accustomed to say that the correspondence defines __\( u \)__ as a function of __\( x \)__.

Thus, a function of __\( x \)__ really consists of two sets __\( \mathcal{M} \)__
and __\( \mathcal{N} \)__ and the correspondence __\( S \)__ given by __\eqref{eq-01}__ of
the quantities __\( x \)__ of __\( \mathcal{M} \)__ on their *images* __\( S(x) \)__
in __\( \mathcal{N} \)__. It will be better for our purposes to describe this
situation by simply speaking of __\( S \)__ rather than the function, and we
shall call __\( S \)__ a mapping of __\( \mathcal{M} \)__ on __\( \mathcal{N} \)__.

Suppose that there is also a mapping __\( T \)__ given by
__\begin{equation}
u \mapsto T(u)
\label{eq-02}
\end{equation}__
on __\( \mathcal{N} \)__ to __\( \mathcal{M} \)__, so that every __\( u \)__ of __\( \mathcal{N} \)__
determines a unique __\( T(u) \)__ in __\( \mathcal{M} \)__. Then we let __\( T \)__ be such
that if __\( u=S(x) \)__, the quantity __\( T(u) = x \)__. In this case, the
mapping __\( S \)__ is called a *non-singular* mapping. __\( T \)__ is called its
*inverse*, and we indicate this by writing __\( T=S^{-1} \)__.

*Cryptography* is the study of all non-singular mappings __\( S \)__
on __\( \mathcal{M} \)__ to __\( \mathcal{N} \)__ where __\( \mathcal{M} \)__ is the set of a
*messages* __\( x \)__ and __\( \mathcal{N} \)__ is the set of all
*cryptograms* __\( S(x) \)__. The mappings are called *cipher
systems*. If a message __\( x \)__ and a cipher system __\( S \)__ are given, the
process of the application of __\( S \)__ to __\( x \)__, so as to obtain the
cryptogram __\( S(x) \)__, is called the *encipherment* of __\( x \)__. When __\( S \)__
and __\( S(x) \)__ are given, the process of the application of __\( S^{-1} \)__ to
the cryptogram __\( S(x) \)__, so as to obtain the message __\( x \)__, is called the
*decipherment* of __\( S(x) \)__.

There are many mathematical situations in which it is possible to
determine a mapping __\( S \)__ on __\( \mathcal{M} \)__ to __\( \mathcal{N} \)__ from a given
list of a finite number of quantities __\( x \)__ in __\( \mathcal{M} \)__ and their
images __\( S(x) \)__ in __\( \mathcal{N} \)__. However we wish to propose the more
difficult problem of determining __\( S \)__ (and hence each __\( x \)__) from a given
finite set of cryptograms __\( S(x) \)__. We use this in the definition of
*cryptanalysis* as the theory of those structural properties of
messages, cryptograms, and cipher systems which are required in order
to solve all problems (which permit a solution) of the kind above. The
solution of such a problem is called the *decryptment* of its
cryptograms, and so cryptanalysis is the study of the methods of
decryptment. *Cryptology* is the subject comprising both
cryptography and cryptanalysis. However, we shall be concerned only
with the first of these two branches here.

#### 3. Cipher systems on components, and codes

It is clear from what we have said that the most primitive cipher
system would be simply a list of all the messages to be used and an
adjacent list of corresponding cryptograms. However, some more
sophisticated cipher systems are describable, as is the case for some
mathematical functions, by formulas. These formulas will express the
cryptogram __\( S(x) \)__ in terms of the result of applying the cipher
system __\( S \)__ to what we shall call *components* of the message __\( x \)__,
and we shall formulate this new concept.

The term message has not been interpreted thus far but we now conceive
of it as any sequence of a finite number of symbols which are either
letters, periods, or commas and the like. We now partition the
message into blocks of symbols called components. The message __\( x \)__ will
then become a sequence of components, each consisting of a group of
symbols of the message __\( x \)__. These occur in the component in the same
order as in __\( x \)__. Also the order of the components themselves is fixed
by the order of the symbols in __\( x \)__. The components may be simply the
words of __\( x \)__, or its sentences, or simply blocks of a fixed number of
letters. In the latter case the final block may not contain enough
letters to satisfy the given definition. Then it will be necessary to
adjoin letters, called *nulls*, to bring up the number of letters
to the required amount.

Suppose now that a message __\( x \)__ has been broken up into __\( n \)__ components
where __\( n \)__ is a positive integer. Let __\( i \)__ be any integer from 1 to __\( n \)__
and let the symbol __\( x_i \)__ represent the __\( i \)__-th component of __\( x \)__. Then
we may represent this situation by writing __\( x \)__ in the following
notation
__\begin{equation}
x = \bigl[x_1, x_2, \dots , x_n\bigr].
\label{eq-03}
\end{equation}__
We wish also to use cipher systems __\( S \)__ which replace __\( x \)__ by sequences
__\begin{equation}
u = S(x) = \bigl[u_1, u_2, \dots , u_m \bigr].
\label{eq-04}
\end{equation}__
Here, the cryptogram __\( u \)__ has been broken up into __\( m \)__ components of some prescribed kind and neither the positive integer __\( m \)__ nor the kind of components __\( u_j \)__ (__\( j=1, \dots , m \)__) need be the same as for __\( x \)__.

The most primitive formula for a cipher system in terms of __\eqref{eq-03}__ and __\eqref{eq-04}__ is given by
__\begin{equation}
S(x) = \bigl[ T(x_1), T(x_2), \dots , T(x_n)\bigr],
\label{eq-05}
\end{equation}__
where __\( T \)__ is a non-singular mapping on the set __\( \mathcal{M}_0 \)__ of the components (of a prescribed kind) of messages to the set __\( \mathcal{N}_0 \)__ of components of cryptograms (also of prescribed kind). The *code* is such a cipher system. Here, the components of __\( x \)__ are the words, __\( \mathcal{M}_0 \)__ is the set of all words in all the messages which will be used, __\( \mathcal{N}_0 \)__ is the set of all the words in all the resulting cryptograms, __\( T \)__ is a non-singular mapping on __\( \mathcal{M}_0 \)__ to __\( \mathcal{N}_0 \)__.

In describing cipher systems where more of a cipher system is to be
given by the formula and less by auxiliary mapping, the nature of the
components __\( u_j \)__ of the cryptogram __\eqref{eq-04}__ may depend both on
the nature of __\( x_i \)__ in __\( x \)__ and also on its position in the message,
which we have indicated by its subscript __\( i \)__. But then a formula
describing the cipher system would depend upon the length __\( n \)__ of the
message __\( x \)__, and we are studying *formulas* independent of __\( x \)__.
We may achieve our end, however, by the adjunction of new components,
which are nulls, to bring up the number of components to a fixed
maximum prescribed in advance. It may also be achieved in a somewhat
more practical way by the use of __\eqref{eq-05}__ and the fact that
each __\( x_i \)__ may itself be regarded as being a message, the set of all
messages to considered is now the set __\( \mathcal{M}_0 \)__ or our
components, __\( T \)__ is a cipher system. But we may prescribe a
partitioning of __\( x \)__. If we then define components for our message so
that each component __\( x_i \)__ permits a further subdivision into
subcomponents
__\( x_{i_1}, \dots \)__, __\( x_{i_{\nu}} \)__,
with __\( \nu \)__ the same for
each __\( i \)__, the cipher system __\( T \)__ will operate on messages all of the
same number of components.

We have now seen how to limit our study to cipher systems on
messages __\eqref{eq-03}__ for a fixed __\( n \)__, and we shall do this.

#### 4. Transposition ciphers

A transposition cipher is simply a cipher system given by __\eqref{eq-03}__ and
__\begin{equation}
S(x) = \bigl[ x_{i_1}, x_{i_2}, \dots , x_{i_n} \bigr],
\label{eq-06}
\end{equation}__
where __\( i_1, \dots, i_n \)__ is any permutation (i.e., rearrangement) of
the integers __\( 1,2,\dots , n \)__. This may be accomplished most
effectively in the general case by simply writing the message and the
permutation and then reading off the cryptogram in the form:
__\begin{equation}
\begin{array}{r cccc}
\textrm{Plain Text} \qquad &
x_1 & x_2 & \dots& x_n
\cr\cr
\smash{\raise-1.5ex\hbox{Cipher System}} \qquad &
1 & 2 & \dots & n
\cr
& i_i & i_2 & \dots & i_n
\cr\cr
\textrm{Cryptogram} \qquad
& x_{i_1} & x_{i_2} & \dots & x_{i_n}
\end{array}
\label{eq-07}
\end{equation}__

To decipher such as message, we read *up* in the cipher system to obtain its inverse, and then have:
__\begin{equation}
\begin{array}{r cccc}
\textrm{Cryptogram}\qquad &
u_1 & u_2 & \dots & u_n,
\cr\cr
\smash{\raise-1.5ex\hbox{Inverse Cipher}}\qquad &
1 & 2 & \dots & n
\cr
& j_i & j_2 & \dots & j_n
\cr\cr
\textrm{Message}\qquad &
u_{j_1} & u_{j_2} & \dots & u_{j_n}
\end{array}
\label{eq-08}
\end{equation}__
For example, we may write:
__\[
\begin{array}{ r rrrrrrrrrrrrrrrr }
\textrm{Plain Text}\quad
& I & N & T & H & A & T & P & R & E & C & E & D & I & N & G
\cr\cr
\smash{\raise-1.5ex\hbox{Cipher System}}\quad
& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 &
\cr
& 7 & 11 & 5 & 1 & 8 & 13 & 14 & 9 & 15 & 2 & 6 & 10 & 12 & 4 & 3 \cr\cr
\textrm{Cryptogram}\quad
& P & E & A & I & R & I & N & E & G & N & T & C & D & H & T
\cr\cr
\smash{\raise-1.5ex\hbox{Inverse System}}\quad
& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 &
\cr
& 4 & 10 & 15 & 14 & 3 & 11 & 1 & 5 & 8 & 12 & 2 & 13 & 6 & 7 & 9 \end{array}
\]__
which we apply to obtain the original message.

There are many devices for accomplishing transformations of this kind but none of them can do more than what we have indicated above. They may need to be studied in cryptanalysis but surely are not worthwhile additions to cryptography. It would seem that their only possible value in this latter subject is that they may be relatively easy to remember. However, the most primitive of them are worthless, and the more complicated ones are not as easy to remember as the following device.

Let us memorize any sentence and write it with a number below each
letter from 1 to the number __\( n \)__ of letters in the sentence. We then
put numbers below those according to the alphabetical order of the
letters, giving repeated letters consecutive numbers. The
transposition cipher system obtained in this way may be written down
rapidly, and is usually much more general in its structure than those
special systems in common use. For example, we have
__\begin{align*}
&
\begin{array}{ r rr | rrrrrr | rrrrrr }
\textrm{Key}\quad
& A & N & E & F & F & O & R & T & S & H & O & U &
L & D
\cr\cr
\smash{\raise-1.5ex\hbox{Cipher}} \quad
& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14
\cr
& 1 & 14 & 6 & 9 & 10 & 15 & 17 & 19 & 18 & 11 &16 & 20 & 12 & 4
\end{array}
\\
\\
&
\begin{array}{ r rr | rrrr}
\textrm{Key}\quad
& B & E & M & A & D & E
\cr\cr
\smash{\raise-1.5ex\hbox{Cipher}} \quad
& 15 & 16 & 17 & 18 & 19 & 20
\cr
& 3 & 7 & 13 & 2 & 5 & 8
\end{array}
\end{align*}__

#### 5. Products of cipher systems

If __\( S \)__ is a non-singular mapping __\( x \mapsto u = S(x) \)__ on
__\( \mathcal{M} \)__ to a set __\( \mathcal{N} \)__ and __\( T \)__ is a non-singular mapping
__\( u \mapsto T(u) \)__ on __\( \mathcal{N} \)__ to a set __\( \mathcal{L} \)__ the
correspondence
__\begin{equation}
x \longmapsto V(x) = T[ S(x) ]
\label{eq-09}
\end{equation}__
is a non-singular mapping __\( V \)__ on __\( \mathcal{M} \)__ to __\( \mathcal{L} \)__.
However, it may be more convenient to compute __\( V(x) \)__ by first
computing __\( u = S(x) \)__, and then __\( T(u) \)__, rather than __\( V(x) \)__ directly. We
shall call __\( V \)__ the *product* __\( ST \)__ of the mappings __\( S \)__ and __\( T \)__.

In cryptography it is frequently possible to think of cryptograms
themselves as being messages, and thus study cipher systems which are
non-singular mappings on __\( \mathcal{M} \)__ to __\( \mathcal{M} \)__. But then the
product __\( ST \)__ of a cipher system __\( S \)__ by a cipher system __\( T \)__ is another
cipher system.

It is also possible frequently to *break down* a cipher system
into a product of simpler ones. This is usually done in analyzing
cipher systems, and much of our discussion will be concerned with a
description of these simpler systems rather than the more complicated
systems derivable from them by the product operation described above.

It should be observed that the operation of product of mappings is
associative, that is, __\( (ST)U = S(TU) \)__ for any three mappings __\( S \)__, __\( T \)__,
__\( U \)__. Indeed, both of these mappings are the same
correspondences
__\[ x \mapsto U \{ T[ S(x) ] \} .\]__
However the
operation is not commutative and indeed __\( TS \)__ may not even be defined.
But even if __\( S \)__ and __\( T \)__ are mappings on __\( \mathcal{M} \)__
to __\( \mathcal{M} \)__, so that __\( ST \)__ and __\( TS \)__ are also mappings
on __\( \mathcal{M} \)__ to __\( \mathcal{M} \)__, they may be different. For example,
let __\( \mathcal{M} \)__ consist of the symbols __\( 1,2,3 \)__; __\( S \)__ be the
correspondence
__\( 1 \mapsto 2 \)__,
__\( 2 \mapsto 3 \)__,
__\( 3 \mapsto 1 \)__;
__\( T \)__ be the correspondence
__\( 1 \mapsto 2 \)__,
__\( 2 \mapsto 1 \)__,
__\( 3 \mapsto 3 \)__.
Then __\( ST \)__ is given by
__\( 1 \mapsto 1 \)__,
__\( 2 \mapsto 3 \)__,
__\( 3 \mapsto 2 \)__,
and __\( TS \)__ by
__\( 1 \mapsto 3 \)__,
__\( 2 \mapsto 2 \)__,
__\( 3 \mapsto 1 \)__.

#### 6. The role of the ring in a cipher alphabet

It is frequently desirable in cryptography to use an intermediate set
__\( \mathcal{N} \)__ and so construct a cipher system __\( S \)__ as the product
__\( TUT^{-1} \)__, where __\( T \)__ is a non-singular mapping on the set
__\( \mathcal{M} \)__ of all messages to the intermediate set __\( \mathcal{N} \)__,
__\( U \)__ is a non-singular mapping on __\( \mathcal{N} \)__ to __\( \mathcal{N} \)__. Let
us then write
__\[
x = \bigl[ x_1, \dots, x_n \bigr],
\]__
for components __\( x_i \)__ of our messages __\( x \)__, and suppose that __\( T \)__ is such that
__\begin{equation}
u = T(x) = \bigl[ u_1, \dots, u_n \bigr],
\qquad u_i = T_0 (x_i).
\label{eq-10}
\end{equation}__
Here, __\( T_0 \)__ is a non-singular mapping on the set __\( \mathcal{M}_0 \)__ of all components of messages, to a set __\( \mathcal{N}_0 \)__ whose quantities are at our choice. Then __\( u \)__ is formed as the sequence above and we have
__\begin{equation}
T^{-1} (u) = \bigl[ T_0^{-1} (u_1), \dots , T_0^{-1} (u_n) \bigr].
\label{eq-11}
\end{equation}__
We apply a second transformation __\( U \)__ on __\( \mathcal{N} \)__ to __\( \mathcal{N} \)__ and have
__\begin{equation}
U(u) = \bigl[ v_1, \dots, v_n \bigr],
\label{eq-12}
\end{equation}__
so that
__\begin{equation}
S (x) = \bigl[ T_0^{-1} (v_1), \dots, T_0^{-1} (v_n) \bigr].
\label{eq-13}
\end{equation}__
Let us call the set __\( \mathcal{N}_0 \)__, together with the mapping __\( T_0 \)__, a *cipher alphabet*.

The cipher alphabet is introduced to simplify the description of __\( S \)__.
In particular we may use a mathematical number system __\( \mathcal{A} \)__ for the
set __\( \mathcal{N}_0 \)__ and so have a set __\( \mathcal{N}_0 \)__ in which addition and
multiplication of its quantities are defined. It may then be a very simple
matter to give formulas for the mapping __\( U \)__ and to give __\( T_0 \)__ explicitly.
However the consequent description of __\( S \)__ in terms of messages alone would
usually be extremely complicated.

The only sets __\( \mathcal{A} \)__ of which we shall use are the sets called
*commutative rings*: A *ring* __\( \mathcal{A} \)__ is a set of
quantities for which the sum __\( a + b \)__ and the product __\( ab \)__ of any __\( a \)__ and __\( b \)__
in __\( \mathcal{A} \)__ are quantities of __\( \mathcal{A} \)__ such that
__\begin{align}
& a + b = b + a, \quad (a+b) +c = a + (b + c), \quad a(bc) = (ab)c,
\label{eq-14}
\\
& a (b + c) = ab + ac, \quad (b+c)a = ba + ca,
\label{eq-15}
\end{align}__
for every __\( a \)__, __\( b \)__, and __\( c \)__ of __\( \mathcal{A} \)__. Moreover we assume that
for every __\( a \)__ and __\( b \)__ of __\( \mathcal{A} \)__ there is a unique solution __\( x \)__
in __\( \mathcal{A} \)__ of the equation
__\begin{equation}
a + x = b.
\label{eq-16}
\end{equation}__
We call __\( \mathcal{A} \)__ a commutative ring if it is also true that
__\begin{equation}
ab = ba
\label{eq-17}
\end{equation}__
for every __\( a \)__ and __\( b \)__ of __\( \mathcal{A} \)__.

In every ring, there is a unique zero quantity 0 such that
__\begin{equation}
a + 0 = a,
\label{eq-18}
\end{equation}__
for every __\( a \)__ of __\( \mathcal{A} \)__, and a unique quantity __\( -{a} \)__, called the
negative of __\( a \)__, such that
__\begin{equation}
a + (-{a}) = 0.
\label{eq-19}
\end{equation}__
Then in __\eqref{eq-15}__ we have __\( x = b + (-{a}) \)__. It can be shown that
the properties we have assumed imply that __\( -{(-{a})} = a \)__, __\( (-{a})b =
a(-{b}) = -{(ab)} \)__, __\( (-{a})(-{b}) = ab \)__ for all quantities __\( a \)__ and __\( b \)__
of __\( \mathcal{A} \)__.

The familiar number systems consisting of all rational numbers, of all
real numbers, and of all complex numbers are examples of commutative rings.
These rings are all *fields*, that is, commutative rings __\( \mathcal{A} \)__
with the property that if __\( a \)__ and __\( b \)__ are in __\( \mathcal{A} \)__ and __\( a \)__ is not
zero there is a unique solution __\( x \)__ in __\( \mathcal{A} \)__ of the equation
__\begin{equation}
a x = b.
\label{eq-20}
\end{equation}__
This quotient __\( x \)__ has a property like the difference __\( x = b - a \)__ which is
the solution of __\eqref{eq-15}__. First there is a *unity quantity* 1
in __\( \mathcal{A} \)__ such that
__\begin{equation}
1 a = a 1 = a,
\label{eq-21}
\end{equation}__
for every quantity __\( a \)__ of __\( \mathcal{A} \)__. Also every __\( a \ne 0 \)__ has a unique
inverse __\( a^{-1} \)__ such that
__\begin{equation}
a a^{-1} = a^{-1} a = 1,
\label{eq-22}
\end{equation}__
and then __\( x = b a^{-1} \)__.

The set of all integers, and the set of all polynomials __\( f(\lambda) \)__ in
a symbol __\( \lambda \)__ with rational coefficients, are both commutative rings
with a unity quality. But they are not fields.

#### 7. Residue class rings in cipher alphabets

Let us now suppose that the components __\( x_i \)__ of a message __\( x \)__ in its
representation __\eqref{eq-03}__ as sequence, are letters of the alphabet,
and perhaps other similar symbols like periods or commas. Then, the
set __\( \mathcal{M}_0 \)__ of all possible components is a finite set and we shall
wish to map it on a ring __\( \mathcal{N}_0 \)__, also with a finite number of
quantities. Let us then proceed to define certain very simple finite rings.

The quantities of our new rings will not be ordinary integers but
*classes* of integers. The reader is already familiar with the
classification of integers into two classes, namely, the class of all even
integers, and the class of all odd integers. For these classes we have
the rules that
__\begin{align*}
& \text{even} + \text{even} = \text{even},\\
& \text{even} + \text{odd} = \text{odd} + \text{even} = \text{odd},\\
& \text{even} \times \text{odd} =\text{odd}\times\text{even}= \text{even},\\
& \text{odd} \times \text{odd} = \text{odd}.
\end{align*}__
Then we may represent the class of all even integers by 0, the class of
all odds by 1, and we have a ring of two elements with the laws
__\begin{align}
&
0 + 0 = 0 = 1 + 1, \qquad 1 + 0 = 0 + 1 = 1,
\notag
\\
&
0 \cdot 0 = 0 \cdot 1 = 1 \cdot 0 = 0,
\qquad 1 \cdot 1 = 1.
\label{eq-23}
\end{align}__

We shall define similarly a ring
__\[
A_m
\]__
of __\( m \)__ classes of ordinary integers, for every fixed integer __\( m > 1 \)__. If __\( a \)__
is any integer there are integers __\( q \)__ and __\( r \)__ such that
__\begin{equation}
a - q m = r,
\label{eq-24}
\end{equation}__
where the remainder __\( r \)__ is one and only one of the integers
__\begin{equation}
0,1,2,\dots,m-1.
\label{eq-25}
\end{equation}__
Let us call two integers __\( a \)__ and __\( b \)__ *congruent* and write
__\begin{equation}
a \equiv b,
\label{eq-26}
\end{equation}__
if the corresponding remainders are the same. Then __\( a \equiv 0 \)__ if and
only if __\( a \)__ is a multiple of __\( m \)__, __\( a \equiv b \)__ if and only if __\( a - b = 0 \)__.

Let us now put all integers into a set of *residue classes*, each
of which will be designated by __\( \{a\} \)__. Here __\( a \)__ is any integer of the
class, __\( \{a\} = \{b\} \)__ if any only if __\( a \equiv b \)__. It is clear that there
are __\( m \)__ classes and that they are precisely the classes
__\[
\{0\}, \{1\}, \dots , \{ m - 1\},
\]__
where if __\( r \)__ has any of the values __\( 0,1, \dots, m-1 \)__, the set __\( \{r\} \)__
consists of all integers differing from __\( r \)__ by a multiple of __\( m \)__.

It is a simple matter to verify the identities
__\begin{align*}
(a + c) - ( b + d) &= (a - b) + (c - d),
\cr
a c - b d &= (a - b) (c - d) + [ d (a - b) + b (c - d) ].
\end{align*}__
They imply that if __\( a \equiv b \)__ and __\( c \equiv d \)__ then __\( a + c \equiv b
+ d \)__, __\( ac\equiv bd \)__. But it follows that __\( \{a + c \} \)__ and __\( \{ a c \} \)__ are uniquely
determined for every two classes __\( \{a \}, \{ c \} \)__ and we define
__\[
\{ a \} + \{ c \} = \{ a + c \}, \qquad \{ a \} \{ c \} = \{ a c \}.
\]__
The set __\( \mathcal{A}_m \)__ of our residue classes is now known to be a
commutative ring.

In actual use we omit the braces and compute with integers in the normal
way but always drop off multiples of __\( m \)__. We need not use __\( 0,1,\dots \)__, __\( m - 1 \)__ as a set of remainders but may choose any other __\( m \)__ integers
providing that there is one and only one from each class. For example,
let us study __\( \mathcal{A}_{26} \)__.

To facilitate computations we use the table of products __\( q \cdot 26 \)__, __\( q =
2,3,\dots \)__, 25, which is given by
__\begin{align*}
&
52, 78, 104, 130, 156, 182, 208, 234, 260, 286, 312, 338,
\\
&
364, 390, 416, 442, 468, 494, 520, 546, 572, 598, 624, 650.
\end{align*}__
To use __\( \mathcal{A}_{26} \)__, we set up a cipher alphabet as a mapping
__\begin{align}
&
\begin{array}{ rrrrr c rrrrr c rrrrr}
A & B & C & D & E &\ & F & G & H & I & J &\ & K & L & M & N & O
\cr
1 & 2 & 3 & 4 & 5 && 6 & 7 & 8 & 9 & 10 && 11 & 12 & 13 & 14 & 15
\end{array}
\notag
\\
\notag
\\
&
\begin{array}{rrrrr c rrrrr c r }
P & Q & R & S & T &\ & U & V & W & X & Y &\ & Z
\cr
16 & 17 & 18 & 19 & 20 && 21 & 22 & 23 & 24 & 25 && 26
\end{array}
\label{eq-27}
\end{align}__
We may now add and multiply integers as usual providing neither sum
nor product exceeds 26. Then __\( 3 + 5 = 9 \)__, __\( 3 \cdot 5 = 15 \)__.
However, __\( 15 + 19 = 34 \equiv 8 \)__, and so if we replace 0 and __\( S \)__ by
what we may call their sum, this sum would be __\( H \)__. Similarly __\( 15
\cdot 19 = 285 \equiv 25 \)__ by the table above, and this corresponds
to __\( Y \)__.

#### 8. The finite field in the construction of cipher systems

We shall construct cipher systems as in equations __\eqref{eq-10}__,
__\eqref{eq-11}__, __\eqref{eq-12}__, __\eqref{eq-13}__, where the set __\( \mathcal{N}_0 \)__
of components __\( u_1 \)__ will be a finite ring
and the mapping __\( U \)__ will be defined by algebraic expressions for the
components __\( v_1, \dots \)__, __\( v_n \)__ of __\( U(u) \)__ in terms of the components __\( u_1,
\dots \)__, __\( u_n \)__ of __\( u \)__. A special instance of such a cipher system is that
where __\( \mathcal{N}_0= A_{26} \)__,
__\begin{equation}
U (u) = \bigl[ a u_1, \dots , a u_n \bigr],
\label{eq-28}
\end{equation}__
for any non-zero quantity of __\( \mathcal{A}_{26} \)__. If __\( a \)__ is the class __\( \{
3 \} \)__ of __\( \mathcal{A}_{26} \)__ our cipher system replaces every letter of our
message by a corresponding letter, such that __\( \mathrm{A}, \dots, \mathrm{Z} \)__
correspond, respectively, to
__\begin{equation}
CFILO\ \ RUXAD\ \ GJMPS\ \ VYBEH\ \ KNQTW\ \ Z.
\label{eq-29}
\end{equation}__
If we attempted to construct the similar mapping with __\( a = \{ 2 \} \)__ we
would replace __\( \mathrm{A}, \dots \mathrm{Z} \)__, respectively, by
__\begin{equation}
BDFHJ\ \ LNPRT\ \ VXZBD\ \ FHJLN\ \ PRTVX\ \ Z,
\label{eq-30}
\end{equation}__
and so the mapping would not be non-singular.

The fact that the cipher system just described is singular arises from the
property that the mappings
__\begin{equation}
x \mapsto a x \quad (x\text{ in }\mathcal{A}),
\label{eq-31}
\end{equation}__
defined for each __\( a \ne 0 \)__ of __\( \mathcal{A} \)__, are singular for some
quantities __\( a \)__ of __\( \mathcal{A}_{26} \)__. Such a mapping is non-singular
for a given __\( a \ne 0 \)__ if it is true that for every __\( b \)__
of __\( \mathcal{A} \)__, there is a solution __\( x \)__ in __\( \mathcal{A} \)__ of the
equation __\eqref{eq-20}__. But then the mappings __\eqref{eq-31}__
of __\( \mathcal{A} \)__ on __\( \mathcal{A} \)__ are all non-singular for __\( a \ne 0 \)__
of __\( \mathcal{A} \)__ if and only if __\( \mathcal{A} \)__ is a field.

The finite rings __\( \mathcal{A}_m \)__ with __\( m = s t \)__ for positive
integers __\( s > 1 \)__, __\( t > 1 \)__ are not fields. This follows since __\( \{ s \}
\{ t \} = \{0 \} \)__, the existence of a solution __\( x \)__ of __\( \{ t \} x =
\{ 1 \} \)__ would imply that
__\( \{s \} \{ t \} x = \{ s \} = \{ 0 \} x = \{ 0 \} \)__. The
rings __\( \mathcal{A}_m \)__ with __\( m \)__ a *prime* integer are fields and two
instances of such rings important for our use are
__\begin{equation}
A_{29}, A_{31}.
\label{eq-32}
\end{equation}__
Let us now set up the cipher alphabet given by __\( \mathcal{A}_{29} \)__ and the
correspondence
__\begin{align}
&
\begin{array}{ rrrrr c rrrrr c rrrrr}
A & B & C & D & E &\ & F & G & H & I & J &\ & K & L & M & N & O
\cr
1 & -1 & 2 & -2 & 3 && -3 & 4 & -4 & 5 & -5 && 6 & -6 & 7 & -7 & 8
\end{array}
\notag
\\
\notag
\\
&
\begin{array}{rrrrr c rrrrr c rrrr }
P & Q & R & S & T &\ & U & V & W & X & Y &\ & Z & , & . & -
\cr
-8 & 9 & -9 & 10 & -10 && 11 & -11 & 12 & -12 & 13 && -13 & 14 & -14 & 0
\end{array}
\label{eq-33}
\end{align}__
We shall use the table of products __\( q \cdot 29 \)__ for __\( q = 2, \dots, 14 \)__,
given by
__\[
58, 87, 116, 145, 174, 203, 232, 261, 290, 319, 348, 377, 405.
\]__
Then we see that the cipher system defined by the mapping __\( x \mapsto \{3\}
x \)__ of __\( \mathcal{A} \)__ on __\( \mathcal{A} \)__ sets up a correspondence of __\( \mathrm{A}
, \dots, \mathrm{Z} \)__, respectively, to
__\begin{equation}
EFKLQ\ \ RWX.,\ \ VUPOJ\ \ IDCAB\ \ GHMNS\ \ TYZ-
\label{eq-34}
\end{equation}__
Here we have used properties contained in the set of congruences
__\begin{alignat*}{4}
28 &\equiv -1,&\quad
27 &\equiv -2,&\quad
26 &\equiv -3,&\quad
25&\equiv -4,
\\
24 &\equiv -5,&\quad
23 &\equiv -6,&\quad
22 &\equiv -7,&\quad
21 &\equiv -8,
\\
20 &\equiv -9,&\quad
19 &\equiv -10,&\quad
18 &\equiv -11,&\quad
17 &\equiv -12,
\\
16 &\equiv-13,&\quad
15 &\equiv -14&\quad
\rlap{\text{ modulo } 29.}
\end{alignat*}__

There are also other finite fields obtained from our finite
fields __\( \mathcal{A}_m \)__, where __\( m \)__ is a prime. Such fields are the sets of
polynomials of the form
__\[
a_0 + a_1 \alpha + a_2 \alpha^2 + \cdots + a_t \alpha^{t-1} \quad
(a_0, \dots, a_t \text{ in }\mathcal{A}_m),
\]__
where __\( \alpha \)__ is a root of an equation __\( f(x) = 0 \)__ of degree __\( t \)__, coefficients
in __\( \mathcal{A}_m \)__, and not factoring in __\( \mathcal{A}_m \)__. Then __\( \alpha \)__
is a primitive __\( (q - 1) \)__-st root of unity, __\( q = m^t \)__ is the number
of elements in this field. We designate such fields by
__\begin{equation}
G F (m^t)
\label{eq-35}
\end{equation}__
(read __\( G \)__, __\( F \)__, __\( m^t \)__), and call such a field a Galois field of __\( m^t \)__
quantities. There are no other finite fields.

The fields __\( \mathcal{A}_m = GF(m) \)__, __\( t=1 \)__. Another important example is
the field __\( GF(3^3) \)__ of 27 elements. Then its quantities are sums
__\begin{equation}
a_0 + a_1 \alpha + a_2 \alpha^2,
\label{eq-37}
\end{equation}__
where __\( a_i = \{ 0 \}, \{ 1 \}, \{2 \} \,\text{modulo } 3 \)__,
__\begin{equation}
\alpha^3 = \alpha + 1.
\end{equation}__

#### 9. Simple and multiple alphabet substitution ciphers

A *substitution cipher* is a non-singular mapping
__\begin{equation}
x = \bigl[ x_1, \dots , x_n \bigr]
\longmapsto
S(x) = \bigl[ u_1, \dots, u_n \bigr],
\label{eq-38}
\end{equation}__
where the __\( x_i \)__ are the *letters* or other symbols of our
message, and the __\( u_1 \)__ are the corresponding symbols determined
by __\( S \)__. An important type of substitution cipher is a non-singular
mapping of the type above in which
__\begin{equation}
S(x) = \bigl[ T_1 (x_1) , \dots , T_n (x_n) \bigr],
\label{eq-39}
\end{equation}__
for non-singular mappings __\( T_i \)__ on __\( \mathcal{M}_0 \)__ to __\( \mathcal{M}_0 \)__,
where __\( \mathcal{M}_0 \)__ is the set of symbols we are using. Thus the
mappings __\( T_i = T \)__ given by __\eqref{eq-29}__, __\eqref{eq-34}__ define
such substitution ciphers. Let us also use any finite
ring __\( \mathcal{A} \)__ in a cipher alphabet which is a non-singular
mapping
__\begin{equation}
x_i \mapsto y_i,
\label{eq-40}
\end{equation}__
on __\( \mathcal{M}_0 \)__ to __\( \mathcal{A} \)__. Then the mappings
__\begin{equation}
T_i: y_i \longmapsto a_i y_i + b_i \quad (i = 1, \dots , n)
\label{eq-41}
\end{equation}__
on __\( \mathcal{A} \)__ to __\( \mathcal{A} \)__ are non-singular for every __\( b_i \)__
in __\( \mathcal{A} \)__ and every non-zero __\( a_i \)__ in __\( \mathcal{A} \)__. It follows that
the cipher systems defined by __\eqref{eq-38}__, __\eqref{eq-39}__, __\eqref{eq-40}__,
__\eqref{eq-41}__ are definable as follows. Replace each letter of our message
of __\( n \)__ letters by a corresponding “number” of the ring __\( \mathcal{A} \)__
determined by __\eqref{eq-40}__. Multiply the __\( i \)__-th such number by
the fixed non-zero number __\( a_i \)__ in __\( \mathcal{A} \)__, add the fixed __\( b_i \)__,
and then replace the result by the corresponding letter determined also
by __\eqref{eq-40}__. Such ciphers are usually called *multiple alphabet*
ciphers and are called *simple* or *monoalphabet* ciphers if the
transformations __\eqref{eq-41}__ are all the same, that is, if
__\begin{equation}
y_i \mapsto a y + b \quad (i = 1, \dots , n).
\label{eq-42}
\end{equation}__

#### 10. Special multiple alphabet substitution ciphers

The so-called *Caesar* cipher is the case where __\eqref{eq-41}__ is given by
__\begin{equation}
y_i \mapsto y_i + b,
\label{eq-43}
\end{equation}__
for __\( b \)__ fixed. If we use __\( \mathcal{A}_{26} \)__ and use __\eqref{eq-27}__ for
the mapping __\eqref{eq-40}__ of the Roman letters on the quantities of our
ring then __\( b \)__ is a class __\( \{ r \} \)__ defined for __\( r = 0, 1, \dots \)__, 25
and every letter __\( x \)__ is replaced by a letter obtained by shifting it __\( r \)__
units in the sequence
__\( A, \dots \)__, __\( Z \)__ of which it is a member.

The *Vigenère*, *Gronsfield*, *Porta*, and *Beaufort*
cipher systems are all variants of our cipher systems determined
by __\eqref{eq-27}__, the use of __\( \mathcal{A}_{26} \)__, and __\eqref{eq-41}__ for __\( a_i
\ne \pm 1 \)__. In the original Vigenère, we use the form
__\begin{equation}
y_i \mapsto y_i + b_i \quad (i = 1, \dots , n)
\label{eq-44}
\end{equation}__
of __\eqref{eq-41}__, where __\( b_i = \{ r_i \} \)__ for __\( r_i \)__ one of __\( 0, 1, \dots \)__, 25,
and we carry each set of __\( n \)__ letters __\( x_i \)__ of our messages to corresponding
letters __\( z_1 , \dots \)__, __\( z_n \)__. Here we obtain the letter __\( z_i \)__ by a shift
of __\( r_i \)__ letters in the alphabet on the letter __\( x_i \)__. The amount of shift
depends on __\( i \)__. Thus, a key word of __\( n \)__ symbols __\( g_1 , \dots \)__, __\( g_n \)__ may
be given, we carry each letter __\( g_i \)__ to a corresponding residue class __\( \{
r_i \} \)__, we use __\( \{ 26 \} = \{ 0 \} \)__, we have __\( 0 \leqq r_i < 26 \)__, and we
shift __\( r_i \)__ letters.

The *Saint-Cyr* cipher is also a true Vigenère cipher and its
mechanism need not be described. The Gronsfield ciphers differs only from
the Vigenère in that __\( r_1 , \dots \)__, __\( r_n \)__ are given rather than the key word.
The so-called *true Beaufort* is the cipher system determined by
__\begin{equation}
y_i \longmapsto z_i = y_i - b_i \quad (i = 1, \dots , n),
\label{eq-45}
\end{equation}__
where __\( b_i = \{ r_i \} \)__, each __\( r_i \)__ lies between 0 and 25, and we
shift __\( r_i \)__ letters backward in the alphabet. Mathematically this
is identical with the Vigenère but with a different cipher system.
The so-called *modified* Vigenère and Beaufort systems are given by
__\begin{equation}
y_i \longmapsto z_i = -{y_i} + b_1 \quad (i = 1, \dots , n),
\label{eq-46}
\end{equation}__
and
__\begin{equation}
y_i \longmapsto z_i = -y_i - b_i \quad (i = 1, \dots , n),
\label{eq-47}
\end{equation}__
respectively, and are mathematically identical.

The Porta cipher is fundamentally the Vigenère but with the cipher
alphabet given by
__\begin{align}
&
\begin{array}{ rrrrr c rrrrr c rrrrr}
A & B & C & D & E &\ & F & G & H & I & J &\ & K & L & M & N & O
\cr
1 & 2 & 3 & 4 & 5 &\ & 6 & 7 & 8 & 9 & 10 &\ & 11 & 12 & 13 & -1 & -2
\end{array}
\notag
\\
\notag
\\
&
\begin{array}{rrrrr c rrrrr c r}
P & Q & R & S & T &\ & U & V & W & X & Y &\ & Z
\cr
-3 & -4 & -5 & -6 & -7 &\ & -8 & -9 & -10 & -11 & -12 &\ & -13
\end{array}
\label{eq-48}
\end{align}__

#### 11. Autoencipherment

A *polygram* substitution cipher is a cipher system given by the use
of a cipher alphabet and non-singular mapping
__\[ y = \bigl[ y_1, \dots , y_n \bigr]
\longmapsto
T(y) = \bigl[z_1 , \dots, z_n \bigr] ,\]__
where each __\( z_j \)__ is a function of
all the __\( y_i \)__ rather than a single __\( y_i \)__. A special case of such a system
is that given by
__\begin{equation}
z_i = y_i + b_i \quad (i = 1, \dots , s),
\label{eq-49}
\end{equation}__
and by
__\begin{equation}
z_i = y_i + y_{i-s} \quad (i = s+1, \dots , n),
\label{eq-50}
\end{equation}__
for some fixed __\( s < n \)__. Thus it results from a shift of __\( r_i \)__ units for
the first __\( s \)__ letters and is a Vigenère for this part, and by *a
shift dependent on the message itself* for the remaining letters in each
group of __\( n \)__ letters.

#### 12. The cipher systems of Hill

Let us suppose that a cipher alphabet involving a finite ring __\( \mathcal{A} \)__
has been prescribed and thus that we may replace any sequence of __\( n \)__
symbols of a message
by a sequence
__\begin{equation}
y = \bigl[ y_1, \dots , y_n \bigr]
\label{eq-51}
\end{equation}__
of quantities of __\( y_i \)__ of the ring __\( \mathcal{A} \)__. We assume that __\( n^2 \)__
quantities __\( a_{ij} \)__ in __\( \mathcal{A} \)__ are given as well as __\( n \)__ other
quantities __\( g_1, \dots \)__, __\( g_n \)__ in __\( \mathcal{A} \)__ and let __\( z_j \)__ be given by
__\begin{equation}
z_j = y_1 a_{1j} + y_2 a_{2j} + \cdots + y_n a_{nj} + g_j
\label{eq-52}
\end{equation}__
for __\( j = 1, \dots \)__, __\( m \)__. Then the mapping defined by
__\begin{equation}
y \longmapsto z = \bigl[ z_1, \dots , z_m \bigr]
\label{eq-53}
\end{equation}__
is a non-singular mapping if the quantities __\( a_{ij} \)__ are such that it is
possible to solve for the __\( y_i \)__ uniquely in terms of the __\( z_j \)__. This occurs
if __\( m = n \)__ and there exist quantities __\( b_{ji} \)__ in __\( \mathcal{A} \)__ such that
__\begin{equation}
y_i = z_1 b_{1 i} + \cdots + z_n b_{n i} + h_i \quad (i = 1,
\dots , n),
\label{eq-54}
\end{equation}__
where
__\begin{equation}
h_i = -( g_1 b_{1 i} + \cdots + g_n b_{n i} ) \quad
(i = 1, \dots , n).
\label{eq-55}
\end{equation}__

If __\( \mathcal{A} \)__ is any commutative ring with a unity quantity 1
the elementary theory of systems of linear equations and determinants is
applicable. Its results imply that the mapping __\eqref{eq-53}__ is non-singular
if and only if the determinant
__\begin{equation}
d = \begin{vmatrix}\mkern5mu
a_{11} & a_{12} & \cdots & a_{1 n}
\cr
a_{21} & a_{22} & \cdots & a_{2 n}
\cr
\vdots & \vdots & \cdots & \vdots
\cr
a_{n 1} & a_{n 2} & \cdots & a_{nn}
\mkern5mu
\end{vmatrix}
\label{eq-56}
\end{equation}__
has an inverse __\( d^{-1} \)__ in __\( \mathcal{A} \)__ such that __\( d d^{-1} = 1 \)__. Then it
is possible to give explicit formulas for the __\( b_{ji} \)__ in terms of __\( d^{-1} \)__
and the __\( n - 1 \)__ rowed minors of the array of which __\( d \)__ is the determinant.
In particular, if __\( \mathcal{A} \)__ is a field, the mapping __\eqref{eq-53}__ is a
non-singular if and only if __\( d \ne 0 \)__. Also __\eqref{eq-53}__ is non-singular
when __\( \mathcal{A} \)__ is the residue-class ring modulo __\( m \)__ if and only if the
residue class __\( d = \{ r \} \)__ for a representative integer __\( r \)__ prime to __\( m \)__.

It must be evident by now that the common substitution ciphers of
Sections 10 and 11 are all special cases
of the systems given by the use of __\eqref{eq-53}__, __\eqref{eq-52}__.
The general transposition cipher alphabet is also such a special case,
for we use a cipher alphabet with __\( \mathcal{A} = \mathcal{A}_{26} \)__ and thus replace
each sequence __\( x = [x_1, \dots \)__, __\( x_n] \)__ of __\( n \)__ letters by a sequence __\( y =
[ y_1, \dots \)__, __\( y_n ] \)__ of __\( n \)__ residue classes. We use a permutation __\( P \)__
replacing __\( x \)__ by __\( [x_{i_1}, \dots \)__, __\( x_{i_n} ] \)__ and have our result if
we can use __\eqref{eq-52}__ to obtain __\( z= [y_{i_1}, \dots \)__, __\( y_{i_n} ] \)__.
This may be accomplished when we take the __\( g_i \)__ all zero, the __\( a_{i_j}
= \{ 0 \} \)__ for all values of __\( i \)__ and __\( j \)__ except those where __\( i = i_j \)__
in which case __\( a_{i_j} = \{ 1 \} \)__.

#### 13. The Hill systems in matrix form

A rectangular array
__\begin{equation}
A = \begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1t}
\cr
a_{21} & a_{22} & \cdots & a_{2t}
\cr
\vdots & \vdots & \ddots & \vdots
\cr
a_{s 1} & a_{s 2} & \cdots & a_{st}
\end{pmatrix}
\label{eq-57}
\end{equation}__
is called an __\( s \)__ by __\( t \)__ matrix. It has __\( s \)__ rows and __\( t \)__ columns of
elements in a ring __\( \mathcal{A} \)__ and the element __\( a_{ij} \)__ is that
element in its __\( i \)__-th row and __\( j \)__-th column. Then we may
replace __\eqref{eq-57}__ by the abbreviated notation
__\begin{equation}
A = (a_{ij}) \quad (i = 1, \dots, s; j = 1, \dots, t).
\label{eq-58}
\end{equation}__

For every two __\( s \)__ by __\( t \)__ matrices __\( A \)__ and
__\begin{equation}
B = (b_{ij}) \quad (i = 1, \dots, s; j = 1, \dots, t),
\label{eq-59}
\end{equation}__
we define
__\begin{equation}
A + B = (c_{ij}), \quad c_{ij} = a_{ij} + b_{ij} \quad (i = 1, \dots,
s; j = 1, \dots, t).
\label{eq-60}
\end{equation}__
Similarly __\( A - B \)__ is defined so as to have __\( a_{ij} - b_{ij} \)__ in
the __\( i \)__-th row and __\( j \)__-th column.

We now let
__\begin{equation}
Y = (y_{k i} ) \quad (k = 1, \dots, r; \,i = 1, \dots, s)
\label{eq-61}
\end{equation}__
be any __\( r \)__ by __\( s \)__ matrix. Then we define the *product*
__\begin{equation}
W = Y \!A = (w_{kj}) \quad (k = 1, \dots, r;\, j = 1, \dots, t)
\label{eq-62}
\end{equation}__
to be the __\( r \)__ by __\( t \)__ matrix whose element in the __\( k \)__-th row and __\( j \)__-th
column is given by
__\begin{equation}
w_{kj} = y_{k1} a_{1 j} + y_{k2} a_{2 j} + \cdots + y_{k s}
a_{s j}.
\label{eq-63}
\end{equation}__

Equations __\eqref{eq-52}__ may be written by the use of matrices in a very
simple form. The sequences __\( y \)__ in __\eqref{eq-51}__ and __\( z \)__ in __\eqref{eq-53}__
are both one by __\( n \)__ matrices and we write __\( g = [g_1, \dots \)__, __\( g_m ] \)__. Let __\( A \)__
be the __\( n \)__ by __\( m \)__ matrix whose element in the __\( i \)__-th row and __\( j \)__-th column is
the coefficient __\( a_{ij} \)__ in our equations __\eqref{eq-52}__. Then __\eqref{eq-52}__
becomes
__\begin{equation}
z = y A + g.
\label{eq-64}
\end{equation}__
The identity mapping __\( y \mapsto z = y \)__ has the form __\eqref{eq-64}__ for __\( g
= [0,\dots \)__, __\( 0] \)__, __\( m = n \)__, and __\( A \)__ the matrix __\( I \)__ whose elements __\( a_{ij} \)__
are all zero, except that the __\( a_{ii} \)__ are all 1. Then __\eqref{eq-54}__
is given by
__\begin{equation}
y = ( z - g) B,
\label{eq-65}
\end{equation}__
where __\( AB = I, B \)__ is the matrix inverse of __\( A \)__.

One may now set up what appears to be a generalization of the
equations __\eqref{eq-52}__. We let
__\[
y = \bigl[ Y_1, \dots, Y_n \bigr]
\]__
for a set of __\( q \)__ by __\( s \)__ matrices __\( Y_i \)__. Let __\( A_{11}, \dots \)__, __\( A_{ij},
\dots \)__, __\( A_{nm} \)__ be a set of __\( s \)__ by __\( t \)__ matrices, __\( C_{11}, \dots \)__,
__\( C_{ji}, \dots \)__, __\( C_{mn} \)__ be a set of __\( r \)__ by __\( q \)__ matrices, __\( G_1,
\dots \)__, __\( G_m \)__ be a set of __\( r \)__ by __\( t \)__ matrices. Then each __\( C_{ji} Y_i
A_{ij} \)__ is an __\( r \)__ by __\( t \)__ matrix and so are the sums
__\begin{equation}
Z_j = C_{j1} Y_1 A_{1 j} + \cdots + C_{jn} Y_n A_{nj} +
G_j \quad (j=1,\dots, m).
\label{eq-66}
\end{equation}__
Nevertheless the mapping defined by __\eqref{eq-66}__ is only a
pseudogeneralization of __\eqref{eq-52}__ for __\( y \)__ may be regarded as being
a sequence of __\( nqs \)__ elements in __\( \mathcal{A} \)__, __\( z = [z_1, \dots \)__, __\( z_n] \)__,
as being a sequence of __\( m r t \)__ elements in __\( \mathcal{A} \)__, __\eqref{eq-66}__
can always be expressed in the form __\eqref{eq-52}__.

However, the form __\eqref{eq-66}__ may be more convenient to use
than __\eqref{eq-52}__. For example, a mapping on a sequence __\( [y_1, y_2, y_3,
y_4] \)__ involves the use of a four rowed matrix. However we may write this
sequence as a matrix
__\begin{equation}
Y = \biggl(\begin{array}{rr} y_1 & y_2 \cr y_3 & y_4 \end{array}\biggr),
\label{eq-67}
\end{equation}__
and then use the mappings defined as in __\eqref{eq-66}__ by the equation
__\begin{equation}
Z = CY\!A + G
\label{eq-68}
\end{equation}__
for two rowed square matrices __\( C \)__, __\( A \)__, __\( G \)__. The mapping is non-singular
if matrices __\( B \)__ and __\( D \)__ exist such that __\( A B = D C = I \)__,
__\begin{equation}
Y = D (Z - G) B.
\label{eq-69}
\end{equation}__
It is not as general as the mapping __\eqref{eq-52}__ but may be quite adequate
for actual use.

#### 14. Fractional substitutions

We have now seen how to carry a *sequence* of *letters* in a
message into a corresponding *array* of what we may call the
*numbers* of a ring and how to carry each such array into
another by the use of a system of linear equations returning to a
cryptogram consisting of a corresponding sequence of letters. This
may be complicated further by the use of non-linear equations and
such substitution cipher systems are known.4
Fractional cipher systems do not differ at all from the substitution cipher
systems already considered in respect to the nature of the mappings defined
by __\eqref{eq-52}__ but do differ in that a somewhat more complicated cipher
alphabet is used. We let __\( x = [x_1, \dots \)__, __\( x_s] \)__ be a message of __\( s \)__
letters and replace *each* letter by a *sequence* of __\( t \)__ quantities
of a ring __\( \mathcal{A} \)__ and thus __\( x \)__ by __\( y = [y_1, \dots \)__, __\( y_n] \)__ for __\( n
= s t \)__, the __\( y_i \)__ in __\( \mathcal{A} \)__. Clearly __\eqref{eq-52}__ replaces __\( y \)__
by a sequence __\( z \)__ in which elements arising from *parts* of sequences
corresponding to different letters may be combined. For example we set
up the mapping
__\[
\begin{array}{ccccccc}
A & B & C & D & E & F & G
\cr
(0,0,0) & (1,0,0) & (2,0,0) & (0,1,0) & (1,1,0) & (2,1,0)
& (0,2,0)
\cr\cr
H & I & J & K & L & M & N
\cr
(1,2,0) & (2,2,0) & (0,0,1) & (1,0,1) & (2,0,1) & (0,1,1)
& (1,1,1)
\cr\cr
O & P & Q & R & S & T & U
\cr
(2,1,1) & (0,2,1) & (1,2,1) & (2,2,1) & (0,0,2) & (1,0,2)
& (2,0,2)
\cr\cr
V & W & X & Y & Z & .
\cr
(0,1,2) & (1,1,2) & (2,1,2) & (0,2,2) & (1,2,2) & (2,2,2)
\end{array}
\]__
with elements of our triples in the residue class ring modulo __\( S \)__. Then
the word FROM becomes the sequence
__\[ (2,1,0,2,2,1,2,1,1,0,1,1) ,\]__
which we group into the set of three sequences __\( (2,1,0,2) \)__, __\( (2,1,2,1) \)__,
__\( (1,0,1,1) \)__, and enscribe by the use of __\eqref{eq-52}__ for __\( n = 4 \)__ and
__\[
d =
\begin{vmatrix}
& 2 & 1 & 0 & 0 &
\cr
& 1 & 1 & 0 & 0 &
\cr
& 0 & 1 & 1 & 2 &
\cr
& 1 & 0 & 0 & 2 &
\end{vmatrix}.
\]__
The result is the sequence
__\[ (1,0,0,1,0,2,2,0,0,2,1,1) ,\]__
which yields
BTCO. Here we have combined the sequence __\( (2,1,0) \)__ arising
from F with the first element in the sequence __\( (2,2,1) \)__ arising
from R.

#### 15. Involutorial cipher systems

A substitution cipher system defined by a cipher alphabet and a
non-singular mapping __\( T \)__ of __\eqref{eq-52}__ is said to be involutorial
if __\( T^{-1} \)__ is the same as __\( T \)__. A large class of such transformations
may be determined as follows. Let __\( A \)__ be any non-singular __\( r \)__-rowed
square matrix with __\( a_{ij} \)__ in the __\( i \)__-th row
and __\( j \)__-th column. Assume that __\( A \)__ is symmetric (that is,
the __\( a_{ij} = a_{ji} \)__) or that __\( r \)__ is even and __\( A \)__ is skew (__\( a_{ij} =
-a_{ji} \)__). We carry a message into a cipher alphabet (best taken to be
a finite field, say, __\( \mathcal{A}_{29} \)__) in which the
elements __\( a_{ij} \)__ of __\( A \)__ lie, and then break up the message into sets
of sequences of __\( r \)__ elements which we use in groups of __\( r \)__ as rows of
corresponding matrices __\( Y \)__. Then we form __\( A Y^{\prime} A^{-1} \)__,
where the columns of __\( Y^{\prime} \)__ are the rows of __\( A \)__.

#### 16. Special ciphers

Let us use the alphabet given by __\( \mathcal{A}_{29} \)__ in equation __\eqref{eq-33}__.
Consider the message given by
__\[
\begin{array}{cccccccccccccccc}
T & H & E & R & E & - & A & R & E & , & O & F & - & C & O & U
\cr
-10 & -4 & 3 & -9 & 3 & 0 & 1 & -9 & 3 & 14
& 8 & -3 & 0 & 2 & 8 & 11
\cr\cr
R & S & E & , & M & O & R & E &- & E & F & F & E & C & T & I
\cr
-9 & 10 & 3 & 14 & 7 & 8 & -9 & 3 & 0 & 3 &
-3 & -3 & 3 & 2 & -10 & 5
\cr\cr
V & E & - & M & E & T & H & O & D & S & . & -
\cr
-11 & 3 & 0 & 7 & -3 & -10 & -4 & 8 & -2 & 10
& -14 & 0
\end{array}
\]__
and then form the matrices
__\begin{alignat*}{2}
& A_1 = \biggl(\begin{array}{rr} -10 & -4 \cr 3 & -9 \end{array}\biggr), \quad
&& A_2 = \biggl(\begin{array}{rr} 3 & 0 \cr 1 & -9 \end{array}\biggr),\quad
&&A_3 = \biggl(\begin{array}{rr} 3 & 14 \cr 8 & -3 \end{array}\biggr),
\cr
& A_4 =\biggl(\begin{array}{rr} 0 & 2 \cr 8 & 11 \end{array}\biggr),\quad
&&A_5 = \biggl(\begin{array}{rr} -9 & 10 \cr 3 & 14 \end{array}\biggr), \quad
&& A_6 = \biggl(\begin{array}{rr} 7 & 8 \cr -9 & 3 \end{array}\biggr),
\cr
&A_7 = \biggl(\begin{array}{rr} 0 & 3 \cr -3 & -3 \end{array}\biggr), \quad
&& A_8 = \biggl(\begin{array}{rr} 3 & 2 \cr -10 & 5 \end{array}\biggr),\quad
&&A_9 = \biggl(\begin{array}{rr} -11 & 3 \cr 0 & 7 \end{array}\biggr),
\cr
& A_{10} = \biggl(\begin{array}{rr} -3 & -10 \cr -4 & 8 \end{array}\biggr),\quad
&&A_{11} = \biggl(\begin{array}{rr} -2 & 10 \cr -14 & 0 \end{array}\biggr).
\end{alignat*}__
Then we compute __\( B A_i \)__, where
__\[
B = \biggl(\begin{array}{rr} 1 & -1 \cr -1 & 2 \end{array}\biggr), \quad B^{-1} =
\biggl(\begin{array}{rr} 2 & 1 \cr 1 & 1 \end{array}\biggr) ,
\]__
and the result is enscribed as
__\begin{align*}
&
ZIZ.\ \ CQBU\ \ JXYQ\ \ PRZR\ \ XH.Z\ \ IGDE
\\
&
KLRY\ \ FKOV\ \ HUUM\ \ UVFW\ \ SET.
\end{align*}__
The frequencies in the original message are thereby completely destroyed.

Using the same __\( B \)__ we may also define the __\( A_i \)__ by
__\begin{alignat*}{2}
& A_1 = \biggl(\begin{array}{rr} -10 & -4 \cr -4 & 3 \end{array}\biggr),
&\quad
& A_2 = \biggl(\begin{array}{rr} -9 & 3 \cr 3 & 0 \end{array}\biggr),
\cr
&\dots\ ,
&\quad
&A_{15} = \biggl(\begin{array}{rr} -14 & 1 \cr 1 & 3 \end{array}\biggr)
\end{alignat*}__
and then carry our original message of 43 symbols (plus one or two nulls)
into one of 60 letters. It might be said that the second __\( -4,3 \)__, etc.,
in our symmetric matrices __\( B_i \)__ are nulls but they are still really a part
of our message.

The two systems above may be combined and thus we write
__\begin{alignat*}{3}
& A_1 = \biggl(\begin{array}{rr} -10 & -4 \cr -4 & 3 \end{array}\biggr),
&\quad
& A_2 = \biggl(\begin{array}{rr} -9 & 3 \cr 0 & 1 \end{array}\biggr),
&\quad
& A_4 = \biggl(\begin{array}{rr} -9 & 3 \cr 3 & 14 \end{array}\biggr),
\cr
&\dots\ ,
&\quad
& A_{12} = \biggl(\begin{array}{rr} -4 & 8 \cr -2 & 10 \end{array}\biggr),
&\quad
& A_{13} = \biggl(\begin{array}{rr} -14 & 5 \cr 5 & -2 \end{array}\biggr) ,
\end{alignat*}__
in which the 5, __\( -2 \)__ are nulls. Then our message is transformed into
one of the 52 elements. Yet, each of these systems uses the *same*
matrix for enciphering and could be deciphered by knowing the possibilities
with explicit knowledge as to when the encipherer changes from ordinary
to symmetric __\( A_i \)__.

There are over 600,000 distinct non-singular two-rowed matrices with elements
in __\( \mathcal{A}_{29} \)__, and the particular matrix used as above may be changed
at will. For example, in written text it might be agreed that certain four
prescribed letters represent the matrix __\( A \)__ used to encipher that paragraph.
Or we might write
__\begin{alignat*}{3}
& I = \biggl(\begin{array}{rr} 1 & 0 \cr 0 & 1 \end{array}\biggr),
&\quad
& A = \biggl(\begin{array}{rr} 3 & 5 \cr -2 & -3 \end{array}\biggr),
&\quad
& B = \biggl(\begin{array}{rr} 3 & 3 \cr 4 & 5 \end{array}\biggr),
\cr
&&
& C = \biggl(\begin{array}{rr} -3 & 7 \cr -1 & 2 \end{array}\biggr),
&\quad
& D = \biggl(\begin{array}{rr} 1 & 1 \cr 1 & 2 \end{array}\biggr),
\end{alignat*}__
and then use the first four letters of each paragraph to give the matrix used.
Thus a paragraph beginning with CIAB would have been enciphered with
__\[
CAB = \biggl(\begin{array}{rr} -10 & 12 \cr 3 & 1 \end{array}\biggr) .
\]__
However, it might be simpler to prescribe __\( A \)__ and __\( B \)__ as well, as four
positions for letters __\( d_1\, d_2 \, d_3 \, d_4 \)__ in a paragraph of a
cryptogram, and use the matrix products
__\[
A \biggl(\begin{array}{rr} d_1 & d_2 \cr d_3 & d_4 \end{array}\biggr) B
\]__
to encipher the paragraph. Of course, other devices than paragraphing to
indicate a change in cipher system could be used.