# Celebratio Mathematica

## A. Adrian Albert

### Some mathematical aspects of cryptography

#### 1. Introduction

The idea of con­nect­ing cryp­to­graphy with math­em­at­ics is not new, but it has not been ex­ploited in the lit­er­at­ure of either sub­ject to the ex­tent of the present pa­per. Our top­ic should be a timely one not only be­cause of the present pub­lic in­terest in any­thing con­nec­ted with our war ef­fort, but also be­cause of the cur­rent ever in­creas­ing use by sci­ent­ists1 of the con­cepts of mod­ern ab­stract al­gebra.

We shall present here a math­em­at­ic­al for­mu­la­tion of a gen­er­al the­ory of crypto­logy2 with de­tailed ap­plic­a­tion to cryp­to­graphy. In this, we shall see that cryp­to­graphy is more than a sub­ject per­mit­ting math­em­at­ic­al for­mu­la­tion, for in­deed it would not be an ex­ag­ger­a­tion to state that ab­stract cryp­to­graphy is identic­al with ab­stract math­em­at­ics.

Our for­mu­la­tion will per­mit a rap­id present­a­tion of the meth­ods of cryp­to­graphy in com­mon use, and we shall show that all of these meth­ods are very spe­cial cases of the so-called al­geb­ra­ic cipher sys­tems. These lat­ter cipher sys­tems are en­tirely prac­tic­al in the simple cases, and we hope that our present­a­tion will des­troy the be­lief of many crypto­lo­gists that they are “only prac­tic­al provid­ing a ma­chine is used.”3

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

The func­tion concept has been de­scribed fre­quently as a uni­fy­ing concept for col­legi­ate math­em­at­ics. Ele­ment­ary func­tions are usu­ally giv­en by for­mu­las $y = f(x)$, but this sort of defin­i­tion is not al­ways pos­sible and only makes sense in an en­vir­on­ment in which the ne­ces­sary ad­di­tion­al as­sump­tions are pre­sup­posed for all the func­tions con­sidered. Let us then for­mu­late the concept in com­plete gen­er­al terms.

Con­sider a set $\mathcal{M}$ con­sist­ing of any ob­jects whatever and call these ob­jects the quant­it­ies of $\mathcal{M}$. (They might be num­bers or phys­ic­al ob­jects or even math­em­at­ic­al con­cepts!) We let $x$ be a sym­bol which is per­mit­ted, dur­ing our dis­cus­sion, to rep­res­ent any quant­ity of $\mathcal{M}$, so that we call $x$ a vari­able whose range is $\mathcal{M}$. Let $\mathcal{N}$ be a second set of quant­it­ies and set up a cor­res­pond­ence $$x \mapsto S(x) \label{eq-01}$$ (read $x$ goes to $S(x)$) whereby every $x$ in $\mathcal{M}$ de­term­ines a unique $S(x)$ in $\mathcal{N}$. Then the sym­bol $u = S(x)$ is a second vari­able, with $\mathcal{N}$ as its range, and we are ac­cus­tomed to say that the cor­res­pond­ence defines $u$ as a func­tion of $x$.

Thus, a func­tion of $x$ really con­sists of two sets $\mathcal{M}$ and $\mathcal{N}$ and the cor­res­pond­ence $S$ giv­en by \eqref{eq-01} of the quant­it­ies $x$ of $\mathcal{M}$ on their im­ages $S(x)$ in $\mathcal{N}$. It will be bet­ter for our pur­poses to de­scribe this situ­ation by simply speak­ing of $S$ rather than the func­tion, and we shall call $S$ a map­ping of $\mathcal{M}$ on $\mathcal{N}$.

Sup­pose that there is also a map­ping $T$ giv­en by $$u \mapsto T(u) \label{eq-02}$$ on $\mathcal{N}$ to $\mathcal{M}$, so that every $u$ of $\mathcal{N}$ de­term­ines a unique $T(u)$ in $\mathcal{M}$. Then we let $T$ be such that if $u=S(x)$, the quant­ity $T(u) = x$. In this case, the map­ping $S$ is called a non-sin­gu­lar map­ping. $T$ is called its in­verse, and we in­dic­ate this by writ­ing $T=S^{-1}$.

Cryp­to­graphy is the study of all non-sin­gu­lar map­pings $S$ on $\mathcal{M}$ to $\mathcal{N}$ where $\mathcal{M}$ is the set of a mes­sages $x$ and $\mathcal{N}$ is the set of all cryp­to­grams $S(x)$. The map­pings are called cipher sys­tems. If a mes­sage $x$ and a cipher sys­tem $S$ are giv­en, the pro­cess of the ap­plic­a­tion of $S$ to $x$, so as to ob­tain the cryp­to­gram $S(x)$, is called the en­cipher­ment of $x$. When $S$ and $S(x)$ are giv­en, the pro­cess of the ap­plic­a­tion of $S^{-1}$ to the cryp­to­gram $S(x)$, so as to ob­tain the mes­sage $x$, is called the de­cipher­ment of $S(x)$.

There are many math­em­at­ic­al situ­ations in which it is pos­sible to de­term­ine a map­ping $S$ on $\mathcal{M}$ to $\mathcal{N}$ from a giv­en list of a fi­nite num­ber of quant­it­ies $x$ in $\mathcal{M}$ and their im­ages $S(x)$ in $\mathcal{N}$. However we wish to pro­pose the more dif­fi­cult prob­lem of de­term­in­ing $S$ (and hence each $x$) from a giv­en fi­nite set of cryp­to­grams $S(x)$. We use this in the defin­i­tion of crypt­ana­lys­is as the the­ory of those struc­tur­al prop­er­ties of mes­sages, cryp­to­grams, and cipher sys­tems which are re­quired in or­der to solve all prob­lems (which per­mit a solu­tion) of the kind above. The solu­tion of such a prob­lem is called the de­crypt­ment of its cryp­to­grams, and so crypt­ana­lys­is is the study of the meth­ods of de­crypt­ment. Crypto­logy is the sub­ject com­pris­ing both cryp­to­graphy and crypt­ana­lys­is. However, we shall be con­cerned 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 prim­it­ive cipher sys­tem would be simply a list of all the mes­sages to be used and an ad­ja­cent list of cor­res­pond­ing cryp­to­grams. However, some more soph­ist­ic­ated cipher sys­tems are de­scrib­able, as is the case for some math­em­at­ic­al func­tions, by for­mu­las. These for­mu­las will ex­press the cryp­to­gram $S(x)$ in terms of the res­ult of ap­ply­ing the cipher sys­tem $S$ to what we shall call com­pon­ents of the mes­sage $x$, and we shall for­mu­late this new concept.

