A substitution cipher is a simple historical encryption technique in which every letter of the alphabet is replaced with a unique letter in the same alphabet.
Writing a message on a dvorak keyboard as if it was qwerty would be an example of a substitution cipher.
(defvar qwerty " -=qwertyuiop[]\asdfghjkl;'zxcvbnm,./")
QWERTY
(defvar dvorak " []',.pyfgcrl/=\aoeuidhtns-;qjkxbmwvz")
DVORAK
(defun substitution-cipher (x a b)
(aref b (position x a)))
SUBSTITUTION-CIPHERAbove, I defined a function which will return the value of the cipher character to a given plain character. If we wanted to apply this to a text we would need:
(defun encode-decode (text a b)
(map 'string (lambda (i) (substitution-cipher i a b))
(string-downcase text)))
ENCODE-DECODE
(encode-decode "the first message" qwerty dvorak)
yd. ucpoy m.ooai.
(encode-decode (encode-decode "the first message" qwerty dvorak) dvorak qwerty)
the first messageA substitution cipher such as qwerty to dvorak would correspond to an element in \(\Sigma_{36}\) the symmetric group on 36 letters which contains exactly 36! = 371993326789901217467999448150835200000000 elements. This means there are exactly 371993326789901217467999448150835200000000 different substitution ciphers. However, even though the large number of such ciphers makes the scheme resistant to brute-force attacks, one can easily break it using statistical approaches.
In any case, today’s problem is inspired by a post by Matt Adereth which in turn inspired by a question that Tommy Hall posed:
What is the smallest \(m\in\mathbb{N}\) such that for every permutation \(\sigma\in \Sigma_{36}\) the permutation \(\sigma^ m\) is the unit permutation?
Now, because of Legendre Theorem, any such \(m\) must divide 36! the order of \(\Sigma_{36}\) which, as you can guess, not very helpful. Well, at least we know that (1) such a number exists, and (2) it must divide 36!.
Before I go any further, I need to define what a cycle is: a cycle is the trace (a.k.a. the orbit) of an element under successive applications of the cipher.
(defun cycle (x a b)
(do* ((z (list x) (append z (list y)))
(y (substitution-cipher x a b) (substitution-cipher y a b)))
((equal x y) z)))
CYCLELet me repeat what Matt got:
(cycle #\ qwerty dvorak)
($
(cycle #\a qwerty dvorak)
(a)
(cycle #\m qwerty dvorak)
(m)
(cycle #$$ qwerty dvorak)
(] =)
(cycle #\, qwerty dvorak)
(, w)
(cycle #\. qwerty dvorak)
(. v k t y f u g i c j h d e)
(cycle #$$ qwerty dvorak)
([ / z ; s o r p l n b x q ' -)I have 4 cycles of length 1, 2 cycles of length 2, 1 cycle of length 14 and 1 cycle of length 15. As Matt observes, the smallest \(m\) in this case is the least common multiple of 2, 14 and 15 which is
(lcm 2 14 15)
210For an arbitrary cipher that number would be:
(defun mystery-number (a b)
(apply #'lcm
(remove-duplicates
(sort (map 'list (lambda (x) (length (cycle x a b))) a)
#'<))))
MYSTERY-NUMBERSo, let us calculate this number for various cases
(defvar colemak " -=qwfpgjluy;[]\arstdhneio'zxcvbkm,./")
COLEMAK
(defvar random-layout " /.,mnbvcxzasdfghjkl;'$$[poiuytrewq=-")
RANDOM-LAYOUT
(mystery-number qwerty dvorak)
210
(mystery-number qwerty colemak)
42
(mystery-number dvorak colemak)
24
(mystery-number colemak random-layout)
90Still, this doesn’t solve the original question I posed. What would be the largest such mystery number for all possible permutations in \(\Sigma_{36}\)? Since I can’t go over all 371993326789901217467999448150835200000000 elements, I should find a better way.
Recall that the number we are looking for is a least common multiple of a collection of numbers \(x_1\) through \(x_\ell\) such that the sum \(x_1 + \cdots + x_\ell = 36\) where we want that \(1\leq x_1\leq \cdots \leq x_\ell\leq 36\).
Today, I will use the brute-force method because I need to teach soon and I don’t have much time, and 36 is relatively small.
The following function returns the list of all possible k-partitions of a number n.
(let ((parlist-table (make-hash-table :test #'equal)))
(defun parlist(n k)
(let ((u (1- k))
(m (truncate (/ n k))))
(cond
((< n 0) nil)
((< k 1) nil)
((= k 1) (list (list n)))
((= k 2) (loop for i from 1 to m collect (list i (- n i))))
(t (or (gethash (list n k) parlist-table)
(setf (gethash (list n k) parlist-table)
(do ((i 1 (1+ i))
(temp nil (nconc temp
(mapcar
(lambda (x) (cons i (mapcar (lambda (y) (+ y (1- i))) x)))
(parlist (- n i (* u (1- i))) u)))))
((> i m) temp)))))))))
PARLISTLet me test it:
(parlist 13 4)
((1 1 1 10) (1 1 2 9) (1 1 3 8) (1 1 4 7) (1 1 5 6) (1 2 2 8) (1 2 3 7)
(1 2 4 6) (1 2 5 5) (1 3 3 6) (1 3 4 5) (1 4 4 4) (2 2 2 7) (2 2 3 6)
(2 2 4 5) (2 3 3 5) (2 3 4 4) (3 3 3 4))I need to go over all possible partitions with varying k and calculate the least common multiples of the resulting numbers. Then pick the maximum.
(defun helper (n)
(loop for k from 1 to n collect
(cons k (car (sort (mapcar
(lambda (x) (apply #'lcm x))
(parlist n k))
#'>)))))
HELPERAnd, the result is
(sort (helper 36) (lambda (x y) (> (cdr x) (cdr y))))
((5 . 13860) (6 . 9240) (7 . 9240) (8 . 5460) (9 . 5460) (4 . 5005)
(10 . 4620) (11 . 4620) (12 . 2310) (13 . 2310) (3 . 1716) (14 . 1260)
(15 . 1260) (16 . 840) (17 . 840) (18 . 420) (19 . 420) (20 . 420)
(21 . 420) (2 . 323) (22 . 210) (23 . 210) (24 . 105) (25 . 84) (26 . 60)
(27 . 60) (1 . 36) (28 . 30) (29 . 30) (30 . 15) (31 . 12) (32 . 6)
(33 . 6) (34 . 3) (35 . 2) (36 . 1))So, there is a permutation \(\sigma\in \Sigma_{36}\) which consists of 5 cycles and when composed with itself 13860 times will return unit, and no smaller number would work.
My hunch is that the number of cycles is related to the square root, but I will have to come back to this later.
(car (sort (helper 4) (lambda (x y) (> (cdr x) (cdr y)))))
(1 . 4)
(car (sort (helper 16) (lambda (x y) (> (cdr x) (cdr y)))))
(3 . 140)
(car (sort (helper 25) (lambda (x y) (> (cdr x) (cdr y)))))
(4 . 1260)