Pinned toot

<エニグマ暗号解読> 

チューリングは同じ部分群をBombeで探す。
マリアン・レイェフスキは巡回群の長さを不変量扱いに。
<新提案>
対称群を交代結び目で表すと、$φ=[0 3][1 4 2]$は
$In : $W = Knots()
$In : $W.from_gauss_code([-1, 4, -2, -5, -3, 1, -4, 2, 5, 3])
$In :$ K1.alexander_polynomial()
$Out : t^-1 - 1 + t$
$In :$ K1.jones_polynomial()
$Out : 1/t + 1/t^3 - 1/t^4$

に対して
$φ=[0 3 1 4 2]$は
$In : $W = Knots()
$In : $W.from_gauss_code([-1, -4, -2, -5, -3, 1, 4, 2, 5, 3])
$In :$ K1.alexander_polynomial()
$Out : 1$
$In :$ K1.jones_polynomial()
$Out : 1$

Pinned toot

全てのローター選択、ローター開始位置が暗号文とクリブから1対1の関係で論理的に求められる方法が必要だ。一方向関数ではないのだから。

「$X*Y*Z=A$となる、$X,Y,Z$を求めよ」
という問題なんだが...
エニグマ・ベクトル空間では一意になる筈なので解けるとは思うが、何を使えば...

Show thread
Pinned toot

アラン・チューリングへ提案 

Bombeを使う際、
・A⇒C⇒D⇒A
・B⇒D⇒E⇒B
のループを別扱いしていると思いますが、アルファベットをデジタルにすれば1ずれてるだけで同じです。
後は手作業で組み合わせを見つければよいので、Bombeの台数と所要時間が大幅に削減できます。(削減比率を計算中)
from sage.groups.perm_gps.symgp_conjugacy_class import default_representative
S = SymmetricGroup(26)
for p in Partitions(26):
print(default_representative(p, S))

によるとアルファベット26文字の対称群が作り出す部分群パターンはたったの2,436パターンしか無いんです!
(aを1に固定した場合
 更にbを2にする必要も無い)
総当りが403,291,461,126,605,635,584,000,000通り⇒2,436通りで絞り込みが可能になります。

Braid groups 

Sageのブレイド群の表現の仕方が先週ずっと分からなかったが、帰りの電車で何故か一瞬にして理解した。簡単な説明描いてよ...😭

これを使えば、エニグマ暗号機のローター設定をBRAID群と見做せて、アレキサンダー多項式を計算できるな。(このままでは解読時間が短くなる訳ではない)

doc.sagemath.org/html/en/refer

ポリアの定理 

を使えば、有限群が有限集合の数え上げになる...
このアプローチは5年ほど前に気になっていたものの、さっぱり分からずに放置していたのですが、また始めてみましょうか。
・組合せ論入門
・グラフの数え上げ 母関数を礎にして
・超高速グラフ数え上げ理論
・Mathematica組合せ論とグラフ理論

Sage Finite Permutation Groups 


profile_polynomial(variable='z')
が気になる。なんだろう、これ。
「The Cycle Polynomial of a Permutation Group」か....

doc.sagemath.org/html/en/refer

グロタンディークファンは世界に100億人は居そうです...
(まだ勉強可能なレベルに達してませんが、資料収集中です)

※エニグマ暗号機の組み合わせ数の端数を直しました・

この週末、SageMathで遊んでみました。理論的に知っているのと、実際に計算するのでは楽しさが違いますね😆
「SageMathで史実上のエニグマ解読方法を研究してみる」
docs.google.com/document/d/1Mx

マリアン・レイェフスキの計算エンジン 

①実際の巡回群を全て調べる
アルファベット6文字の場合
from sage.groups.perm_gps.symgp_conjugacy_class import conjugacy_class_iterator
S = SymmetricGroup(6)
for p in conjugacy_class_iterator([4,2]): print(S(p))

②巡回群の位数毎の個数を調べる
S26 = SymmetricGroup(26)
P = S26.cycle_index()
403291461126605635584000000* P

※貧弱なMac miniで計算すると、6文字でもかなり時間かかる。当時のBombeやコロッサスに比べるとこれでも相当に速いんだろうけど。

Sageの遊び方 

分かってきましたよ。マニュアルの例文を読み、気になる文章をコピペして実際に走らせて数字を適当に変えてみれば段々と意味が分かってくる。
教科書と違って実際の計算結果が見えるので、理解度が深まってくる...
細かい文法は覚えなくてもいい。

しかし似たような機能が、
・Finite Permutation Groups
・Groups
・Conjugacy classes of groups
などに散らばっているので機能を探しにくいですね。

エニグマ解読の不変量 

これで、対称群の部分群をアレキサンダー多項式とジョーンズ多項式を使うことで分類の為の不変量にします。
⇒今日やっと計算できたので、これから検証開始!
※これは手作業ではとても無理ですね。Sage凄い!
※疲れたので暫くステイホームで旅に出ます。

⇒後は、ジョーンズ多項式から逆に対称群を見つけられれば良いのですが。

Show thread

