## 91115/11116 !

by

One of my favorite encryption techniques isn’t really an encryption at all: it fails in the basic sense that if you know the method of encryption, you can easily decrypt the message. But it does reduce every message to a fraction, and I like that. I can envision entire conversations consisting of phrases like “73/9”. Here’s how it works. You start by replacing each letter with a number: say, A=1, B=2,…,Z=26, and perhaps (space)=27, plus whatever punctuation that you want. Then you write your message as a continued fraction (that is, a nested fraction where each numerator is 1). For example, to write “HELLO” you’d let H=8, E=5, L=12, L=12, and O=15 and write:

$8+\frac{1}{5+\frac{1}{12+\frac{1}{12+\frac{1}{15}}}}$.

Then you’d simplify it before sending it. For example, the fraction above simplifies to:

$8+\frac{1}{5+\frac{1}{12+\frac{1}{\frac{181}{15}}}}$ and then $8+\frac{1}{5+\frac{1}{12+\frac{15}{181}}}$

all the way to $\frac{91115}{11116}$.

To decrypt, use division to write the fraction as a continued fraction (keeping in mind that words that end in “A” will turn out to be ambiguous unless you develop a way around it). Want to have some fun? Try decrypting $\frac{2358}{169}$ (or the longer $\frac{536341314626}{38440072317}$).

I don’t know if the guy in the painting by Lesser Ury is really a spy, but I kind of think he looks like one.

### 3 Responses to “91115/11116 !”

1. Barry Leiba Says:

Right, a handy code for some math-oriented kids to play with. Of course, one can vary the mapping between alphabet and numbers, to make it “harder” (but it still just amounts to a substitution cipher once you sort out the division code). And avoiding mapping 1 should take care of the ambiguity problem.

Here’s a simple REXX program to do the decoding:

/* Decode Xi’s cipher
Enter the numerator and the denominator of the code.
*/
numeric digits 30
parse arg a b
alpha = “ABCDEFGHIJKLMNOPQRSTUVWXYZ ”
msg = “”
do while b > 0
q = a % b
r = a // b
msg = msg || substr(alpha, q, 1)
a = b
b = r
end
say msg

Used:
> xxcode 536341314626 38440072317
MATH IS FUN

2. TwoPi Says:

Godel’s proof of the incompleteness of formal arithmetic hinged in part on the ability to encode sequences of symbols as integers, along with a proof that various logical properties become number theoretic (such as, “is this string of symbols a well-formed formuila?”, or “is this string of symbols a valid proof”?).

Godel’s encoding involves prime powers. Adapted to your “HELLO” example (and using your mapping of the alphabet to the integers), it would lead to the integer $2^8 3^5 5^{12} 7^{12} 11^{15}$, which is a 39 digit integer.

One can prove Godel’s result using the partial fraction encoding rather than the prime power encoding; the one advantage to doing so is that the arithmetic remains simple enough to illustrate by hand for small examples, while Godel’s scheme becomes unmanageable almost immediately.

I can almost imagine two people exchanging fractions as a way to communicate; I can’t imagine folk working with the expansion of “MATH IS FUN” in the prime power encoding.

3. Jason Dyer Says:

I am curious if continued fractions could be used for a real cryptographic system. Not simple continued fractions with only 1s in the numerators, but the kind that allows arbitrary numerators.