The term mes­sage has not been in­ter­preted thus far but we now con­ceive of it as any se­quence of a fi­nite num­ber of sym­bols which are either let­ters, peri­ods, or com­mas and the like. We now par­ti­tion the mes­sage in­to blocks of sym­bols called com­pon­ents. The mes­sage $x$ will then be­come a se­quence of com­pon­ents, each con­sist­ing of a group of sym­bols of the mes­sage $x$. These oc­cur in the com­pon­ent in the same or­der as in $x$. Also the or­der of the com­pon­ents them­selves is fixed by the or­der of the sym­bols in $x$. The com­pon­ents may be simply the words of $x$, or its sen­tences, or simply blocks of a fixed num­ber of let­ters. In the lat­ter case the fi­nal block may not con­tain enough let­ters to sat­is­fy the giv­en defin­i­tion. Then it will be ne­ces­sary to ad­join let­ters, called nulls, to bring up the num­ber of let­ters to the re­quired amount.

Sup­pose now that a mes­sage $x$ has been broken up in­to $n$ com­pon­ents where $n$ is a pos­it­ive in­teger. Let $i$ be any in­teger from 1 to $n$ and let the sym­bol $x_i$ rep­res­ent the $i$-th com­pon­ent of $x$. Then we may rep­res­ent this situ­ation by writ­ing $x$ in the fol­low­ing nota­tion $$x = \bigl[x_1, x_2, \dots , x_n\bigr]. \label{eq-03}$$ We wish also to use cipher sys­tems $S$ which re­place $x$ by se­quences $$u = S(x) = \bigl[u_1, u_2, \dots , u_m \bigr]. \label{eq-04}$$ Here, the cryp­to­gram $u$ has been broken up in­to $m$ com­pon­ents of some pre­scribed kind and neither the pos­it­ive in­teger $m$ nor the kind of com­pon­ents $u_j$ ($j=1, \dots , m$) need be the same as for $x$.

The most prim­it­ive for­mula for a cipher sys­tem in terms of \eqref{eq-03} and \eqref{eq-04} is giv­en by $$S(x) = \bigl[ T(x_1), T(x_2), \dots , T(x_n)\bigr], \label{eq-05}$$ where $T$ is a non-sin­gu­lar map­ping on the set $\mathcal{M}_0$ of the com­pon­ents (of a pre­scribed kind) of mes­sages to the set $\mathcal{N}_0$ of com­pon­ents of cryp­to­grams (also of pre­scribed kind). The code is such a cipher sys­tem. Here, the com­pon­ents of $x$ are the words, $\mathcal{M}_0$ is the set of all words in all the mes­sages which will be used, $\mathcal{N}_0$ is the set of all the words in all the res­ult­ing cryp­to­grams, $T$ is a non-sin­gu­lar map­ping on $\mathcal{M}_0$ to $\mathcal{N}_0$.

In de­scrib­ing cipher sys­tems where more of a cipher sys­tem is to be giv­en by the for­mula and less by aux­il­i­ary map­ping, the nature of the com­pon­ents $u_j$ of the cryp­to­gram \eqref{eq-04} may de­pend both on the nature of $x_i$ in $x$ and also on its po­s­i­tion in the mes­sage, which we have in­dic­ated by its sub­script $i$. But then a for­mula de­scrib­ing the cipher sys­tem would de­pend upon the length $n$ of the mes­sage $x$, and we are study­ing for­mu­las in­de­pend­ent of $x$. We may achieve our end, however, by the ad­junc­tion of new com­pon­ents, which are nulls, to bring up the num­ber of com­pon­ents to a fixed max­im­um pre­scribed in ad­vance. It may also be achieved in a some­what more prac­tic­al way by the use of \eqref{eq-05} and the fact that each $x_i$ may it­self be re­garded as be­ing a mes­sage, the set of all mes­sages to con­sidered is now the set $\mathcal{M}_0$ or our com­pon­ents, $T$ is a cipher sys­tem. But we may pre­scribe a par­ti­tion­ing of $x$. If we then define com­pon­ents for our mes­sage so that each com­pon­ent $x_i$ per­mits a fur­ther sub­di­vi­sion in­to sub­com­pon­ents $x_{i_1}, \dots$, $x_{i_{\nu}}$, with $\nu$ the same for each $i$, the cipher sys­tem $T$ will op­er­ate on mes­sages all of the same num­ber of com­pon­ents.

We have now seen how to lim­it our study to cipher sys­tems on mes­sages \eqref{eq-03} for a fixed $n$, and we shall do this.

#### 4. Transposition ciphers

A trans­pos­i­tion cipher is simply a cipher sys­tem giv­en by \eqref{eq-03} and $$S(x) = \bigl[ x_{i_1}, x_{i_2}, \dots , x_{i_n} \bigr], \label{eq-06}$$ where $i_1, \dots, i_n$ is any per­muta­tion (i.e., re­arrange­ment) of the in­tegers $1,2,\dots , n$. This may be ac­com­plished most ef­fect­ively in the gen­er­al case by simply writ­ing the mes­sage and the per­muta­tion and then read­ing off the cryp­to­gram in the form: $$\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}$$

To de­cipher such as mes­sage, we read up in the cipher sys­tem to ob­tain its in­verse, and then have: $$\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}$$ For ex­ample, 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 ap­ply to ob­tain the ori­gin­al mes­sage.

