In summer 1940, Germany demanded access to Swedish telephone cables to send encoded messages from occupied Norway back to the homeland. Sweden acceded but tapped the lines and discovered that a new cryptographic system was being used. The T52 Geheimschreiber (or G-schreiber in short), with more than 800 quadrillion settings, was conveying top-secret information but seemed immune to a successful codebreaking attack.

T52
The Siemens & Halske T52 — also known as the Geheimfernschreiber ("secret teleprinter") or Schlüsselfernschreibmaschine (SFM) — was a World War II German cipher machine and teleprinter produced by the electrical engineering firm Siemens & Halske. The instrument and its traffic were codenamed Sturgeon by British cryptanalysts.

The Swedish intelligence service assigned mathematician Arne Beurling to the task, giving him only a pile of coded messages and no knowledge of the mechanism that had been used to encode them. But after two weeks alone with a pencil and paper he announced that he had decoded the messages. He also described how a complementary machine could be built to decode the messages automatically. Thanks to his work, Swedish officials learned in advance of the impending invasion of the Soviet Union. Unfortunately, Stalin's staff disregarded their warnings. In his book The Codebreakers1 Bengt Beckman accounts of the exploit. In his foreword to the book, Peter Jones writes:

To this day no one knows exactly how Beurling reasoned during the two weeks he spent on the G-Schreiber. In 1976 he was interviewed about his work by a group from the Swedish military, and became extremely irritated when pressed for an explanation. He finally responded, "A magician does not reveal his tricks." It seems the only clue Beurling ever offered was the remark, cryptic itself, that threes and fives were important.

Assignment

In the end, the procedure used by the T52 Geheimschreiber did not turn out to be al too complicated. It uses an alphabet of $$m$$ symbols that are all different and have a fixed order. The positions of the symbols in the alphabet are indexed $$0, 1, \ldots, m - 1$$.

In addition, two integers $$a$$ and $$b$$ are used as the key for encoding and decoding. Each symbol at position $$x$$ in the alphabet is encoded as the symbol at position $$E(x)$$ in the alphabet, where \[E(x) = (ax + b)\ \textrm{mod}\ m \qquad (0 \leq x < m)\] and the operator $$\textrm{mod}$$ results in the remainder after integer division. Each symbol at position $$x$$ in the alphabet is decoded as the symbol at position $$D(x)$$ in the alphabet, where \[D(x) = a'(x - b)\ \textrm{mod}\ m \qquad (0 \leq x < m)\] and $$a'$$ is the multiplicative inverse of $$a$$ modulo $$m$$. In other words, $$a'$$ is the integer in the interval $$[0, m[$$ that satisfies the equation \[1 = aa'\ \textrm{mod}\ m\] The multiplicative inverse of $$a$$ only exists if $$a$$ and $$m$$ are coprime. This is the case if the greatest common divisor of $$a$$ and $$m$$ equals 1. If this is the case, there is only one integer in the interval $$[0, m[$$ that satisfies the equation for the multiplicative inverse.

When the Germans noticed that messages sent using the T52 could be easily decoded, they tried to make the encryption procedure more complex. This was done by not encoding a message once but twice. First a message was encoded by a T52 that used keys $$a_1$$ and $$b_1$$, and the result was encoded again by a T52 that used keys $$a_2$$ and $$b_2$$. This is only possible if the two machines use the same alphabet. From the observation that \[E_2(E_1(x)) = (a_2((a_1x + b_1)\ \textrm{mod}\ m) + b_2)\ \textrm{mod}\ m = (a_1a_2x + (a_2b_1 + b_2))\ \textrm{mod}\ m\] it follows that this has the same effect as encoding the message only once by a T52 that used keys a_1a_2$$ and $$(a_2b_1 + b_2)$.

Your task is to define a class T52 whose objects represent T52 Geheimschreiber machines that can be used to encode and decode messages according to the procedures outlined above. This class must support at least the following methods:

In should also be possible to add two objects of the class T52 using the + operator. This should result in a new object of the class T52 that represents a T52 Geheimschreiber machine that encodes messages in the same way as if we would first encode the message using the machine to the left of the + operator and then encode the result once more using the machine to the right of the + operator. If the two T52 objects that are added do not use the same alphabet of symbols, an AssertionError must be raised with the message alphabets are different.

Example

>>> machine1 = T52(3, 5, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')

>>> machine1.encodeSymbol('G')
'X'
>>> machine1.encodeSymbol('S')
'H'
>>> machine1.encodeSymbol('-')
'-'

>>> machine1.decodeSymbol('X')
'G'
>>> machine1.decodeSymbol('H')
'S'
>>> machine1.decodeSymbol('-')
'-'

>>> machine1.encode('G-SCHREIBER')
'X-HLAERDIRE'
>>> machine1.decode('X-HLAERDIRE')
'G-SCHREIBER'

>>> machine2 = T52(17, 11, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')
>>> machine2.encode('X-HLAERDIRE')
'M-AQLBOKROB'

>>> machine12 = machine1 + machine2
>>> machine12.encode('G-SCHREIBER')
'M-AQLBOKROB'

>>> T52(4, 5, 'ABCDEFGHIJKLMMLKJIHGFEDCBA')
Traceback (most recent call last):
AssertionError: alphabet has repeated symbols

>>> T52(4, 5, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')
Traceback (most recent call last):
AssertionError: 4 and 26 are not coprime

>>> machine1 + T52(17, 11, 'abcdefghijklmnopqrstuvwxyz')
Traceback (most recent call last):
AssertionError: alphabets are different