<エニグマ暗号解読> 

チューリングは同じ部分群をBombeで探す。
マリアン・レイェフスキは巡回群の長さを不変量扱いに。
<新提案>
対称群を交代結び目で表すと、$φ=[0 3][1 4 2]$は
$In : $W = Knots()
$In : $W.from_gauss_code([-1, 4, -2, -5, -3, 1, -4, 2, 5, 3])
$In :$ K1.alexander_polynomial()
$Out : t^-1 - 1 + t$
$In :$ K1.jones_polynomial()
$Out : 1/t + 1/t^3 - 1/t^4$

に対して
$φ=[0 3 1 4 2]$は
$In : $W = Knots()
$In : $W.from_gauss_code([-1, -4, -2, -5, -3, 1, 4, 2, 5, 3])
$In :$ K1.alexander_polynomial()
$Out : 1$
$In :$ K1.jones_polynomial()
$Out : 1$

エニグマ解読、色々考えて... 

一般線形群で多様体を考えたり、
置換行列で共役類を考えるより
5年前に考えておいた結び目理論を使う方がやはり便利そうだ。(特性方程式を簡単に使えるのは結び目位しか私の知識では思いつかないので)
当時はジョーンズ多項式とか知らなかったのに、凄い直感だな。
「組合せ論の基礎 (サイエンスライブラリ数学 9) 」P134
第5章 Polyaの方法 
例3 結び糸の数え上げ

エニグマの対称群が作る共役類 

「あるローター設定における対称群が作る静的な共役類」ではなく
「あるローター設定における対称群間の動的な共役類」を求める事ができれば、マリアン・レイェフスキの解読方法を拡張してBombe無しの計算で解読できると思うんだが...
こうなると置換行列ではなくて一般的な群の概念だけで考えられる。
Bombeの計算はある意味で毎回総当たり戦だけど、それをもっと綺麗に解読できる。
4枚ローターで事前準備するのにどれくらいの時間が掛かるんだろうか?

さて、何の文献を読めば共役類の勉強が出来るんだろう?
まずは世界の研究者が書いた論文を読んで理解しよう

マツコの知らないエニグマ解読洋書の世界 

洋書の世界ではエニグマ暗号機の解読に関する本はごまんとあるものの「解読情報をどう使った」などが95%。「どうやって解読したのかサラッと説明」が4%。「どういうロジックなのか」は1%。「数学的にどういう意味か?」で満足できるものは、ほぼ1冊も無い。趣味の論文めいたモノで数点見られるくらい。
(今調べ直したら、4年ほど前に知らべたファイルを入れてある保管庫に5個あった)
日本語訳だとサイモン・シン「暗号解読」だけど、あれもプラグ配線解読について、はほぼ何も言ってくれない。
すこぶる不満。😬

エニグマ解読を100行以内で書く言語 

MIPで解く方法を進めよう。解読時間はかかるけど、原理的にはPrologで書けば一番綺麗だな...
しかし、Prologで置換群を書こうとすると目標の100行以内に収める事が出来るだろうか?

更に、全変数に制約が掛けられる訳ではないし...(クリブの部分にしか掛けられない)

そうなるとPrologよりはMIPの方が短く書ける。

Show thread

置換群の性質について調べる所からか。

そうか、26×4次元?方程式にすればいいのかな...?
暗号文が増えれば解けそうだな。
要はこれってMIPでは?
(整数線形計画問題)
だったら、Pythonでもjuliaでも得意じゃん。
「セクシーな数学」のグレゴリー・チャイティンが無限次数ディオファントス方程式とか言ってたような気がする。あぁ、あっちの世界には行きたくないのに。

Show thread

「空手踊り」という奇妙な覚え方をしたので、カラテオドリさんの名前が未だに覚えられない。
(今気がついたけど、ひょっとしてあってる????...)
※ムックとガチャピンも子供の頃に逆に覚えたので、今でも分からない。

全てのローター選択、ローター開始位置が暗号文とクリブから1対1の関係で論理的に求められる方法が必要だ。一方向関数ではないのだから。

「$X*Y*Z=A$となる、$X,Y,Z$を求めよ」
という問題なんだが...
エニグマ・ベクトル空間では一意になる筈なので解けるとは思うが、何を使えば...

Show thread

結局、「分類」という方法に固執してると史実的なエニグマ解読と基本的には変わらないんだよな。そこを突破するアイデアは無いものか?件数が少なくなっても総当り的な考え方からは脱皮できていない。
何か新しい数学が必要だ。

Show thread

多様体を使おうが、結び目を使おうがエニグマ解読の方針自体に大きな違いは無いな。。。結び目だと視覚的になるけど。先の展開を考えると多様体の方が表現的にキャパがありそう?
いや、結局は同じことをしようとしているのでは?ボルツマンモデルで統計力学にもっていくと。。。

Show thread

多様体を勉強しないとエニグマの置換群の一般線形群が作り出す26次の行列をイメージできない。

Show more
Mathtodon

A Mastodon instance named Mathtodon, where you can post toots with beautiful mathematical formulae in TeX/LaTeX style.