There are many devices for ac­com­plish­ing trans­form­a­tions of this kind but none of them can do more than what we have in­dic­ated above. They may need to be stud­ied in crypt­ana­lys­is but surely are not worth­while ad­di­tions to cryp­to­graphy. It would seem that their only pos­sible value in this lat­ter sub­ject is that they may be re­l­at­ively easy to re­mem­ber. However, the most prim­it­ive of them are worth­less, and the more com­plic­ated ones are not as easy to re­mem­ber as the fol­low­ing device.

Let us mem­or­ize any sen­tence and write it with a num­ber be­low each let­ter from 1 to the num­ber $n$ of let­ters in the sen­tence. We then put num­bers be­low those ac­cord­ing to the al­pha­bet­ic­al or­der of the let­ters, giv­ing re­peated let­ters con­sec­ut­ive num­bers. The trans­pos­i­tion cipher sys­tem ob­tained in this way may be writ­ten down rap­idly, and is usu­ally much more gen­er­al in its struc­ture than those spe­cial sys­tems in com­mon use. For ex­ample, 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-sin­gu­lar map­ping $x \mapsto u = S(x)$ on $\mathcal{M}$ to a set $\mathcal{N}$ and $T$ is a non-sin­gu­lar map­ping $u \mapsto T(u)$ on $\mathcal{N}$ to a set $\mathcal{L}$ the cor­res­pond­ence $$x \longmapsto V(x) = T[ S(x) ] \label{eq-09}$$ is a non-sin­gu­lar map­ping $V$ on $\mathcal{M}$ to $\mathcal{L}$. However, it may be more con­veni­ent to com­pute $V(x)$ by first com­put­ing $u = S(x)$, and then $T(u)$, rather than $V(x)$ dir­ectly. We shall call $V$ the product $ST$ of the map­pings $S$ and $T$.

In cryp­to­graphy it is fre­quently pos­sible to think of cryp­to­grams them­selves as be­ing mes­sages, and thus study cipher sys­tems which are non-sin­gu­lar map­pings on $\mathcal{M}$ to $\mathcal{M}$. But then the product $ST$ of a cipher sys­tem $S$ by a cipher sys­tem $T$ is an­oth­er cipher sys­tem.

It is also pos­sible fre­quently to break down a cipher sys­tem in­to a product of sim­pler ones. This is usu­ally done in ana­lyz­ing cipher sys­tems, and much of our dis­cus­sion will be con­cerned with a de­scrip­tion of these sim­pler sys­tems rather than the more com­plic­ated sys­tems de­riv­able from them by the product op­er­a­tion de­scribed above.

It should be ob­served that the op­er­a­tion of product of map­pings is as­so­ci­at­ive, that is, $(ST)U = S(TU)$ for any three map­pings $S$, $T$, $U$. In­deed, both of these map­pings are the same cor­res­pond­ences $x \mapsto U \{ T[ S(x) ] \} .$ However the op­er­a­tion is not com­mut­at­ive and in­deed  $TS$ may not even be defined. But even if $S$ and $T$ are map­pings on $\mathcal{M}$ to $\mathcal{M}$, so that $ST$ and $TS$ are also map­pings on $\mathcal{M}$ to $\mathcal{M}$, they may be dif­fer­ent. For ex­ample, let $\mathcal{M}$ con­sist of the sym­bols $1,2,3$;  $S$ be the cor­res­pond­ence $1 \mapsto 2$, $2 \mapsto 3$, $3 \mapsto 1$; $T$ be the cor­res­pond­ence $1 \mapsto 2$, $2 \mapsto 1$, $3 \mapsto 3$. Then $ST$ is giv­en 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 fre­quently de­sir­able in cryp­to­graphy to use an in­ter­me­di­ate set $\mathcal{N}$ and so con­struct a cipher sys­tem $S$ as the product $TUT^{-1}$, where $T$ is a non-sin­gu­lar map­ping on the set $\mathcal{M}$ of all mes­sages to the in­ter­me­di­ate set $\mathcal{N}$, $U$ is a non-sin­gu­lar map­ping on $\mathcal{N}$ to $\mathcal{N}$. Let us then write $x = \bigl[ x_1, \dots, x_n \bigr],$ for com­pon­ents $x_i$ of our mes­sages $x$, and sup­pose that $T$ is such that $$u = T(x) = \bigl[ u_1, \dots, u_n \bigr], \qquad u_i = T_0 (x_i). \label{eq-10}$$ Here, $T_0$ is a non-sin­gu­lar map­ping on the set $\mathcal{M}_0$ of all com­pon­ents of mes­sages, to a set $\mathcal{N}_0$ whose quant­it­ies are at our choice. Then $u$ is formed as the se­quence above and we have $$T^{-1} (u) = \bigl[ T_0^{-1} (u_1), \dots , T_0^{-1} (u_n) \bigr]. \label{eq-11}$$ We ap­ply a second trans­form­a­tion $U$ on $\mathcal{N}$ to $\mathcal{N}$ and have $$U(u) = \bigl[ v_1, \dots, v_n \bigr], \label{eq-12}$$ so that $$S (x) = \bigl[ T_0^{-1} (v_1), \dots, T_0^{-1} (v_n) \bigr]. \label{eq-13}$$ Let us call the set $\mathcal{N}_0$, to­geth­er with the map­ping $T_0$, a cipher al­pha­bet.

The cipher al­pha­bet is in­tro­duced to sim­pli­fy the de­scrip­tion of $S$. In par­tic­u­lar we may use a math­em­at­ic­al num­ber sys­tem $\mathcal{A}$ for the set $\mathcal{N}_0$ and so have a set $\mathcal{N}_0$ in which ad­di­tion and mul­ti­plic­a­tion of its quant­it­ies are defined. It may then be a very simple mat­ter to give for­mu­las for the map­ping $U$ and to give $T_0$ ex­pli­citly. However the con­sequent de­scrip­tion of $S$ in terms of mes­sages alone would usu­ally be ex­tremely com­plic­ated.

