Trending News: 群之可解性威脅情報指標 Indicators of compromise (IoC)Palo Alto Firewall URL過濾 以及 Application Block Page群NP-Completeness異常檢測的問題分類異常檢測的方法評估異常檢測簡介 Anomaly Detection高斯消去法Vectors時間複雜度不同的Turing MachineTuring Machine熵 Entropy資訊測量符號Mutual InformationPalo Alto Firewall 防火牆 Policy 政策 設定Palo Alto 防火牆 NAT (Network Address Translation) 設定《研究生完全求生手冊》讀後心得：研究生必須學會的方法、秘訣與淺規則密碼系統 RSA 攻防中國餘式定理 Chinese Remainder Theorem 與 同構 Isomorphism 特性Square Multiply 演算法尤拉函數 Euler’s totient function整數複雜度量測如何 安裝 Palo Alto VM《長銷》讀後心得：內容、定位、行銷、平台，從個人創作到企業經營都要懂的打造經典之道
週三. 9 月 18th, 2024
Trending News: 群之可解性威脅情報指標 Indicators of compromise (IoC)Palo Alto Firewall URL過濾 以及 Application Block Page群NP-Completeness異常檢測的問題分類異常檢測的方法評估異常檢測簡介 Anomaly Detection高斯消去法Vectors時間複雜度不同的Turing MachineTuring Machine熵 Entropy資訊測量符號Mutual InformationPalo Alto Firewall 防火牆 Policy 政策 設定Palo Alto 防火牆 NAT (Network Address Translation) 設定《研究生完全求生手冊》讀後心得：研究生必須學會的方法、秘訣與淺規則密碼系統 RSA 攻防中國餘式定理 Chinese Remainder Theorem 與 同構 Isomorphism 特性Square Multiply 演算法尤拉函數 Euler’s totient function整數複雜度量測如何 安裝 Palo Alto VM《長銷》讀後心得：內容、定位、行銷、平台，從個人創作到企業經營都要懂的打造經典之道
週三. 9 月 18th, 2024

群之可解性

目錄

Definition 2.7

首先讓我們定義G為一個群，我們說G是solvable/soluble(可解)的話代表存在filtration G = G_{0} \rhd G_{1} \rhd \cdots \rhd G_{n} = \{e\}使得說G_{i}/G_{i+1}是abelian的

照這個定義來看如果是要解多項式f \in Q[x]的話就需要滿足求根式解

Proposition 2.8

如果G是solvable的話，則G的subgroups以及商數皆為solvable

證明

讓G = G_{0} \rhd G_{1} \rhd \cdots \rhd G_{n} = \{e\}使得G_{i}/G_{i+1}屬於abelian

讓H < G屬於subgroup

    \[\Rightarrow H = H \cap G_{0} \rhd H \cap G_{1} \rhd \cdots H \cap G_{n} = \{e\}\]

    \[(H \cap G_{i})/(H \cap G_{i+1}) \hookrightarrow G_{i}/G_{i+1} &\Rightarrow (H \cap G_{i})/(H \cap G_{i+1}) \>\> is \>\> abelian.\]

    \[\Rightarrow H \>\> is \>\> solvable\]

假設H \lhd G，則G_{i}H < G以及G_{i+1}H \lhd G_{i}H.

    \[G_{i}/G_{i+1} \twoheadrightarrow (G_{i}H)/(G_{i+1}H)\]

    \[\Rightarrow (G_{i}H)/(G_{i+1}H) \cong (G_{i}H/H)/(G_{i+1}H/H) \>\> is \>\> abelian.\]

    \[\Rightarrow G/H \>\> is \>\> solvable.\]

範例

(1)D_{n} = <x, y| x^{n} = y^{2} = e, yxy^{-1} = x^{-1}>屬於solvable.

證明：D_{n} \rhd <x> \rhd \{e\}, D_{n}/<x> \cong \mathbb{Z}/2\mathbb{Z}, <x> \cong \mathbb{Z}/n\mathbb{Z}

