まげ店長 @MageManager@mathtod.online

◎ブレイド群によるエニグマ暗号解読
具体的な形にするのに半年はかかると思うので、忘れないようにメモ。

チューリングは同じ部分群を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$

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通りで絞り込みが可能になります。

要点：「類体論へ至る道」をやって良かった。

前にも感動してちょっと書きましたが、エニグマ暗号解読って有限巡回群の直積を使うんですよね。今までこれに関する定理を知らなかったんですが、今やってる有限アーベル群は思い切りエニグマ暗号解読です。難しいけどワクワクします。エニグマの専門書でも（私が理解できてないからかもしれないけど）少なくとも和書ではこのアプローチは皆無です。大抵は長々しく日本語で説明が書かれてますが、そこに規則性は視えないわけで。

「結び目と素数」という楽しそうな本を再発見。今やってる事とも外れそうじゃないし、結び目と繋がるっていうのが良さそうです。

#類体論へ至る道
（証明　補題（３））
$(a_1,a_2)\in H_1\cap H_2$とすると
　$(a_1,a_2)\in H_1→a_2=e_2$
　$(a_1,a_2)\in H_2→a_1=e_1$
∴$(a_1,a_2)=(e_1,e_2)$
∴$H_1\cap H_2=\{(e_1,e_2)\}$
（証明終　補題（３））

#類体論へ至る道
（証明　補題（２））
$H_1$に示し、$H_2$も同じ。

○$H_1$が$G$の部分群である事。
$(a_1,e_2),(b_1,e_2)\in H_1$とすると
　$(a_1,e_2)(b_1,e_2)=(a_1b_1,e_2e_2)$
　　$=(a_1b_1,e_2)\in H_1$
$(a_1,e_2)\in H_1$とすると
　$(a_1,e_2)^{-1}=(a_1^{-1},e_2)\in H_1$

○$H_1$が$G$の正規部分群である事。
$(b_1,b_2)\in G_1×G_2,$
$(a_1,e_2)\in H_1$とすると
　$(b_1,b_2)(a_1,e_2)(b_1,b_2)^{-1}$
　$=(b_1,b_2)(a_1,e_2)(b_1^{-1},b_2^{-1})$
　$=(b_1a_1b_1^{-1},b_2a_2b_2^{-1})$
　$=(b_1a_1b_1^{-1},e_2)\in H_1$
∴$(b_1,b_2)H_1(b_1,b_2)^{-1}\subset H_1$
（証明終　補題（２））

#類体論へ至る道
（証明　補題（１））
○$H_1$と$H_2$の元の積で表せる事。
$∀(a_1,a_2)\in G_1×G_2$とすると
　$(a_1,a_2)=(a_1,e_2)(e_1,a_2)$
　$\in H_1H_2$…⑧

○一意的に表せる事。
　$(a_1,a_2)=x_1x_2$
　　　$(x_1\in H_1，x_2\in H_2)$
　$→x_1=(a_1,e_2),$
　　　$x_2=(e_1,a_2)$
を示せば良い。

$x_1\in H_1$より
　$x_1=(b_1,e_2)(∃b_1\in G_1),$
　$x_2=(e_1,c_2)(∃c_2\in G_2)$
と表される。このとき
　$x_1x_2=(b_1,e_2)(e_1,c_2)$
　　　　$=(b_1,c_2)$

仮定より$x_1x_2=(a_1,a_2)$
∴$(a_1,a_2)=(b_1,c_2)$
∴$a_1=b_1,a_2=c_2$

∴ $x_1=(b_1,e_2)=(a_1,e_2)$
　$x_2=(e_1,c_2)=(e_1,a_2)$
（証明終　補題（１））

#類体論へ至る道
補題ーーーーーーーーーーーー
群の直積$G_1×G_2$に対して、
その部分集合
　$H_1=\{(a_1,e_2)|a_1\in G_1\}$
　　$\subset G_1×G_2$
　$H_2=\{(e_1,a_2)|a_2\in G_2\}$
　　$\subset G_1×G_2$
を考えると、
$H_1,H_2$は次の性質を満足する。

（１）$G$の任意の元は$H_1$と$H_2$の
　　　元の積として一意的に表せる。
　　　…⑤

（２）$H_i(i\in \mathbb{N})$は
　　　$G_1×G_2$の正規部分群…⑥

（３）$H_1\cap H_2=\{e_1,e_2\}$…⑦

#類体論へ至る道
←①②③④：
（証明）
補題⑧より
　$G=H_1H_2$

$g’\in H_1\cap H_2,(g’\in G)$とすると、
　$e\in H_1\cap H_2$で
　$g’e=eg’$なので
補題１⑤より
　$g’=e$
∴$H_1\cap H_2=\{e\}$

∴$G$は$H_1$と$H_2$の直積に分解される。
（証明終）

#類体論へ至る道
（証明）
→①：
$h_1\in H_1,h_2\in H_2$のとき
$H_1$が正規部分群なので
　$h_2^{-1}h_1h_2 \in H_1$
∴$h_1^{-1}h_2^{-1}h_1h_2 \in H_1$…⑨