The only sets $\mathcal{A}$ of which we shall use are the sets called com­mut­at­ive rings: A ring $\mathcal{A}$ is a set of quant­it­ies for which the sum $a + b$ and the product $ab$ of any $a$ and $b$ in $\mathcal{A}$ are quant­it­ies 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 as­sume that for every $a$ and $b$ of $\mathcal{A}$ there is a unique solu­tion $x$ in $\mathcal{A}$ of the equa­tion $$a + x = b. \label{eq-16}$$ We call $\mathcal{A}$ a com­mut­at­ive ring if it is also true that $$ab = ba \label{eq-17}$$ for every $a$ and $b$ of $\mathcal{A}$.

In every ring, there is a unique zero quant­ity 0 such that $$a + 0 = a, \label{eq-18}$$ for every $a$ of $\mathcal{A}$, and a unique quant­ity $-{a}$, called the neg­at­ive of $a$, such that $$a + (-{a}) = 0. \label{eq-19}$$ Then in \eqref{eq-15} we have $x = b + (-{a})$. It can be shown that the prop­er­ties we have as­sumed im­ply that $-{(-{a})} = a$, $(-{a})b = a(-{b}) = -{(ab)}$, $(-{a})(-{b}) = ab$ for all quant­it­ies $a$ and $b$ of $\mathcal{A}$.

The fa­mil­i­ar num­ber sys­tems con­sist­ing of all ra­tion­al num­bers, of all real num­bers, and of all com­plex num­bers are ex­amples of com­mut­at­ive rings. These rings are all fields, that is, com­mut­at­ive rings $\mathcal{A}$ with the prop­erty that if $a$ and $b$ are in $\mathcal{A}$ and $a$ is not zero there is a unique solu­tion $x$ in $\mathcal{A}$ of the equa­tion $$a x = b. \label{eq-20}$$ This quo­tient $x$ has a prop­erty like the dif­fer­ence $x = b - a$ which is the solu­tion of \eqref{eq-15}. First there is a unity quant­ity 1 in $\mathcal{A}$ such that $$1 a = a 1 = a, \label{eq-21}$$ for every quant­ity $a$ of $\mathcal{A}$. Also every $a \ne 0$ has a unique in­verse $a^{-1}$ such that $$a a^{-1} = a^{-1} a = 1, \label{eq-22}$$ and then $x = b a^{-1}$.

The set of all in­tegers, and the set of all poly­no­mi­als $f(\lambda)$ in a sym­bol $\lambda$ with ra­tion­al coef­fi­cients, are both com­mut­at­ive rings with a unity qual­ity. But they are not fields.

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

Let us now sup­pose that the com­pon­ents $x_i$ of a mes­sage $x$ in its rep­res­ent­a­tion \eqref{eq-03} as se­quence, are let­ters of the al­pha­bet, and per­haps oth­er sim­il­ar sym­bols like peri­ods or com­mas. Then, the set $\mathcal{M}_0$ of all pos­sible com­pon­ents is a fi­nite set and we shall wish to map it on a ring $\mathcal{N}_0$, also with a fi­nite num­ber of quant­it­ies. Let us then pro­ceed to define cer­tain very simple fi­nite rings.

The quant­it­ies of our new rings will not be or­din­ary in­tegers but classes of in­tegers. The read­er is already fa­mil­i­ar with the clas­si­fic­a­tion of in­tegers in­to two classes, namely, the class of all even in­tegers, and the class of all odd in­tegers. 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 rep­res­ent the class of all even in­tegers by 0, the class of all odds by 1, and we have a ring of two ele­ments 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 sim­il­arly a ring $A_m$ of $m$ classes of or­din­ary in­tegers, for every fixed in­teger $m > 1$. If $a$ is any in­teger there are in­tegers $q$ and $r$ such that $$a - q m = r, \label{eq-24}$$ where the re­mainder $r$ is one and only one of the in­tegers $$0,1,2,\dots,m-1. \label{eq-25}$$ Let us call two in­tegers $a$ and $b$ con­gru­ent and write $$a \equiv b, \label{eq-26}$$ if the cor­res­pond­ing re­main­ders are the same. Then $a \equiv 0$ if and only if $a$ is a mul­tiple of $m$,  $a \equiv b$ if and only if $a - b = 0$.

Let us now put all in­tegers in­to a set of residue classes, each of which will be des­ig­nated by $\{a\}$. Here $a$ is any in­teger of the class, $\{a\} = \{b\}$ if any only if $a \equiv b$. It is clear that there are $m$ classes and that they are pre­cisely the classes $\{0\}, \{1\}, \dots , \{ m - 1\},$ where if $r$ has any of the val­ues $0,1, \dots, m-1$, the set $\{r\}$ con­sists of all in­tegers dif­fer­ing from $r$ by a mul­tiple of $m$.

It is a simple mat­ter to veri­fy the iden­tit­ies \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 im­ply that if $a \equiv b$ and $c \equiv d$ then $a + c \equiv b + d$, $ac\equiv bd$. But it fol­lows that $\{a + c \}$ and $\{ a c \}$ are uniquely de­term­ined 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 com­mut­at­ive ring.

In ac­tu­al use we omit the braces and com­pute with in­tegers in the nor­mal way but al­ways drop off mul­tiples of $m$. We need not use $0,1,\dots$, $m - 1$ as a set of re­main­ders but may choose any oth­er $m$ in­tegers provid­ing that there is one and only one from each class. For ex­ample, let us study $\mathcal{A}_{26}$.

To fa­cil­it­ate com­pu­ta­tions we use the table of products $q \cdot 26$, $q = 2,3,\dots$, 25, which is giv­en 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 al­pha­bet as a map­ping \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 mul­tiply in­tegers as usu­al provid­ing neither sum nor product ex­ceeds 26. Then $3 + 5 = 9$, $3 \cdot 5 = 15$. However, $15 + 19 = 34 \equiv 8$, and so if we re­place 0 and $S$ by what we may call their sum, this sum would be $H$. Sim­il­arly $15 \cdot 19 = 285 \equiv 25$ by the table above, and this cor­res­ponds to $Y$.

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

