Pinned post

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

Pinned post

<エニグマ暗号解読> 

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

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

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

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

Show thread

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

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


(証明 補題(3))
$(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)\}$
(証明終 補題(3))

Show thread


(証明 補題(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$
(証明終 補題(2))

Show thread


(証明 補題(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)$
(証明終 補題(1))

Show thread


補題ーーーーーーーーーーーー
群の直積$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$は次の性質を満足する。

(1)$G$の任意の元は$H_1$と$H_2$の
   元の積として一意的に表せる。
   …⑤

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

(3)$H_1\cap H_2=\{e_1,e_2\}$…⑦

Show thread


←①②③④:
(証明)
補題⑧より
 $G=H_1H_2$

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

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

Show thread


(証明)
→①:
$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$の各元は可換。
∴ ①が示される。

→②:補題⑧より示される。
→③:補題⑦より示される。
→④:補題⑤より示される。
(証明終)

Show thread


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より②が成り立つ。
(証明終)


(1)$(a^k)^{n’}=a^{kn’}=a^{k’dn’}$
 $=(a^n)^{k’}=e^{k’}=e$
(2)$(a^k)^l=e,(l\in \mathbb{N})$とする。
このとき$a^{kl}=e$と補題1より
$kl$は$a$の位数$n$によって割り切れる。
$n|kl$より$n’|l$
∴$n’≤l$
∴$(a^k)^l=e,(l\in \mathbb{N})$ならば$n’≤l$

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

Show thread


補題4(定理3.6系1)
$r,s$を自然数とする。群$G$の元$a$の位数を$rs$とすると、
元$a^r$の位数は$s$であり、
元$a^s$の位数は$r$
$|a|=rs→|a^r|=s,|a^s|=r$

(証明)
補題5より得られる。
(証明終)

補題5
(証明)
$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’$であることを
 示せば良い。

Show thread


補題3
群$G$の2つの元$a,b$が可換で、位数が$m,n$とする。
$m$と$n$が互いに素であれば元$ab$の位数は$mn$。

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

(2)
$(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$
補題1より
∴$n|lm$
仮定より$(m,n)=1$より
 $n|l$

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

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

Show thread


ここで
 $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$の位数は補題3によって
 $|a_1|=|a^{m_2}|=m_1,$
 $|b_1|=|b^{n_1}|=n_2$
$(m_1,n_2)=1$なので補題4より
$a_1b_1$の位数は$m_1n_2=l$
(証明終

Show thread


補題2
群$G$の可換な2つの元$a,b$の位数が
それぞれ$m,n$とする。
$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}$

Show thread


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

補題1
$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$
(証明終)

Show thread


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$とすると
補題1より
 $β^m\neq 1⇔n\nmid m$
∴$m$と$n$の最小公倍数を$l$とすれば
 $m < l$である。

補題2より$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$は巡回群。
(証明終)

Show older
Mathtodon

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