信息安全数学基础
  • 导读
  • 第一章 整数的可除性
    • 素数的判断
    • 广义欧几里得除法
    • 贝祖等式
    • gcd & lcm
    • 线性丢番图方程
  • 第二章 同余
    • 同余的性质
    • 剩余
    • 欧拉函数
    • 同余定理
    • 模重复平方计算法
    • RSA加密
  • 第三章 同余式
    • 一次同余式
    • 同余式组求解
    • 复杂取模运算简化
    • 高次同余式
    • 素数模的同余式简化
  • 第四章 二次同余式和平方剩余
    • 二次同余式化简
    • 二次剩余
    • Lengendre符号
    • 模p平方剩余判断
    • 雅可比符号
    • 模平方根
    • Rabin加密
    • 模平方和
  • 第五章 原根与指标
    • 指数
    • 原根
    • 指标
    • n次同余式
    • ElGamal加密
  • 第六章 素性检验
    • 伪素数和Fermat素性检验
    • Euler伪素数和Solovay-Stassen素性检验
    • 强伪素数和Miller-Rabin Primality素性检验
    • 梅森素数和Lucas-Lehmer Primality素性检验
    • 随机数生成
  • 第七章 群
    • 群和子群
    • 正规子群和商群
    • 同态和同构
    • 循环群
    • 置换群
  • 第八章 环与域
    • 环
    • 环与域
    • 多项式环
    • 有限域
  • 第九章 椭圆曲线
    • 基本概念
    • 椭圆曲线加法
    • ElGamal加密
由 GitBook 提供支持
在本页
  • 定义
  • 性质
  • 证明同构
  • 同态分解定理

这有帮助吗？

  1. 第七章 群

同态和同构

定义

  • 同态：f:G→G′,∀a,b∈G,f(ab)=f(a)f(b)f:G\rightarrow G^\prime,\forall a,b\in G,f\left(ab\right)=f\left(a\right)f\left(b\right)f:G→G′,∀a,b∈G,f(ab)=f(a)f(b)

  • 单同态：fff为单射

  • 满同态：fff为满射

  • 同构：fff为双射，记作f:G≅G′f:G\cong G^\primef:G≅G′

  • 自同态：G=G′G=G^\primeG=G′

  • 像：f:X→Y,A⊆X,B⊆Y,Af:X\rightarrow Y,A\subseteq X,B\subseteq Y,Af:X→Y,A⊆X,B⊆Y,A在YYY中的像f[A]f\left[A\right]f[A]为{f(a)∣a∈A}\left\{f\left(a\right)\mid a\in A\right\}{f(a)∣a∈A}

  • 逆像：BBB在XXX中的逆像f−1[B]f^{-1}{\left[B\right]}f−1[B]为{x∈X∣f(x)∈B}\left\{x\in X\mid f\left(x\right)\in B\right\}{x∈X∣f(x)∈B}

  • 核/核子群：ker(f)=f−1[{e′}]={x∈G∣f(x)=e′}\mathrm{ker}{\left(f\right)}=f^{-1}{\left[\left\{e^\prime\right\}\right]}=\left\{x\in G\mid f\left(x\right)=e^\prime\right\}ker(f)=f−1[{e′}]={x∈G∣f(x)=e′}

同态映射f:Z→(Zp,+)f:Z\rightarrow \left(Z_p,+\right)f:Z→(Zp​,+)，ker⁡(f)=<pZ>\ker\left(f\right)=<pZ>ker(f)=<pZ>

  • 像子群：g(G)g\left(G\right)g(G)

    核子群即由GGG中所有能通过fff映射成为G′G^\primeG′中的单位元的元素所组成的集合 像子群即GGG中所有元素通过fff映射后组成的集合

性质

  • fff为GGG到G′G^\primeG′的同态（同构），ggg为G′G^\primeG′到G′′G^{\prime\prime}G′′的同态（同构）⟹f∘g\Longrightarrow f\circ g⟹f∘g为GGG到G′′G^{\prime\prime}G′′的同态（同构）

  • fff为GGG到G′G^\primeG′的同态

    • f(e)=e′f\left(e\right)=e^\primef(e)=e′

    • ∀a∈G,f(a−1)=f−1(a)\forall a\in G,f\left(a^{-1}\right)=f^{-1}{\left(a\right)}∀a∈G,f(a−1)=f−1(a)

    • ker(f)≤G\mathrm{ker}{\left(f\right)}\leq Gker(f)≤G且fff为单同态⟺ker(f)={e}\Longleftrightarrow \mathrm{ker}{\left(f\right)}=\left\{e\right\}⟺ker(f)={e}

    • H′≤G′⟹f−1(H′)≤GH^\prime\leq G^\prime\Longrightarrow f^{-1}{\left(H^\prime\right)}\leq GH′≤G′⟹f−1(H′)≤G

证明f:G→G′f:G\rightarrow G^\primef:G→G′同构

  • STEP1: fff为同态映射

    证明f:G→G′,∀a,b∈G,f(ab)=f(a)f(b)f:G\rightarrow G^\prime,\forall a,b\in G,f\left(ab\right)=f\left(a\right)f\left(b\right)f:G→G′,∀a,b∈G,f(ab)=f(a)f(b)

  • STEP2: ker(f)={e}\mathrm{ker}{\left(f\right)}=\left\{e\right\}ker(f)={e}或fff为单射

    证明f(m)=f(n)⟹m=nf\left(m\right)=f\left(n\right)\Longrightarrow m=nf(m)=f(n)⟹m=n

  • STEP3: fff为满射

    证明m=f−1(n),f(m)=nm=f^{-1}{\left(n\right)},f\left(m\right)=nm=f−1(n),f(m)=n

同态分解定理

  • 自然同态

    f:G→G′f:G\rightarrow G^\primef:G→G′同态⟹ker(f)\Longrightarrow \mathrm{ker}{\left(f\right)}⟹ker(f)为GGG的正规子群

    NNN为GGG的正规子群S:G→G/H(a→aN)S:G\rightarrow G/H(a\rightarrow aN)S:G→G/H(a→aN)是核为NNN的同态，SSS为自然同态

  • 同态基本定理

    f:G→G′f:G\rightarrow G^\primef:G→G′同态⟹∃\Longrightarrow \exists⟹∃唯一G/ker(f)→f(G)G/\mathrm{ker}{\left(f\right)}\rightarrow f\left(G\right)G/ker(f)→f(G)同构fˉ:aker(f)→f(a)f=i∘fˉ∘s\bar{f}:a\mathrm{ker}{\left(f\right)}\rightarrow f\left(a\right)f=i\circ \bar{f}\circ sfˉ​:aker(f)→f(a)f=i∘fˉ​∘s，其中sss为G→G/ker(f)G\rightarrow G/\mathrm{ker}{\left(f\right)}G→G/ker(f)自然同态，i:c→ci:c\rightarrow ci:c→c为f(G)→G′f\left(G\right)\rightarrow G^\primef(G)→G′恒等同态

    s:G→G/Ns:G\rightarrow G/Ns:G→G/N同态⟹∀a∈G,f(a)=fˉ∘s(a)\Longrightarrow \forall a\in G,f\left(a\right)=\bar{f}\circ s\left(a\right)⟹∀a∈G,f(a)=fˉ​∘s(a)

上一页正规子群和商群下一页循环群

最后更新于4年前

这有帮助吗？