We shall con­struct cipher sys­tems as in equa­tions \eqref{eq-10}, \eqref{eq-11}, \eqref{eq-12}, \eqref{eq-13}, where the set $\mathcal{N}_0$ of com­pon­ents $u_1$ will be a fi­nite ring and the map­ping $U$ will be defined by al­geb­ra­ic ex­pres­sions for the com­pon­ents $v_1, \dots$, $v_n$ of $U(u)$ in terms of the com­pon­ents $u_1, \dots$, $u_n$ of $u$. A spe­cial in­stance of such a cipher sys­tem is that where $\mathcal{N}_0= A_{26}$, $$U (u) = \bigl[ a u_1, \dots , a u_n \bigr], \label{eq-28}$$ for any non-zero quant­ity of $\mathcal{A}_{26}$. If $a$ is the class $\{ 3 \}$ of $\mathcal{A}_{26}$ our cipher sys­tem re­places every let­ter of our mes­sage by a cor­res­pond­ing let­ter, such that $\mathrm{A}, \dots, \mathrm{Z}$ cor­res­pond, re­spect­ively, to $$CFILO\ \ RUXAD\ \ GJMPS\ \ VYBEH\ \ KNQTW\ \ Z. \label{eq-29}$$ If we at­temp­ted to con­struct the sim­il­ar map­ping with $a = \{ 2 \}$ we would re­place $\mathrm{A}, \dots \mathrm{Z}$, re­spect­ively, by $$BDFHJ\ \ LNPRT\ \ VXZBD\ \ FHJLN\ \ PRTVX\ \ Z, \label{eq-30}$$ and so the map­ping would not be non-sin­gu­lar.

The fact that the cipher sys­tem just de­scribed is sin­gu­lar arises from the prop­erty that the map­pings $$x \mapsto a x \quad (x\text{ in }\mathcal{A}), \label{eq-31}$$ defined for each $a \ne 0$ of $\mathcal{A}$, are sin­gu­lar for some quant­it­ies $a$ of $\mathcal{A}_{26}$. Such a map­ping is non-sin­gu­lar for a giv­en $a \ne 0$ if it is true that for every $b$ of $\mathcal{A}$, there is a solu­tion $x$ in $\mathcal{A}$ of the equa­tion \eqref{eq-20}. But then the map­pings \eqref{eq-31} of $\mathcal{A}$ on $\mathcal{A}$ are all non-sin­gu­lar for $a \ne 0$ of $\mathcal{A}$ if and only if $\mathcal{A}$ is a field.

The fi­nite rings $\mathcal{A}_m$ with $m = s t$ for pos­it­ive in­tegers $s > 1$, $t > 1$ are not fields. This fol­lows since $\{ s \} \{ t \} = \{0 \}$, the ex­ist­ence of a solu­tion $x$ of $\{ t \} x = \{ 1 \}$ would im­ply that $\{s \} \{ t \} x = \{ s \} = \{ 0 \} x = \{ 0 \}$. The rings $\mathcal{A}_m$ with $m$ a prime in­teger are fields and two in­stances of such rings im­port­ant for our use are $$A_{29}, A_{31}. \label{eq-32}$$ Let us now set up the cipher al­pha­bet giv­en by $\mathcal{A}_{29}$ and the cor­res­pond­ence \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$, giv­en by $58, 87, 116, 145, 174, 203, 232, 261, 290, 319, 348, 377, 405.$ Then we see that the cipher sys­tem defined by the map­ping $x \mapsto \{3\} x$ of $\mathcal{A}$ on $\mathcal{A}$ sets up a cor­res­pond­ence of $\mathrm{A} , \dots, \mathrm{Z}$, re­spect­ively, to $$EFKLQ\ \ RWX.,\ \ VUPOJ\ \ IDCAB\ \ GHMNS\ \ TYZ- \label{eq-34}$$ Here we have used prop­er­ties con­tained in the set of con­gru­ences \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 oth­er fi­nite fields ob­tained from our fi­nite fields $\mathcal{A}_m$, where $m$ is a prime. Such fields are the sets of poly­no­mi­als 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 equa­tion $f(x) = 0$ of de­gree $t$, coef­fi­cients in $\mathcal{A}_m$, and not factor­ing in $\mathcal{A}_m$. Then $\alpha$ is a prim­it­ive $(q - 1)$-st root of unity, $q = m^t$ is the num­ber of ele­ments in this field. We des­ig­nate such fields by $$G F (m^t) \label{eq-35}$$ (read $G$, $F$, $m^t$), and call such a field a Galois field of $m^t$ quant­it­ies. There are no oth­er fi­nite fields.

The fields $\mathcal{A}_m = GF(m)$, $t=1$. An­oth­er im­port­ant ex­ample is the field $GF(3^3)$ of 27 ele­ments. Then its quant­it­ies are sums $$a_0 + a_1 \alpha + a_2 \alpha^2, \label{eq-37}$$ where $a_i = \{ 0 \}, \{ 1 \}, \{2 \} \,\text{modulo } 3$, $$\alpha^3 = \alpha + 1.$$

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