また$H_2$が正規部分群なので
　$h_1^{-1}h_2^{-1}h_1 \in H_2$
∴$h_1^{-1}h_2^{-1}h_1h_2\in H_2$…⑩

∴$h_1^{-1}h_2^{-1}h_1h_2=(h_2h_1)^{-1}(h_1h_2) $
⑨⑩より
　$\in H_1∩H2$
補題⑦より
　$=\{e\}$

∴$(h_2h_1)^{-1}(h_1h_2)=e$となり
∴$h_1h_2=h_2h_1$
∴$H_1$の各元と$H_2$の各元は可換。
∴ ①が示される。

→②：補題⑧より示される。
→③：補題⑦より示される。
→④：補題⑤より示される。
（証明終）

#類体論へ至る道
P118　問題
群$G$とその正規部分群$H_1,H_2$に対して
　$G=H_1×H_2$
が成り立つ為には次の各条件
が必要十分である。

1.$x_1x_2=x_2x_1,$
　$(∀x_1\in H_1,∀x_2\in H_2)$…①
かつ
任意の$x\in G$が$x=x_1x_2$と
一意的に表せる。…②

2.$H_1\cap H_2=\{e\}$…③
　　かつ
　$G=H_1H_2$…④

#類体論へ至る道
P117　原始根
$r$を法$p$の原始根とするとき、
　$r^x\equiv 1(\mod p)…①⇔$
　　$x\equiv 0(\mod p-1)$…②

（証明）
定義：
　$a,b\not\equiv 0(\mod p) $のとき
　$a\equiv b(\mod p)⇔$
$ind_ga\equiv ind_gb(\mod p-1)$
　$ind_g1=0,ind_gg=1$

①より
　$r^x\equiv 1(\mod p)$
$ind$をとり
　$ind_rr^x\equiv ind_r1(\mod p-1)$
定義より
　$x\equiv 0(\mod p-1)$
∴①$⇔$②
（証明終）

#類体論へ至る道
P117　系（2校）
$F$を有限体とすると$F^✗$は巡回群。…①
特に$p$を法とする既約剰余類群
　$(\mathbb{Z}/p\mathbb{Z})^✗$は巡回群。…②

（証明）
$F^✗$は有限体$F$から
$0$を除いた乗法群なので
$F$の有限部分群。
$M=F^✗$とすると
$M$は$F^✗$の有限部分群。
∴定理8.2より①が成り立つ。

P12系1より
$p$を法とする既約剰余類群
　$(\mathbb{Z}/p\mathbb{Z})^✗$
は乗法で群を成す。

P29定理2.5より
位数は$φ(p)$なので
$(\mathbb{Z}/p\mathbb{Z})^✗$は$F^✗$の有限部分群。
∴定理8.2より②が成り立つ。
（証明終）

#類体論へ至る道
（１）$(a^k)^{n’}=a^{kn’}=a^{k’dn’}$
　$=(a^n)^{k’}=e^{k’}=e$
（２）$(a^k)^l=e,(l\in \mathbb{N})$とする。
このとき$a^{kl}=e$と補題１より
$kl$は$a$の位数$n$によって割り切れる。
$n|kl$より$n’|l$
∴$n’≤l$
∴$(a^k)^l=e,(l\in \mathbb{N})$ならば$n’≤l$

（１）（２）より、
$n’$は$(a^k)^l=e$を満足する
自然数$l$のうち最小の正整数。
∴$a^k$の位数は$n’$
（証明終）

#類体論へ至る道
補題４（定理3.6系１）
$r,s$を自然数とする。群$G$の元$a$の位数を$rs$とすると、
元$a^r$の位数は$s$であり、
元$a^s$の位数は$r$
$|a|=rs→|a^r|=s,|a^s|=r$

（証明）
補題５より得られる。
（証明終）

補題５
（証明）
$G$を$a$によって生成される
位数$n$の巡回群とする。
$G$の元$a^k$の位数は$\frac{n}{(n,k)}$となる。
　$|a^k|=\frac{n}{(n,k)}$
（証明）
$G=$ < $a$ > として、
$n$と$k$の最大公約数を$d$とする。
このとき
$n=n’d,k=k’d$とすると、$(n’,k’)=1$で
　$\frac{n}{(n,k)}=\frac{n}{(d)}=n’$
∴$a^k$の位数が$n’$であることを
　示せば良い。

#類体論へ至る道
補題３
群$G$の2つの元$a,b$が可換で、位数が$m,n$とする。
$m$と$n$が互いに素であれば元$ab$の位数は$mn$。

（証明）
群$G$の単位元を$e$とする。
（１）$(ab)^{mn}=e$を示す。
　$(ab)^{mn}=a^{mn}b^{mn}$
　$=(a^m)^n(b^n)^m$
　$=e^ne^m=ee=e$

（２）
$(ab)^l=e,(l\in \mathbb{N})$と仮定する。
$a$と$b$は可換なので、
　$a^lb^l=e$
∴$a^l=(b^{-1})^l$
$m$乗すると
　$(b^{-1})^{lm}=(a^l)^m=(a^m)^l$
　$=e^l=e$
∴$(b^{-1})^{lm}=e$
∴$b^{lm}=e$
補題１より
∴$n|lm$
仮定より$(m,n)=1$より
　$n|l$

