精华内容
下载资源
问答
  • 素数阶群必为循环群

    万次阅读 2019-09-06 08:38:55
    素数阶群必为循环群,这个性质很重要,尤其是在密码学中,我们总是引入素数阶的群,这个性质保证了我们引入的群具有循环群的一切特征,包括交换性、具有生成元。 前要知识 群论中的拉格朗日定理(子群的必然能...

    前言:仅个人小记。素数阶群必为循环群,这个性质很重要,尤其是在密码学中,我们总是引入素数阶的群,这个性质保证了我们引入的群具有循环群的一切特征,包括交换性、具有生成元

    前要知识

    1. 群论中的拉格朗日定理(子群的阶必然能整除群阶) 。参看 https://blog.csdn.net/qq_25847123/article/details/100318620
    2. 素数 p 以内的正整数都与 p 互质。
    3. 素数阶群只有平凡子群 {e} 和 G ,不存在非平凡子群。证明如下:
      因为群 G 的阶为素数 p,且由前要知识2知,素数 p以内的正整数都与 p 互质,故而 G 的子群的阶不可能是
      { 2 , 3 , . . . , p − 1 } \{2,3,...,p-1\} {2,3,...,p1}故而 G 的子群的阶只有可能为
      { 1 , p } \{1,p\} {1,p}换言之,素数阶群 G 只可能有平凡子群 {e} 和 G不存在非平凡子群。证毕!

    证明

    群 G 中的任一元素 a 都可以构建一个循环子群 H,具体为 H = { e , a , a 2 , . . . , a k } H = \{e,a,a^2,...,a^k\} H={e,a,a2,...,ak}前要知识3知道,对于素数阶群,子群只有 {e} 和 G。
    显然当 a = e 时
    H = { e , a } = { e } H = \{e,a\}=\{e\} H={e,a}={e} a = e̸ a=\not e a=e,则必然
    H = G H=G H=G因为 H 已经是一个循环群了,所以必然 G 是一个循环群,进而素数阶群必然是一个循环群,得证。

    小结

    简言之, 由于群G是素数阶群,故而由任一元素生成的循环群要么是 {e} 要么是 G。当元素本身不为 e 时,该元素生成的循环群只能必然是 G,即必然有元素能生成群 G,故而群 G 必然是一个循环群。

    谢谢支持!
    邮箱: officeforcsdn@163.com
    展开全文
  • 对Sylow P-子群为循环群的10Pn非交换群的结构进行了分类,并讨论了这类群的非交换图,其中P>5, 且P为素数.
  • 输入安全参数λ\lambdaλ输出参数(p1,p2,p3,G,GT,e)(p_1, p_2, p_3, G, G_T, e)(p1​,p2​,p3​,G,GT​,e), 其中, p1,p2,p3p_1, p_2, p_3p1​,p2​,p3​表示3个不同的大素数, GGG和GTG_TGT​表示两个NNN阶循环群 ...

    合数阶群双线性映射

    Ψ \Psi Ψ是群的生成算法, 输入安全参数 λ \lambda λ输出参数 ( p 1 , p 2 , p 3 , G , G T , e ) (p_1, p_2, p_3, G, G_T, e) (p1,p2,p3,G,GT,e), 其中, p 1 , p 2 , p 3 p_1, p_2, p_3 p1,p2,p3表示3个不同的大素数, G G G G T G_T GT表示两个 N N N阶循环群 ( N = p 1 p 2 p 3 N = p_1p_2p_3 N=p1p2p3), e : G × G → G T e: G \times G → G_T e:G×GGT表示双线性映射当且仅当满足以下3个条件:
    (1) 双线性: ∀ u , v ∈ G \forall u, v \in G u,vG a , b ∈ Z N a,b \in Z_N a,bZN, 等式 e ( u a , v b ) = e ( u , v ) a b e(u^a, v^b) = e(u, v)^{ab} e(ua,vb)=e(u,v)ab成立.
    (2) 非退化性: ∃ g ∈ G , s t .   e ( g , g ) \exists g \in G, st.~e(g, g) gG,st. e(g,g) G T G_T GT中阶为 N N N.
    (3) 可计算性: 对于 ∀ u , v ∈ G \forall u, v \in G u,vG, ∃ \exists 计算e(u, v)的多项式时间算法.

    衍生结论: 假设群 G p 1 , G p 2 , G p 3 G_{p_1}, G_{p_2}, G_{p_3} Gp1,Gp2,Gp3分别是群 G G G中阶为 p 1 , p 2 , p 3 p_1, p_2, p_3 p1,p2,p3的子群. 取参数 h i ∈ G p i , h j ∈ G p j , i ≠ j h_i \in G_{p_i}, h_j \in G_{p_j}, i \neq j hiGpi,hjGpj,i=j, 则必有 e ( h i , h j ) = 1 e(h_i, h_j) = 1 e(hi,hj)=1.

    证明:
    基于一个基本观察, g p 1 p 2 g^{p_1p_2} gp1p2是群 G p 3 G_{p_3} Gp3的生成元. 这样考虑, 令 t = g p 1 p 2 t = g^{p_1p_2} t=gp1p2, 在群 G G G中, g p 1 p 2 p 3 g^{p_1p_2p_3} gp1p2p3是生成元, 所以 t p 3 t^{p_3} tp3 G p 3 G_{p_3} Gp3的生成元. 同理 g p 1 p 3 g^{p_1p_3} gp1p3是群 G p 2 G_{p_2} Gp2的生成元, g p 2 p 3 g^{p_2p_3} gp2p3是群 G p 1 G_{p_1} Gp1的生成元.
    所以可以用生成元表示, h i = g i α i , h j = g j α j h_i = g_i^{\alpha_i}, h_j = g_j^{\alpha_j} hi=giαi,hj=gjαj, 其中 g k = g p m p n , k , m , n ∈ { 1 , 2 , 3 } , m ≠ n , m ≠ k , n ≠ k g_k = g^{p_mp_n}, k,m,n \in \{1,2,3\}, m \neq n, m \neq k, n \neq k gk=gpmpn,k,m,n{1,2,3},m=n,m=k,n=k.
    e ( h i , h j ) = e ( g i α i , g j α j ) = e ( g α i , g p l α j ) p 1 p 2 p 3 = 1 , l ∈ { 1 , 2 , 3 } e(h_i, h_j) = e(g_i^{\alpha_i}, g_j^{\alpha_j}) = e(g^{\alpha_i}, g^{p_l \alpha_j})^{p_1p_2p_3} = 1, l \in \{1,2,3\} e(hi,hj)=e(giαi,gjαj)=e(gαi,gplαj)p1p2p3=1,l{1,2,3}


    素数阶群双线性映射

    Ψ \Psi Ψ是群的生成算法, 输入安全参数 λ \lambda λ输出参数 ( p , G 1 , G 2 , G T , e , g , g ~ ) (p, G_1, G_2, G_T, e, g, \tilde{g}) (p,G1,G2,GT,e,g,g~), 其中, p p p表示大素数, G 1 , G 2 G1, G_2 G1,G2 G T G_T GT表示3个 p p p阶循环群, g , g ~ g, \tilde{g} g,g~分别表示 G 1 , G 2 G1, G_2 G1,G2的生成元, e : G 1 × G 2 → G T e: G_1 \times G_2 → G_T e:G1×G2GT表示双线性映射当且仅当满足以下3个条件:
    (1) 双线性: ∀ u ∈ G 1 , v ∈ G 2 \forall u \in G_1, v \in G_2 uG1,vG2 a , b ∈ Z p a,b \in Z_p a,bZp, 等式 e ( u a , v b ) = e ( u , v ) a b e(u^a, v^b) = e(u, v)^{ab} e(ua,vb)=e(u,v)ab成立.
    (2) 非退化性: ∃ g ∈ G 1 , g ~ ∈ G 2 , s t .   e ( g , g ~ ) \exists g \in G_1, \tilde{g} \in G_2, st.~e(g, \tilde{g}) gG1,g~G2,st. e(g,g~) G T G_T GT中阶为 p p p.
    (3) 可计算性: 对于 ∀ u ∈ G 1 , v ∈ G 2 \forall u \in G_1, v \in G_2 uG1,vG2, ∃ \exists 计算e(u, v)的多项式时间算法.

    补充:
    G 1 ≠ G 2 G_1 \neq G_2 G1=G2, 称该映射为非对称双线性映射,
    G 1 = G 2 G_1 = G_2 G1=G2, 则是对称双线性映射.

    展开全文
  • 求n阶循环群上平方根的方法 前面讨论勒让德符号计算问题时,就说明了二次同余式是否有解的问题的重要性。今天来讨论,对于二次同余方程:x2≡a(modp)x^{2} \equiv a\pmod{p}x2≡a(modp)有解,即Legendre符号(ap)=1(\...

    求n阶循环群上平方根的方法

    前面讨论勒让德符号计算问题时,就说明了"二次同余式是否有解"的问题的重要性。今天来讨论,当二次同余方程: x 2 ≡ a ( m o d p ) x^{2} \equiv a\pmod{p} x2a(modp)有解时,即Legendre符号 ( a p ) = 1 (\frac{a}{p})=1 (pa)=1,那么如何求 x x x的值呢?这就是今天要讨论的 n n n阶循环群的平方根求法(由于p是奇素数,模p的乘法群的阶是 p − 1 p-1 p1,所以这里的 n n n就是 p − 1 p-1 p1)。

    其实我本来也觉得这个证明过程和计算过程偏复杂,不想深入理解记住,但是闭卷考试要考,逼得我不得不掌握。

    1、问题描述

    如果方程
    x 2 ≡ a ( m o d p ) x^{2}\equiv a\pmod{p} x2a(modp)
    有根, p p p是奇素数,求 x x x

    2、简单的分析

    我们知道:

    1. 若存在奇数 q q q,满足 a q ≡ 1 ( m o d p ) a^{q}\equiv 1 \pmod{p} aq1(modp),那么必定有 ( ± a q + 1 2 ) 2 ≡ a q + 1 ≡ a ( m o d p ) (\pm a^{\frac{q+1}{2}})^{2}\equiv a^{q+1}\equiv a\pmod{p} (±a2q+1)2aq+1a(modp),所以有 x = ± a q + 1 2 x=\pm a^{\frac{q+1}{2}} x=±a2q+1。但是若满足这个式子的 q q q是偶数,则 q + 1 2 \frac{q+1}{2} 2q+1是小数,这式子就是不对的。那么这种情况就需要用第二条。
    2. 若存在 B ∈ Z p ∗ B\in \mathbb{Z}_{p}^{*} BZp,有 B 2 l a q ≡ 1 ( m o d p ) B^{2l}a^{q}\equiv 1\pmod{p} B2laq1(modp)成立(其中 l l l是大于等于0的任意某个整数, q q q是奇数),则必有 ( ± B l a q + 1 2 ) 2 ≡ a ( m o d p ) (\pm B^{l}a^{\frac{q+1}{2}})^{2} \equiv a \pmod{p} (±Bla2q+1)2a(modp)成立,那 x = ± B l a q + 1 2 x=\pm B^{l}a^{\frac{q+1}{2}} x=±Bla2q+1

    现在的问题归结成:如何找满足2的这个 B , l , q B,l,q B,l,q

    3、过程

    p p p是奇素数,根据欧拉定理,有 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv 1\pmod{p} ap11(modp),我们对 p − 1 p-1 p1做分解,企图构造出满足要求的 B , l , q B,l,q B,l,q

    具体的,将 p − 1 p-1 p1分解成 p − 1 = 2 s t p-1=2^{s}t p1=2st,找这里最大的 s s s,使得 t t t为奇数。如 100 = 2 2 × 25 100=2^{2}\times 25 100=22×25。显然, s ≥ 1 s\geq 1 s1

    ​ 任取 b ∈ Z p ∗ b\in \mathbb{Z}_{p}^{*} bZp s . t . s.t. s.t. b b b是模p的一个二次非剩余,那么自然有 b p − 1 2 ≡ − 1 ( m o d p ) b^{\frac{p-1}{2}}\equiv -1\pmod{p} b2p11(modp)。令 B ≡ b t ( m o d p ) B\equiv b^{t} \pmod{p} Bbt(modp),则有 B 2 s − 1 ≡ b 2 s − 1 t ≡ − 1 ( m o d p ) B^{2^{s-1}}\equiv b^{2^{s-1}t}\equiv -1\pmod{p} B2s1b2s1t1(modp)。注意到 a a a是模p的二次剩余(因为题目说了方程有解),所以 a p − 1 2 ≡ 1 ( m o d p ) a^{\frac{p-1}{2}}\equiv 1\pmod{p} a2p11(modp),所以令 A = a t A=a^{t} A=at,则 A 2 s − 1 ≡ 1 ( m o d p ) A^{2^{s-1}}\equiv 1 \pmod{p} A2s11(modp)

    ​ 若 s = 1 s=1 s=1,则已经有了 A ≡ a t ≡ 1 ( m o d p ) A\equiv a^{t} \equiv 1\pmod{p} Aat1(modp)成立,且 t t t是奇数,利用第1 条可以得出根

    ​ 若 s > 1 s>1 s>1,那么 A 2 s − 1 ≡ ( A 2 s − 2 ) 2 ≡ 1 ( m o d p ) A^{2^{s-1}}\equiv (A^{2^{s-2}})^{2}\equiv 1\pmod{p} A2s1(A2s2)21(modp),则有 A 2 s − 2 ≡ ± 1 ( m o d p ) A^{2^{s-2}}\equiv \pm 1\pmod{p} A2s2±1(modp)。因为 B 2 s − 1 ≡ − 1 ( m o d p ) B^{2^{s-1}}\equiv -1\pmod{p} B2s11(modp),所以,如果令
    l 1 = { 0 若 A 2 s − 2 ≡ 1 ( m o d p ) 1 若 A 2 s − 2 ≡ − 1 ( m o d p ) l_{1}=\begin{cases} 0 & 若A^{2^{s-2}}\equiv 1 \pmod{p} \\ 1 & 若A^{2^{s-2}}\equiv -1 \pmod{p} \end{cases} l1={01A2s21(modp)A2s21(modp)
    这样必有 ( B 2 s − 1 ) l 1 A 2 s − 2 ≡ 1 ( m o d p ) (B^{2^{s-1}})^{l_{1}}A^{2^{s-2}}\equiv 1\pmod{p} (B2s1)l1A2s21(modp)

    ​ 若此时 s = 2 s=2 s=2,则上式变成 B 2 l 1 A ≡ B 2 l 1 a t ≡ 1 ( m o d p ) B^{2l_{1}}A\equiv B^{2l_{1}}a^{t}\equiv 1\pmod{p} B2l1AB2l1at1(modp)成立,利用第2 条可以得出根

    ​ 若此时 s > 2 s>2 s>2,那么 ( ( B 2 s − 2 ) l 1 A 2 s − 3 ) 2 ≡ 1 ( m o d p ) ((B^{2^{s-2}})^{l_{1}}A^{2^{s-3}})^{2}\equiv 1\pmod{p} ((B2s2)l1A2s3)21(modp),则有 ( B 2 s − 2 ) l 1 A 2 s − 3 ≡ ± 1 ( m o d p ) (B^{2^{s-2}})^{l_{1}}A^{2^{s-3}}\equiv \pm 1\pmod{p} (B2s2)l1A2s3±1(modp)。继续利用 B 2 s − 1 ≡ − 1 ( m o d p ) B^{2^{s-1}}\equiv -1\pmod{p} B2s11(modp),所以,如果令
    l 2 = { 0 若 ( B 2 s − 2 ) l 1 A 2 s − 3 ≡ 1 ( m o d p ) 1 若 ( B 2 s − 2 ) l 1 A 2 s − 3 ≡ − 1 ( m o d p ) l_{2}=\begin{cases} 0 & 若(B^{2^{s-2}})^{l_{1}}A^{2^{s-3}}\equiv 1 \pmod{p} \\ 1 & 若(B^{2^{s-2}})^{l_{1}}A^{2^{s-3}}\equiv -1 \pmod{p} \end{cases} l2={01(B2s2)l1A2s31(modp)(B2s2)l1A2s31(modp)
    这样必有 ( B 2 s − 1 ) l 2 ( B 2 s − 2 ) l 1 A 2 s − 3 ≡ 1 ( m o d p ) (B^{2^{s-1}})^{l_{2}}(B^{2^{s-2}})^{l_{1}}A^{2^{s-3}}\equiv 1\pmod{p} (B2s1)l2(B2s2)l1A2s31(modp)

    ​ 若此时 s = 3 s=3 s=3,则上式变成 B 4 l 2 + 2 l 1 A ≡ B 4 l 2 + 2 l 1 a t ≡ 1 ( m o d p ) B^{4l_{2}+2l_{1}}A\equiv B^{4l_{2}+2l_{1}}a^{t}\equiv 1\pmod{p} B4l2+2l1AB4l2+2l1at1(modp)成立,利用第2 条可以得出根

    ​ 若此时 s > 3 s>3 s>3,那么 ( ( B 2 s − 2 ) l 2 ( B 2 s − 3 ) l 1 A 2 s − 4 ) 2 ≡ 1 ( m o d p ) ((B^{2^{s-2}})^{l_{2}}(B^{2^{s-3}})^{l_{1}}A^{2^{s-4}})^{2}\equiv 1\pmod{p} ((B2s2)l2(B2s3)l1A2s4)21(modp),则有 ( B 2 s − 2 ) l 2 ( B 2 s − 3 ) l 1 A 2 s − 4 ≡ ± 1 ( m o d p ) (B^{2^{s-2}})^{l_{2}}(B^{2^{s-3}})^{l_{1}}A^{2^{s-4}}\equiv \pm 1\pmod{p} (B2s2)l2(B2s3)l1A2s4±1(modp)。继续利用 B 2 s − 1 ≡ − 1 ( m o d p ) B^{2^{s-1}}\equiv -1\pmod{p} B2s11(modp),所以,如果令
    l 3 = { 0 若 ( B 2 s − 2 ) l 2 ( B 2 s − 3 ) l 1 A 2 s − 4 ≡ 1 ( m o d p ) 1 若 ( B 2 s − 2 ) l 2 ( B 2 s − 3 ) l 1 A 2 s − 4 ≡ − 1 ( m o d p ) l_{3}=\begin{cases} 0 & 若(B^{2^{s-2}})^{l_{2}}(B^{2^{s-3}})^{l_{1}}A^{2^{s-4}}\equiv 1 \pmod{p} \\ 1 & 若(B^{2^{s-2}})^{l_{2}}(B^{2^{s-3}})^{l_{1}}A^{2^{s-4}}\equiv -1 \pmod{p} \end{cases} l3={01(B2s2)l2(B2s3)l1A2s41(modp)(B2s2)l2(B2s3)l1A2s41(modp)
    这样必有 ( B 2 s − 1 ) l 3 ( B 2 s − 2 ) l 2 ( B 2 s − 3 ) l 1 A 2 s − 4 ≡ 1 ( m o d p ) (B^{2^{s-1}})^{l_{3}}(B^{2^{s-2}})^{l_{2}}(B^{2^{s-3}})^{l_{1}}A^{2^{s-4}}\equiv 1\pmod{p} (B2s1)l3(B2s2)l2(B2s3)l1A2s41(modp)

    ​ 若此时 s = 4 s=4 s=4,则上式变成 B 8 l 3 + 4 l 2 + 2 l 1 A ≡ B 8 l 3 + 4 l 2 + 2 l 1 a t ≡ 1 ( m o d p ) B^{8l_{3}+4l_{2}+2l_{1}}A\equiv B^{8l_{3}+4l_{2}+2l_{1}}a^{t}\equiv 1\pmod{p} B8l3+4l2+2l1AB8l3+4l2+2l1at1(modp)成立,利用第2 条可以得出根

    ​ 若 s > 4 s>4 s>4,那么继续利用上述算法一直计算下去 ⋯ \cdots

    这样就可以求得二次同余式的根。

    总结来说就是一直看 s s s的取值,最终使得 A A A的指数变成1,这样就有了 B 2 l a t ≡ 1 ( m o d p ) B^{2l}a^{t}\equiv 1 \pmod{p} B2lat1(modp)(t为奇数)出现了。

    4、例子

    大家不妨找一个简单的例子试一下。如
    x 2 ≡ 52 ( m o d 101 ) x^{2}\equiv 52\pmod{101} x252(mod101)
    :(1)先判断这个方程是不是有解,即求Legendre符号 ( 25 101 ) (\frac{25}{101}) (10125).
    ( 52 101 ) = ( 4 101 ) ( 13 101 ) = ( − 1 ) 13 − 1 2 101 − 1 2 ( 101 13 ) = ( 10 13 ) = ( 5 13 ) ( 2 13 ) = ( − 1 ) 1 3 2 − 1 8 ( − 1 ) 5 − 1 2 13 − 1 2 ( 13 5 ) = ( − 1 ) ( 3 5 ) = ( − 1 ) ( 2 3 ) = ( − 1 ) ( − 1 ) 3 2 − 1 8 = 1 (\frac{52}{101}) =(\frac{4}{101})(\frac{13}{101})=(-1)^{\frac{13-1}{2} \frac{101-1}{2}}(\frac{101}{13})=(\frac{10}{13})=(\frac{5}{13})(\frac{2}{13})\\=(-1)^{\frac{13^{2}-1}{8}}(-1)^{\frac{5-1}{2} \frac{13-1}{2}}(\frac{13}{5})=(-1)(\frac{3}{5})=(-1)(\frac{2}{3})=(-1)(-1)^{\frac{3^{2}-1}{8}}=1 (10152)=(1014)(10113)=(1)213121011(13101)=(1310)=(135)(132)=(1)81321(1)2512131(513)=(1)(53)=(1)(32)=(1)(1)8321=1
    所以方程有解。

    (2)根据题目, a = 52 , p = 101 , p − 1 = 100 = 2 2 × 25 a=52,p=101,p-1=100=2^{2}\times 25 a=52,p=101,p1=100=22×25,所以, s = 2 , t = 25 s=2,t=25 s=2,t=25

    ​ 找一个模101的非二次剩余:(一般看看 ( 2 p ) (\frac{2}{p}) (p2)或者 ( 3 p ) (\frac{3}{p}) (p3)等等)
    ( 3 101 ) = ( − 1 ) 3 − 1 2 101 − 1 2 ( 101 3 ) = ( 2 3 ) = − 1 (\frac{3}{101})=(-1)^{\frac{3-1}{2} \frac{101-1}{2}}(\frac{101}{3})=(\frac{2}{3})=-1 (1013)=(1)23121011(3101)=(32)=1
    所以, b = 3 , B = b t = 3 25 ( m o d 101 ) , A = a t = 5 2 25 ( m o d 101 ) b=3,B=b^{t}=3^{25}\pmod{101},A=a^{t}=52^{25}\pmod{101} b=3,B=bt=325(mod101),A=at=5225(mod101)。(注意这里会出现大数的模幂运算,如非必要可以不计算,等后面需要计算时利用重复平方-乘方法进行计算,有时为了验证推导是不是正确也可以计算结果加以验证)

    因为 s = 2 s=2 s=2,所以需要计算 l 1 l_{1} l1,由于 A 2 s − 2 ≡ A ≡ 1 ( m o d p ) A^{2^{s-2}}\equiv A\equiv 1\pmod{p} A2s2A1(modp),所以 l 1 = 0 l_{1}=0 l1=0

    ​ 如此就找到了 A 2 s − 1 ≡ 1 ( m o d p ) A^{2^{s-1}}\equiv 1\pmod{p} A2s11(modp),根据条件2,即 x ≡ ( ± 5 2 25 + 1 2 ) ≡ ± 31 ( m o d 101 ) x\equiv (\pm 52^{\frac{25+1}{2}})\equiv \pm 31 \pmod{101} x(±52225+1)±31(mod101)

    展开全文
  • 如何证明一个群是循环群

    万次阅读 2018-11-15 19:40:44
    如何证明一个群是循环群content分析:证明一个群是循环群的思路证明推论:素数的群是循环群 content 如何证明一个群是循环群? 有限群一定是循环群吗?不一定。 推论:素数的群是循环群。 分析:证明一...

    content

    如何证明一个群是循环群?
    有限群一定是循环群吗?不一定。
    推论:阶是素数的群是循环群。

    分析:证明一个群是循环群的思路

    证明一个群是循环群的思路有三种:
    1.利用循环群的定义证明群中每一个元都能表示为群中同一个元的方幂;
    2.利用同构的思想,先构造一个恰当的循环群,再证明它和该群同构;
    3.先在群中生成一个循环子群,若能证明子群就是该群即可;
    在上面的几种思路中,(3)是最佳选择。

    证明推论:阶是素数的群是循环群

    在这里插入图片描述

    展开全文
  • 循环群:设群GGG中任意元素都可以表示成某一固定元素aaa的幂次,G={an∣n∈Z},G=\{a^n|n\in Z\},G={an∣n∈Z},那么称GGG为循环群,aaa群GGG的生成元,写成G=<a>G=<a>G=<a>。 有一个例子,...
  • 循环群的生成元及子群(不一定对-_-#)

    万次阅读 多人点赞 2018-10-14 22:54:23
    是15阶循环群。 求出 G 的所有生成元 求出 G 的所有子群   该题的解题过程如下: 小于等于15,且与15 互为素数的数是1、2、4、7、8、11、13、14 ,故生成元,,,,,,, 15 的正因子有1,3,5,15,故有四...
  • 假设G是有限。子H称为G的H-子,如果对任何g∈G有NG( H)∩Hg≤H。用H ( G)表示G中 所有 H-子的集合。本文讨论某些素数阶和4阶循环是 H-子的结构。
  • 叛徒追踪和撤销是属性基加密(ABE)需要解决的问题。...最后利用完全子树构架,将PGWABE方案转变为素数阶群上可追踪并撤销叛徒的ABE方案(PABTR)。性能分析表明,与ABTR方案相比,PABTR方案在同等安全性上效率更高。
  • 一直知道 ,对于素数 p,Zp∗={1,2,...,p−1}Z_p^*=\{1,2,...,p-1\}Zp∗​={1,2,...,p−1}是一个循环群,并且一直在使用这个性质(比如欧拉定理,费马定理,生成元的使用),但却不知道 Zp∗Z_p^*Zp∗​什么是一个...
  • 是以1生成元的循环群因为2=1+14=123=1+14+14=130=2+24=14<N4,+4>={14,1,12,13}\color{blue} <N_4,+_4>是以1生成元的循环群\\ 因为2=1+1_4=1^2\\3=1+1_4+1_4=1^3\\0=2+2_4=1^4\\ <N_4,+_4>=\...
  • 设p素数,且p>5,对Sylowp-子群循环的12pn阶群进行了完全分类并获得了其全部构造:1)当p≡1(mod12)时,G恰有16个彼此不同构的类型;2)当p≡5(mod12)时,G恰有10个彼此不同构的类型;3)当p≡7(mod12)时,G恰有14个彼此不...
  • 以模6加法群(Z6,+)认识循环群及其特点

    万次阅读 多人点赞 2018-09-23 17:57:18
    刚开始接触循环群不容易理解,不妨以模6加法群&lt;Z6,+&gt;入手,来认识循环群的特点。 首先,循环群,顾名思义,cycle group即带有循环的意思。怎么个循环法呢? 我们看&lt;Z6,+&gt;中的元素{0...
  • 一.子与配集分解 1.子 (1)概念: (2)判定: 2.配集与配集分解 (1)将分拆成等价类: ...引理1:设GGG是,A≤GA≤GA≤G;定义在GGG上的关系:对应g,h∈G,g...定理1(拉格朗日定理(Lagrange Theorem)):设GGG有限,A≤
  • 循环群生成元

    千次阅读 2015-03-19 14:55:50
    循环群生成元 对于mod n域中的任意数a,若有gcd(m,n)=1,则m该域的生成元,使得a+km可以域中任意数. 证明十分简单,若gcd(m,n)=1,则lcm(m,n)=m*n,则对于a的mod n运算,需要n次的计算才能回到a,...
  • 题目:编写一个函数求循环群的一个生成元,使用java代码实现 函数输入:一个大素数p,类型BigInteger 函数返回值:输出素域p除开零元的一个生成元g,类型BigInteger 不要暴力,能不能有巧妙一些的...
  • ,a∈G,a的整数次幂可归纳定义: a0 = e an+1 = an· a, n∈N a-n = (a-1)n, n∈N 容易证明,∀m,n∈I,am··an = am+n, (am)n = amn. 定义:设<G,·>是,a∈G,若∀n∈I+,an≠ e,则称a的是...
  • 数学--数论--原根(循环群生成元)

    千次阅读 2020-02-06 22:53:57
    突然今天,我想不起什么是原根来了,查了一下定义,哎~这货不是离散数学,循环群生成元吗??不是<a+>而是<a∗>是乘法而不是加法<a_+>而是<a_*>是乘法而不是加法<a+​>而是<a∗​&...
  • 给出了所有中心循环且中心商的小于 p5的有限 p-的自同构,p为素数
  • 因为197的三个数位循环移位后的数字:197、971、719均为素数。 100以内这样的数字包括13个,2、3,、5、7、11、13、17、31、37、71、73、79、97。 求任意正整数n以内一共有多少个这样的循环素数。 import math def ...
  • 利用有限群的性质,运用群扩张和数论的理论,给出了当p,q是不同的素数且p,2 3p2q群G在具有p2q循环正规子群A时的构造如下:①当B为循环群时,有22型;②当B[4,2]型交换群时,有19型;③当B初等交换群时,...
  • 设G是具有循环极大子的pn阶群,p为素数。对G的7个互不同构的类型,给出了G的各元之个数,进一步证明了除3个类型外,其余4个类型均可由其各元之个数进行刻画。
  • GAP命令: gap> for i in [1..100] do Print("U(",i,")=",IdGroup(Units(ZmodnZ(i))),"\n"); od; U(1)=[ 1, 1 ] U(2)=[ 1, 1 ] U(3)=[ 2, 1 ] U(4)=[ 2, 1 ] U(5)=[ 4, 1 ] U(6)=[ 2, 1 ] U(7)=[ 6, 2 ] U(8)=...
  • ㈠ 数学函数符号怎么打1、点输入法上的键盘标志,会出来软键盘和特殊符号,点特殊符号就有。2、实在不行再word里打出来复制粘贴㈡ 什么叫符号函数 符号函数有多少符号函数是数学上的Sgn 函数返回...Sgn函数一般指...
  • 但是在这里要注意每次内循环开始前必须要将 get 变量重新置零,因为每次循环完都要重新记录,最后在内循环后加一个判断就可以了,如果 get 还 0 肯定那个数是质数,就直接输出就可以了。 小C:不错,这个开胃菜够...
  • 证明单映射→\to→证明π−1(π(X))=X,X\pi^{-1}(\pi(X))=X,Xπ−1(π(X))=X,X一个集合 所谓轨道就是一个等价类,这个等价类里面的元素就是能产生关联的所有元素。比如1在作用下变成了2,原来集合里面的2变成了5...
  • C语言算法小技巧:找质数素数)1.基本算法 质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除。也就是只有2个因数,1和它本身。 1.基本算法 根据质数的概念,一个数num,除以2到num-1所有...
  • 则对任意的一个正整数 n,存在一个特征 p,元素个数 pn 的有限域 GF(pn).web注:任意一个有限域,其元素的个数必定 pn,其中 p 一个素数(有限域的特征),n 一个正整数.数组例1(有限域 GF(p)) 令 p 一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,454
精华内容 1,381
关键字:

循环群的阶为素数