A sub­sti­tu­tion cipher is a non-sin­gu­lar map­ping $$x = \bigl[ x_1, \dots , x_n \bigr] \longmapsto S(x) = \bigl[ u_1, \dots, u_n \bigr], \label{eq-38}$$ where the $x_i$ are the let­ters or oth­er sym­bols of our mes­sage, and the $u_1$ are the cor­res­pond­ing sym­bols de­term­ined by $S$. An im­port­ant type of sub­sti­tu­tion cipher is a non-sin­gu­lar map­ping of the type above in which $$S(x) = \bigl[ T_1 (x_1) , \dots , T_n (x_n) \bigr], \label{eq-39}$$ for non-sin­gu­lar map­pings $T_i$ on $\mathcal{M}_0$ to $\mathcal{M}_0$, where $\mathcal{M}_0$ is the set of sym­bols we are us­ing. Thus the map­pings $T_i = T$ giv­en by \eqref{eq-29}, \eqref{eq-34} define such sub­sti­tu­tion ciphers. Let us also use any fi­nite ring $\mathcal{A}$ in a cipher al­pha­bet which is a non-sin­gu­lar map­ping $$x_i \mapsto y_i, \label{eq-40}$$ on $\mathcal{M}_0$ to $\mathcal{A}$. Then the map­pings $$T_i: y_i \longmapsto a_i y_i + b_i \quad (i = 1, \dots , n) \label{eq-41}$$ on $\mathcal{A}$ to $\mathcal{A}$ are non-sin­gu­lar for every $b_i$ in $\mathcal{A}$ and every non-zero $a_i$ in $\mathcal{A}$. It fol­lows that the cipher sys­tems defined by \eqref{eq-38}, \eqref{eq-39}, \eqref{eq-40}, \eqref{eq-41} are defin­able as fol­lows. Re­place each let­ter of our mes­sage of $n$ let­ters by a cor­res­pond­ing “num­ber” of the ring $\mathcal{A}$ de­term­ined by \eqref{eq-40}. Mul­tiply the $i$-th such num­ber by the fixed non-zero num­ber $a_i$ in $\mathcal{A}$, add the fixed $b_i$, and then re­place the res­ult by the cor­res­pond­ing let­ter de­term­ined also by \eqref{eq-40}. Such ciphers are usu­ally called mul­tiple al­pha­bet ciphers and are called simple or monoal­pha­bet ciphers if the trans­form­a­tions \eqref{eq-41} are all the same, that is, if $$y_i \mapsto a y + b \quad (i = 1, \dots , n). \label{eq-42}$$

#### 10. Special multiple alphabet substitution ciphers

The so-called Caesar cipher is the case where \eqref{eq-41} is giv­en by $$y_i \mapsto y_i + b, \label{eq-43}$$ for $b$ fixed. If we use $\mathcal{A}_{26}$ and use \eqref{eq-27} for the map­ping \eqref{eq-40} of the Ro­man let­ters on the quant­it­ies of our ring then $b$ is a class $\{ r \}$ defined for $r = 0, 1, \dots$, 25 and every let­ter $x$ is re­placed by a let­ter ob­tained by shift­ing it $r$ units in the se­quence $A, \dots$, $Z$ of which it is a mem­ber.

The Vi­genère, Gronsfield, Porta, and Beaufort cipher sys­tems are all vari­ants of our cipher sys­tems de­term­ined by \eqref{eq-27}, the use of $\mathcal{A}_{26}$, and \eqref{eq-41} for $a_i \ne \pm 1$. In the ori­gin­al Vi­genère, we use the form $$y_i \mapsto y_i + b_i \quad (i = 1, \dots , n) \label{eq-44}$$ 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$ let­ters $x_i$ of our mes­sages to cor­res­pond­ing let­ters $z_1 , \dots$, $z_n$. Here we ob­tain the let­ter $z_i$ by a shift of $r_i$ let­ters in the al­pha­bet on the let­ter $x_i$. The amount of shift de­pends on $i$. Thus, a key word of $n$ sym­bols $g_1 , \dots$, $g_n$ may be giv­en, we carry each let­ter $g_i$ to a cor­res­pond­ing residue class $\{ r_i \}$, we use $\{ 26 \} = \{ 0 \}$, we have $0 \leqq r_i < 26$, and we shift $r_i$ let­ters.

The Saint-Cyr cipher is also a true Vi­genère cipher and its mech­an­ism need not be de­scribed. The Gronsfield ciphers dif­fers only from the Vi­genère in that $r_1 , \dots$, $r_n$ are giv­en rather than the key word. The so-called true Beaufort is the cipher sys­tem de­term­ined by $$y_i \longmapsto z_i = y_i - b_i \quad (i = 1, \dots , n), \label{eq-45}$$ where $b_i = \{ r_i \}$, each $r_i$ lies between 0 and 25, and we shift $r_i$ let­ters back­ward in the al­pha­bet. Math­em­at­ic­ally this is identic­al with the Vi­genère but with a dif­fer­ent cipher sys­tem. The so-called mod­i­fied Vi­genère and Beaufort sys­tems are giv­en by $$y_i \longmapsto z_i = -{y_i} + b_1 \quad (i = 1, \dots , n), \label{eq-46}$$ and $$y_i \longmapsto z_i = -y_i - b_i \quad (i = 1, \dots , n), \label{eq-47}$$ re­spect­ively, and are math­em­at­ic­ally identic­al.

The Porta cipher is fun­da­ment­ally the Vi­genère but with the cipher al­pha­bet giv­en 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 poly­gram sub­sti­tu­tion cipher is a cipher sys­tem giv­en by the use of a cipher al­pha­bet and non-sin­gu­lar map­ping $y = \bigl[ y_1, \dots , y_n \bigr] \longmapsto T(y) = \bigl[z_1 , \dots, z_n \bigr] ,$ where each $z_j$ is a func­tion of all the $y_i$ rather than a single $y_i$. A spe­cial case of such a sys­tem is that giv­en by $$z_i = y_i + b_i \quad (i = 1, \dots , s), \label{eq-49}$$ and by $$z_i = y_i + y_{i-s} \quad (i = s+1, \dots , n), \label{eq-50}$$ for some fixed $s < n$. Thus it res­ults from a shift of $r_i$ units for the first $s$ let­ters and is a Vi­genère for this part, and by a shift de­pend­ent on the mes­sage it­self for the re­main­ing let­ters in each group of $n$ let­ters.

#### 12. The cipher systems of Hill