同様に$m|l$
∴$mn|l$なので
∴$mn≤l$

（１）（２）より
$mn$は$(ab)^l=e$を満たす自然数$l$のうち最小の整数なので
$ab$の位数は$mn$
（証明終）

#類体論へ至る道
ここで
　$m_1=p_1^{e_1}…p_r^{e_r}$
　$m_2=p_{r+1}^{f1}…p_{r+s}^{f_s}$
　　$(0≤e_i,f_i)$
　$n_1=p_1^{e’_1}…p_r^{e’_r}$
　$n_2=p_{r+1}^{f’_1}…p_{r+s}^{f’_s}$
　　$(0≤e'_i,f'_i)$
とおけば　
　$m=m_1m_2,$
　$n=n_1n_2,$
　$l=m_1n_2$

$a_1=a^{m_2},b_1=b^{n_1}$
なる元を考えると、
$a_1,b_1$の位数は補題３によって
　$|a_1|=|a^{m_2}|=m_1,$
　$|b_1|=|b^{n_1}|=n_2$
$(m_1,n_2)=1$なので補題４より
$a_1b_1$の位数は$m_1n_2=l$
（証明終

#類体論へ至る道
補題２
群$G$の可換な2つの元$a,b$の位数が
それぞれ$m,ｎ$とする。
$m$と$n$の最小公倍数を$l$とするとき、
$G$に位数$l$の元が存在する。
（証明）
$m$と$n$を素因数分解して
　$m=p_1^{e_1}…p_r^{e_r}p_{r+1}^{f1}…p_{r+s}^{f_s}$
　　$(0≤e_i,f_i)$
　$n=p_1^{e’_1}…p_r^{e’_r}p_{r+1}^{f’_1}…p_{r+s}^{f’_s}$
　　$(0≤e'_i,f'_i)$
　$(e_1≥e’_1,…,e_r≥e’_r,$
　$f_1≤f'_1,…,f_s≤f'_s)$
となる様に表現する事ができる。

このとき、
$m$と$n$の最小公倍数は
　$l=p_1^{e_1}…p_{r+1}^{f'_1}…p_{r+s}^{f'_s}$

#類体論へ至る道
P27より
既約剰余類群の位数は$φ(p)$なので有限、
$(\mathbb{Z}/p\mathbb{Z})^✗$は巡回群。
∴②が成り立つ。
（証明終）

補題１
$G$の元$a$の位数を$n$とする。
このとき、非負整数$k,l$について
　$a^k=e⇔k\equiv 0(\mod n)$

（証明）
→：$k$を$n$で割ると
　$∃q,r\in \mathbb{Z},k=nq+r$
　$(0 ≤ r < n)$
$n$は$a$の位数なので、$a^n=e$
∴$a^k=a^{nq+r}=(a^n)^qa^r=e^qa^r$

仮定により
　$a^r=a^k=e$
∴$a^r=e$で$0 ≤ r < n$

ところが$n$は$a^l=e$となる
$l$の中で最小の正整数なので
　$r=0$
∴$k=nq$
∴$k\equiv 0(\mod n)$

←：$k\equiv 0(\mod n)$とすると、
ある整数$q$が存在して
$k=nq$と表される。
∴$a^k=a^{nq}=(a^n)^q=e^q=e$
∴$a^k=e$
（証明終）

#類体論へ至る道
P117　系
$F$を有限体とすると$F^✗$は巡回群。…①
特に$p$を法とする既約剰余類群
　$(\mathbb{Z}/p\mathbb{Z})^✗$は巡回群。…②

（証明）
$|F|=q$とする。
$F^✗$の位数は$q-1$なので
$F^✗$に位数$q-1$の元が
存在することを示せば良い。

この為に、$F^✗$の元$α$の位数$m$が
　$m < q-1$と仮定する。
このとき$F^✗$の中には
位数が$m$より大きなものが
存在することを示せば、
$F^✗$に位数$q-1$の元が
あることになる。

P116系より$F^✗$の元のうち、
たかだか$m$個の元が
　$X^m-1$
の根になる。
　$m < q-1$
なので$F^✗$にはある元$β$が存在して
　$β^m-1\neq 0$
この$β$の位数を$n$とすると
補題１より
　$β^m\neq 1⇔n\nmid m$
∴$m$と$n$の最小公倍数を$l$とすれば
　$m < l$である。

補題２より$F^✗$には位数$l$の元が存在する。
∴定理8.2より①が成り立つ。

#類体論へ至る道
P116　定理8.2
$F$を可換体とする。$M$を乗法群
　$F^✗=\{a(\in F)|a\neq 0\}$
の有限部分群であれば$M$は巡回群。

（証明）
$p$を任意の素数とし、$F$における方程式
　$x^p=1$
を考える。

$F$は体なのでP50問題より$x^p=1$は
$F$内にたかだか$p$個の解しか持たない。

よって部分群の$M$に属する解も
たかだか$p$個の解しか持たない。

∴P116定理8.1の系より$M$は巡回群。
（証明終）