[Next] [Up] [Previous] [Index]

The Interval Method

If you could rotate only one side of a rotor, then you would be guaranteed that for each of the 26 possible positions, every input letter would be connected to a different output letter. A special kind of rotor, called a half-rotor, can do this, by having contacts in a circle on one side, and bands around an axle on the other side. But this kind of rotor is bulky and expensive compared to a normal rotor. To ensure that moving a rotor through its possible positions will produce 26 alphabets that are as different as possible, a method called the interval method can be used in wiring rotors.

Edward Hebern originated this method himself; this perhaps is less surprising than it seems (one would, perhaps, have expected the master cryptologist W. F. Friedman to come up with it, for example) when one considers that his first rotor machine, made for use by users in the commercial world, only had one rotor in it.

Finding an interval method rotor sequence is related to solving the Eight Queens problem, except in this case the problem involves a chessboard that allows one to move off any edge and then back on on the opposite edge, and the "queens" can only move and capture along one diagonal, the same diagonal for all of them. A perfect solution is possible only on a board of odd order; seven queens on a 7x7 board, nine queens on a 9x9 board, but for this modified problem, there is no solution for eight pieces.

A simple proof of this fact depends on properties of triangular numbers. The nth triangular number is (n^2+n)/2. If n is an odd number, this is a multiple of n, but if it is an even number, this is an odd multiple of n/2.

On both sides of a rotor, one wire is connected to each contact. So, if the wires are connected to each contact on the opposite side, the sum of the displacements must be equal to zero, modulo the size of the rotor, since the wires are still connected to contacts with the same numbers, contact 1 through contact n. If one tries to use all possible displacements from 1 to n, (or from 0 to n-1, if you prefer) then for even n, the sum will be wrong.

Here is an example of an interval method wiring:

From:         1  2  3  4  5  6  7  8  9
To:           5  4  3  2  1  9  8  7  6

(Difference:  4  2  0  7  5  3  1  8  6)

An interval method wiring for an even number of contacts will have exactly one possible difference omitted, and one repeated twice. Fortunately, while the above example of an interval method sequence is highly symmetrical, there are many possible arrangements that satisfy the interval criterion, and most appear almost random.

Here is another example of an interval method wiring, this time for a 26-contact rotor:

From:         A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
To:           L  N  K  Y  U  W  Z  J  X  H  E  I  A  O  G  S  P  V  C  T  D  R  B  Q  F  M

(Difference: 11 12  8 21 16 17 19  2 15 24 20 23 14  1 18  3 25  4 10  0  9 22  5 19  7 13)

Here, only the difference of 6 is omitted, and only the difference of 19 occurs twice.

Note that it is the alphabet used for constructing an example of a Friedman square on the previous page.

Table of the number of interval method wirings

Ignoring rotations  Ignoring rotations   All
of the whole rotor  of the whole rotor
and one side by
itself

1-contact rotors:          -                   1                    1
2-contact rotors:          1                   2                    2
3-contact rotors:          -                   1                    3
4-contact rotors:          1                   4                   16
5-contact rotors:          -                   3                   15
6-contact rotors:          4                  24                  144
7-contact rotors:          -                  19                  133
8-contact rotors:         32                 256                2,048
9-contact rotors:          -                 225                2,025
10-contact rotors:       464               4,640               46,400
11-contact rotors:         -               3,441               37,851
12-contact rotors:     8,768             105,216            1,262,592
13-contact rotors:         -              79,259            1,030,367
14-contact rotors:   227,008           3,178,112           44,493,568
15-contact rotors:         -           2,424,195           36,362,925
16-contact rotors: 7,814,144         125,026,304        2,000,420,864
17-contact rotors:         -          94,471,089        1,606,008,513

where the number of odd-contact rotors in the third column is from integer sequence A006717 in the Handbook of Integer Sequences, while the number of even-contact rotors is calculated by my own computer program. Note that, in the case of 2-contact rotors, one does not multiply by n (which is 2) going from the second to the third column, because in that case the arrangements are symmetric.

The same type of backtracking algorithm as is used to solve the Eight Queens problem was used in my program to generate the numbers for even-contact rotors, but instead of trying various permutations of the output contact numbers from 1 to n, I instead tried permutations of the set of intervals I was using. This let me exploit a symmetry (instead of considering all possibilities for the duplicated and omitted intervals, I only needed to work with one), and divide the number of arrangements I generated by n, as well as reducing the number of levels the program went through to build an arrangement by one, since the two duplicate intervals of zero were fixed by an outer loop.

[Next] [Up] [Previous] [Index]