Let us sup­pose that a cipher al­pha­bet in­volving a fi­nite ring $\mathcal{A}$ has been pre­scribed and thus that we may re­place any se­quence of $n$ sym­bols of a mes­sage by a se­quence $$y = \bigl[ y_1, \dots , y_n \bigr] \label{eq-51}$$ of quant­it­ies of $y_i$ of the ring $\mathcal{A}$. We as­sume that $n^2$ quant­it­ies $a_{ij}$ in $\mathcal{A}$ are giv­en as well as $n$ oth­er quant­it­ies $g_1, \dots$, $g_n$ in $\mathcal{A}$ and let $z_j$ be giv­en by $$z_j = y_1 a_{1j} + y_2 a_{2j} + \cdots + y_n a_{nj} + g_j \label{eq-52}$$ for $j = 1, \dots$, $m$. Then the map­ping defined by $$y \longmapsto z = \bigl[ z_1, \dots , z_m \bigr] \label{eq-53}$$ is a non-sin­gu­lar map­ping if the quant­it­ies $a_{ij}$ are such that it is pos­sible to solve for the $y_i$ uniquely in terms of the $z_j$. This oc­curs if $m = n$ and there ex­ist quant­it­ies $b_{ji}$ in $\mathcal{A}$ such that $$y_i = z_1 b_{1 i} + \cdots + z_n b_{n i} + h_i \quad (i = 1, \dots , n), \label{eq-54}$$ where $$h_i = -( g_1 b_{1 i} + \cdots + g_n b_{n i} ) \quad (i = 1, \dots , n). \label{eq-55}$$

If $\mathcal{A}$ is any com­mut­at­ive ring with a unity quant­ity 1 the ele­ment­ary the­ory of sys­tems of lin­ear equa­tions and de­term­in­ants is ap­plic­able. Its res­ults im­ply that the map­ping \eqref{eq-53} is non-sin­gu­lar if and only if the de­term­in­ant $$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}$$ has an in­verse $d^{-1}$ in $\mathcal{A}$ such that $d d^{-1} = 1$. Then it is pos­sible to give ex­pli­cit for­mu­las for the $b_{ji}$ in terms of $d^{-1}$ and the $n - 1$ rowed minors of the ar­ray of which $d$ is the de­term­in­ant. In par­tic­u­lar, if $\mathcal{A}$ is a field, the map­ping \eqref{eq-53} is a non-sin­gu­lar if and only if $d \ne 0$. Also \eqref{eq-53} is non-sin­gu­lar when $\mathcal{A}$ is the residue-class ring mod­ulo $m$ if and only if the residue class $d = \{ r \}$ for a rep­res­ent­at­ive in­teger $r$ prime to $m$.

It must be evid­ent by now that the com­mon sub­sti­tu­tion ciphers of Sec­tions 10 and 11 are all spe­cial cases of the sys­tems giv­en by the use of \eqref{eq-53}, \eqref{eq-52}. The gen­er­al trans­pos­i­tion cipher al­pha­bet is also such a spe­cial case, for we use a cipher al­pha­bet with $\mathcal{A} = \mathcal{A}_{26}$ and thus re­place each se­quence $x = [x_1, \dots$, $x_n]$ of $n$ let­ters by a se­quence $y = [ y_1, \dots$, $y_n ]$ of $n$ residue classes. We use a per­muta­tion $P$ re­pla­cing $x$ by $[x_{i_1}, \dots$, $x_{i_n} ]$ and have our res­ult if we can use \eqref{eq-52} to ob­tain $z= [y_{i_1}, \dots$, $y_{i_n} ]$. This may be ac­com­plished when we take the $g_i$ all zero, the $a_{i_j} = \{ 0 \}$ for all val­ues of $i$ and $j$ ex­cept those where $i = i_j$ in which case $a_{i_j} = \{ 1 \}$.

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

A rect­an­gu­lar ar­ray $$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}$$ is called an $s$ by $t$ mat­rix. It has $s$ rows and $t$ columns of ele­ments in a ring $\mathcal{A}$ and the ele­ment $a_{ij}$ is that ele­ment in its $i$-th row and $j$-th column. Then we may re­place \eqref{eq-57} by the ab­bre­vi­ated nota­tion $$A = (a_{ij}) \quad (i = 1, \dots, s; j = 1, \dots, t). \label{eq-58}$$

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

We now let $$Y = (y_{k i} ) \quad (k = 1, \dots, r; \,i = 1, \dots, s) \label{eq-61}$$ be any $r$ by $s$ mat­rix. Then we define the product $$W = Y \!A = (w_{kj}) \quad (k = 1, \dots, r;\, j = 1, \dots, t) \label{eq-62}$$ to be the $r$ by $t$ mat­rix whose ele­ment in the $k$-th row and $j$-th column is giv­en by $$w_{kj} = y_{k1} a_{1 j} + y_{k2} a_{2 j} + \cdots + y_{k s} a_{s j}. \label{eq-63}$$

Equa­tions \eqref{eq-52} may be writ­ten by the use of matrices in a very simple form. The se­quences $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$ mat­rix whose ele­ment in the $i$-th row and $j$-th column is the coef­fi­cient $a_{ij}$ in our equa­tions \eqref{eq-52}. Then \eqref{eq-52} be­comes $$z = y A + g. \label{eq-64}$$ The iden­tity map­ping $y \mapsto z = y$ has the form \eqref{eq-64} for $g = [0,\dots$, $0]$, $m = n$, and $A$ the mat­rix $I$ whose ele­ments $a_{ij}$ are all zero, ex­cept that the $a_{ii}$ are all 1. Then \eqref{eq-54} is giv­en by $$y = ( z - g) B, \label{eq-65}$$ where $AB = I, B$ is the mat­rix in­verse of $A$.

One may now set up what ap­pears to be a gen­er­al­iz­a­tion of the equa­tions \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$ mat­rix and so are the sums $$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}$$ Nev­er­the­less the map­ping defined by \eqref{eq-66} is only a pseudo­gen­er­al­iz­a­tion of \eqref{eq-52} for $y$ may be re­garded as be­ing a se­quence of $nqs$ ele­ments in $\mathcal{A}$, $z = [z_1, \dots$, $z_n]$, as be­ing a se­quence of $m r t$ ele­ments in $\mathcal{A}$, \eqref{eq-66} can al­ways be ex­pressed in the form \eqref{eq-52}.

