Its nice to finally find modern material directly on topic – writ respect to Turings On Permutation’s manuscript. its also interesting to take the modern presentation and compare it to Turing’s world, of probably 1938. For Turing writing shows his orientation (and assuredly the context of his writing): cryptanalysis.

We can assume that Turing went on a GCCS course in 1938ish and learned the lingo. In particular, he probably learned to think in terms of “beetles” and uprights/rods and drums.

There is just something rather unpretentious about the writing style of Diaconis – specially when you consider when its dealing with what is, if written without the obliqueness-inducing academic language – a verboten topic: cryptographic wheel wiring. Rather like Turing, whose obliqueness was pre-functory doing little to hide the context – analyzing german enigma Italian herbern and American sigaba machine,  Diacnois in 1996 was perhaps reflecting the time times (1996) when crypto walls were tumbling down.

image

http://statweb.stanford.edu/~cgates/PERSI/papers/random_matrices.pdf

A second paper does us proud, tool

image

http://statweb.stanford.edu/~cgates/PERSI/papers/rwfg.pdf

Random Walks on Finite Groups: A Survey of Analytic Techniques. P. Diaconis L. Saloff-Coste, Prob. Meas. on Groups XI, H. Heyer (ed.), World Scientific Singapore, pp. 44-75. [PDF]

we get simple presentation of how markov chains relate to measure functions and probability distributions

image 

 

we see a simple presentation of “detailed balance”

image

we see folks heading for fourier basis and invariant theory

image

we also see why one is interested in calculating under different norms

image

in general, we now see how “normalized counting” is part of the 1936+ era “secret sauce” – turning all this theory and algebra into practical ways of mounting cryptanalytical attacks. One assumes that Turing was taught the isomorph attack on enigma for example, in 1938.

Concerning cosets, normal subgroups and aperiodicity and An, we see

image

We see now WHY turing was concerned to search out those uprights which were exactly Sn or An.

Next, we see another specific Turing component – undiscussed in his work (since he is talking to an elite audience).

image

In Turings work, this was a simplification of his first thought (concerning delta), modeled by Diaconis (above)

image

(we though the 1 was there to count up how my edges landed on each output pad of the wheel, in the fano plane!)

Specifically, we also see an An argument pertinent to understanding the Turing manuscript:

image

Just as interesting is the material on class functions (and bi-invariancy):

image

Advertisements

About home_pw@msn.com

Computer Programmer who often does network administration with focus on security servers. Very strong in Microsoft Azure cloud!
This entry was posted in coding theory. Bookmark the permalink.