(2)S_{3} \cong D_{3}屬於solvable

(3)S_{4}屬於solvable

(4)如果n \geq 5則S_{n}不屬於solvable，(\xRightarrow[\text{Galois}]{} f \in Q[x], deg(f) \geq 5,一般來說無法在求根式解解出)

證明：假設我們有一個filtration S_{n} = G_{0} \rhd G_{1} \rhd \cdots \rhd G_{n} = \{e\}使得G_{i}/G_{i+1}是abelian的，G_{i}本身應該會包含在S_{n}上所有i的所有3-cycles組合，但在n \geq 5的時候會矛盾

(5)B_{n}(F) \subset GL_{n}(F)，意指Borel subgroup是solvable的，B_{n}(F)例如像是\{\begin{pmatrix}* & \cdots & *\\0 & * & *\\0 & 0 & *\end{pmatrix} \in GL_{n}(F)\}：一組upper triangular matrices

證明：n = 3: B_{3} \supset U_{3} \supset \mathcal{Z}(U_{3}) = \{\begin{pmatrix}1 & 0 & x\\ & 1 & 0 \\ & & 1\end{pmatrix} | x \in F\} \supset \{1\}，其中U_{3} := \{\begin{pmatrix}1 & x & y\\ & 1 & z \\ & & 1\end{pmatrix}|x, y, z \in F\}，而\{\begin{pmatrix}1 & 0 & x\\ & 1 & 0 \\ & & 1\end{pmatrix} | x \in F\} \supset \{1\} \cong F

U_{3} \rightarrow F \times F, \begin{pmatrix}1 & x & y\\ & 1 & z \\ & & 1\end{pmatrix} \mapsto (x, z) with kernel \mathcal{Z}(U_{3})

B_{3} \rightarrow \{\begin{pmatrix}a_{1} & & \\ & a_{2} & \\ & & a_{3}\end{pmatrix}|a_{1}, a_{2}, a_{3} \in F^{x}\}, \begin{pmatrix}a_{1} & * & * \\0 & a_{2} & * \\ 0 & 0 & a_{3}\end{pmatrix} \mapsto \begin{pmatrix}a_{1} & & \\ & a_{2} & \\ & & a_{3}\end{pmatrix}，其中a_{1}, a_{2}, a_{3} \cong F^{x} \times F^{x} \times F^{x}與kernel

    \[U_{3} \Rightarrow B_{3}/U_{3} \cong F^{x} \times F^{x} \times F^{x}\]

    \[\Rightarrow B_{3} \>\> is \>\> solvable.\]

Scientia

我是Scientia，研究興趣包含Cryptology, Cryptographic Engineering, Security and Privacy, Computational Complexity, Quantum Cryptography, Cybersecurity, Hardware Security以及Anomaly Detection.

Related Posts

群
群

在數論當中群(Group)是其中一種重要的概念，代數最基本由三種結構組成：群 Group, 環 Ring, 體 Field，而群作為最基本的代數結構，也是我們在密碼系統中常常使用的，故需要先了解群的定義對於後續密碼系統分析會比較方便。

Continue reading
NP-Completeness
NP-Completeness

首先需要一個問題叫做布林公式(Boolean formula)會像：

    \[\phi = (\bar{x} \wedge y) \vee (x \wedge \bar{z})\]

裡面的每一個符號稱作variable，每一個variable可以給0或1的值就像在做.

Continue reading

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

You Missed

密碼理論

群之可解性

群之可解性
網路安全

威脅情報指標 Indicators of compromise (IoC)

威脅情報指標 Indicators of compromise (IoC)
防火牆

Palo Alto Firewall URL過濾 以及 Application Block Page

Palo Alto Firewall URL過濾 以及 Application Block Page
密碼理論

群

群
密碼理論

NP-Completeness

NP-Completeness
異常檢測

異常檢測的問題分類

異常檢測的問題分類