However, the form \eqref{eq-66} may be more con­veni­ent to use than \eqref{eq-52}. For ex­ample, a map­ping on a se­quence $[y_1, y_2, y_3, y_4]$ in­volves the use of a four rowed mat­rix. However we may write this se­quence as a mat­rix $$Y = \biggl(\begin{array}{rr} y_1 & y_2 \cr y_3 & y_4 \end{array}\biggr), \label{eq-67}$$ and then use the map­pings defined as in \eqref{eq-66} by the equa­tion $$Z = CY\!A + G \label{eq-68}$$ for two rowed square matrices $C$, $A$, $G$. The map­ping is non-sin­gu­lar if matrices $B$ and $D$ ex­ist such that $A B = D C = I$, $$Y = D (Z - G) B. \label{eq-69}$$ It is not as gen­er­al as the map­ping \eqref{eq-52} but may be quite ad­equate for ac­tu­al use.

#### 14. Fractional substitutions

We have now seen how to carry a se­quence of let­ters in a mes­sage in­to a cor­res­pond­ing ar­ray of what we may call the num­bers of a ring and how to carry each such ar­ray in­to an­oth­er by the use of a sys­tem of lin­ear equa­tions re­turn­ing to a cryp­to­gram con­sist­ing of a cor­res­pond­ing se­quence of let­ters. This may be com­plic­ated fur­ther by the use of non-lin­ear equa­tions and such sub­sti­tu­tion cipher sys­tems are known.4 Frac­tion­al cipher sys­tems do not dif­fer at all from the sub­sti­tu­tion cipher sys­tems already con­sidered in re­spect to the nature of the map­pings defined by \eqref{eq-52} but do dif­fer in that a some­what more com­plic­ated cipher al­pha­bet is used. We let $x = [x_1, \dots$, $x_s]$ be a mes­sage of $s$ let­ters and re­place each let­ter by a se­quence of $t$ quant­it­ies 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} re­places $y$ by a se­quence $z$ in which ele­ments arising from parts of se­quences cor­res­pond­ing to dif­fer­ent let­ters may be com­bined. For ex­ample we set up the map­ping $\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 ele­ments of our triples in the residue class ring mod­ulo $S$. Then the word FROM be­comes the se­quence $(2,1,0,2,2,1,2,1,1,0,1,1) ,$ which we group in­to the set of three se­quences $(2,1,0,2)$, $(2,1,2,1)$, $(1,0,1,1)$, and en­scribe 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 res­ult is the se­quence $(1,0,0,1,0,2,2,0,0,2,1,1) ,$ which yields BTCO. Here we have com­bined the se­quence $(2,1,0)$ arising from F with the first ele­ment in the se­quence $(2,2,1)$ arising from R.

#### 15. Involutorial cipher systems

A sub­sti­tu­tion cipher sys­tem defined by a cipher al­pha­bet and a non-sin­gu­lar map­ping $T$ of \eqref{eq-52} is said to be in­vol­utori­al if $T^{-1}$ is the same as $T$. A large class of such trans­form­a­tions may be de­term­ined as fol­lows. Let $A$ be any non-sin­gu­lar  $r$-rowed square mat­rix with $a_{ij}$ in the $i$-th row and $j$-th column. As­sume that $A$ is sym­met­ric (that is, the $a_{ij} = a_{ji}$) or that $r$ is even and $A$ is skew ($a_{ij} = -a_{ji}$). We carry a mes­sage in­to a cipher al­pha­bet (best taken to be a fi­nite field, say, $\mathcal{A}_{29}$) in which the ele­ments $a_{ij}$ of $A$ lie, and then break up the mes­sage in­to sets of se­quences of $r$ ele­ments which we use in groups of $r$ as rows of cor­res­pond­ing 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 al­pha­bet giv­en by $\mathcal{A}_{29}$ in equa­tion \eqref{eq-33}. Con­sider the mes­sage giv­en 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 com­pute $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 res­ult is en­scribed as \begin{align*} & ZIZ.\ \ CQBU\ \ JXYQ\ \ PRZR\ \ XH.Z\ \ IGDE \\ & KLRY\ \ FKOV\ \ HUUM\ \ UVFW\ \ SET. \end{align*} The fre­quen­cies in the ori­gin­al mes­sage are thereby com­pletely des­troyed.

Us­ing 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 ori­gin­al mes­sage of 43 sym­bols (plus one or two nulls) in­to one of 60 let­ters. It might be said that the second $-4,3$, etc., in our sym­met­ric matrices $B_i$ are nulls but they are still really a part of our mes­sage.

The two sys­tems above may be com­bined 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 mes­sage is trans­formed in­to one of the 52 ele­ments. Yet, each of these sys­tems uses the same mat­rix for en­ci­pher­ing and could be de­ciphered by know­ing the pos­sib­il­it­ies with ex­pli­cit know­ledge as to when the en­cipher­er changes from or­din­ary to sym­met­ric $A_i$.

There are over 600,000 dis­tinct non-sin­gu­lar two-rowed matrices with ele­ments in $\mathcal{A}_{29}$, and the par­tic­u­lar mat­rix used as above may be changed at will. For ex­ample, in writ­ten text it might be agreed that cer­tain four pre­scribed let­ters rep­res­ent the mat­rix $A$ used to en­cipher that para­graph. 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 let­ters of each para­graph to give the mat­rix used. Thus a para­graph be­gin­ning with CIAB would have been en­ciphered with $CAB = \biggl(\begin{array}{rr} -10 & 12 \cr 3 & 1 \end{array}\biggr) .$ However, it might be sim­pler to pre­scribe $A$ and $B$ as well, as four po­s­i­tions for let­ters $d_1\, d_2 \, d_3 \, d_4$ in a para­graph of a cryp­to­gram, and use the mat­rix products $A \biggl(\begin{array}{rr} d_1 & d_2 \cr d_3 & d_4 \end{array}\biggr) B$ to en­cipher the para­graph. Of course, oth­er devices than para­graph­ing to in­dic­ate a change in cipher sys­tem could be used.