Trending News: 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《長銷》讀後心得：內容、定位、行銷、平台，從個人創作到企業經營都要懂的打造經典之道
週一. 5 月 6th, 2024
Trending News: 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《長銷》讀後心得：內容、定位、行銷、平台，從個人創作到企業經營都要懂的打造經典之道
週一. 5 月 6th, 2024

群

目錄

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

定義

一個群由一個集合和運算元組成G = (S, \odot)，集合S以及運算元\odot(這個意思表示任何運算元皆可，而我們在密碼系統內最常表達的是加法+與乘法*)，而一個群需要滿足下列四個條件：

  • (封閉性 Closure)：For\ every\ x, y \in S, x \odot y \in S ，對於任何元素x和y屬於S這個集合裡面，做任何的運算後該元素也應該要屬於這個集合內。
  • (關聯性 Associativity)：For\ every\ x,y,z \in S,(x \odot y) \odot z = x \odot (y \odot z)，對於任何元素x, y, z屬於這個集合S內，先運算x與y最後再與z運算，跟y與z做運算最後再跟x做運算的結果是一樣的。
  • (單位元素 Identity)：Exist\ e \in S\ such\ that\ for\ every\ x \in S, x \odot e = e \odot x = x，在集合S內存在一個單位元素e能夠讓集合內任何一個元素x與這個e做運算會得到x本身。
  • (反元素 Inverse)：For\ every\ x \in S, exist\ y \in S, x \odot y = e，對這個集合S的x元素存在一個y元素，而x元素與y元素進行運算能夠得到單位元素e。

滿足以上四點的話該集合S就能構成一個群，而在多一項條件的話可以變成阿貝爾群(Abelian)：

  • (交換性 Commutative)：For\ every x, y \in S, x \odot y = y \odot x，對於任意x, y元素在S集合內，x對y進行運算跟y跟x進行運算結果都一樣。

Additive Groups 加法群

滿足群的條件，如果整個群裡面運算元使用加法，代表這是一個加法群，其定義如下：

  • 運算元 \odot \to +
  • 單位元素 Identity：0
  • 反元素 inverse: \exists -x 對於x \in S
  • multiple：kx = x + x +….+ x

範例

(Z, +)：Z是整數集合\{-\infin…-2,-1,0,1,2,…,\infin\}，而+則代表在這個整數群內通通使用加法運算

(Z_n, +)：Z_n=\{0,1,…,n-1\}，Z_n是0到n-1的整數群並且使用加法運算在(mod\ n)的條件之下，(mod\ n)才能把條件限制在n-1之下

  • \lVert Z_n \rVert = n，Z_n這個整數群內的元素個數總共有n個，從0到n-1
  • -x \to n-x：x - x = 0\ (mod\ n) \to -x = n - x

(Z_p[x],+)：集合由多項式組成而係數在Z_q集合內

Multiplicative Groups 乘法群

滿足群的條件，如果整個群裡面運算元使用乘法，代表這是一個乘法群，其定義如下：

  • 運算元 \odot \to *
  • 單位元素 Identity：1
  • 反元素 Inverse：x^{-1}
  • multiple：x^{k} = x * x * ... * x

範例

(Q\text{\textbackslash}\{0\}, *)：Q是有理數集合排除掉0，並且這個群使用乘法運算元

(Z_n^{*}, *)：Z_n^{*}=\{x | x \in Z_n, x\perp n\}，Z_n^{*}代表這個整數群在(mod \> n)之下，並且整個群都是使用乘法運算元

  • \lVert Z_n^{*} \rVert = \varphi(n)
  • x^{-1}指的是x^{-1} (mod\> n)在x \in Z_n^{*}的條件下

Scientia

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

Related Posts

高斯消去法
高斯消去法

    \[\begin{cases}2x + 4y - 2z = 2 \\ 4x + 9y - 3z = 8 \\ -2x - 3y + 7z = 10\end{cases}\]

為了解決上述的聯立方程系統，使用高斯消去法減少不同variable的係數來求出我們需要的結果.

Continue reading
Vectors
Vectors

在整個線性代數中，最基本的單位就是一個向量，假設一個擁有兩個值的向量像是

    \[V = \begin{bmatrix}v_{1} \\ v_{2} \end{bmatrix}\]

向量加法假設另一組向量w一樣包含於兩個值$w = \begin{bmatr…

Continue reading

發佈留言

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

You Missed

資訊安全 防火牆

Palo Alto Firewall URL過濾 以及 Application Block Page

Palo Alto Firewall URL過濾 以及 Application Block Page
數學 數論

群

群
理論電腦科學 計算理論

NP-Completeness

NP-Completeness
異常檢測

異常檢測 問題分類

異常檢測 問題分類
異常檢測

異常檢測 方法評估

異常檢測 方法評估
異常檢測

異常檢測簡介 Anomaly Detection

異常檢測簡介 Anomaly Detection