← COMP5521 全部讲次
L07a-2 · 第 8 周

L07a-2 循环群:一个元素自乘就能走遍全群

拿 Z₁₁* 里的一个数反复自乘:4 走五步就回到 1,7 走满十步才回来。由此讲元素的阶、循环群与生成元、指数 mod q 的化简,以及加法写法下的循环群。

一句话版

拿群里的一个元素不停自乘,它迟早会回到 1。如果回到 1 之前把群里每个元素都走了一遍,这个元素就叫生成元,这个群就叫循环群。

群是什么、Z₁₁* 的乘法表怎么查,见上一页 L07a。这一页只看一个元素自己反复相乘。

先认识这几个词

词 全称 / 读法 一句人话
gⁱ 读「g 的 i 次方」 g 自乘 i 次,每次乘完 mod 11
元素的阶 order of an element 自乘几次第一次回到 1
群的阶 q order of a group 群里一共有几个元素,Z₁₁* 是 10
生成元 g generator,也叫原根 primitive root 自乘能走遍群里每个元素的那个元素
⟨g⟩ 读「g 生成的群」 g 的所有次幂组成的集合
循环群 cyclic group 能被某一个元素生成的群

一个类比:只有一个按钮的转盘

想象一个刻着 1 到 10 的转盘,只有一个按钮。每按一次,指针按固定规则跳到下一格。

规则选「乘 7 再 mod 11」,从 7 出发。指针依次停在 7、5、2、3、10、4、6、9、8、1,十格全走到了才回到 1。7 就是这个转盘的生成元。

换一个按钮,规则改成「乘 4 再 mod 11」。指针依次停在 4、5、9、3、1,然后又是 4、5、9、3、1。它只在五格之间打转,另外五格永远到不了。

按钮按多少次都没关系,只看按了几圈零几下。7 的转盘走 10 步回到起点,所以按 115 次和按 5 次停在同一格。

类比在哪里失效:

  • 转盘只演示一个元素反复自乘,看不出两个不同元素相乘落在哪,那要查乘法表。
  • 在加法群里「按按钮」是加,不是乘,这一页最后一个概念会换成加法再看一遍。

从零讲起

1. 元素的幂和阶

它解决什么问题

上一页看的是两个不同的数相乘。密码学里更常见的是一个数自己反复相乘,比如 gˣ mod p。要知道这样乘下去会落在哪里、多久重复一次,就得先看清一个元素的幂长什么样。

直觉

在 Z₁₁* 里,一个数自乘的结果永远在 1 到 10 之间,只有十种可能。乘的次数一多,迟早会碰到之前出现过的数,从那以后就开始重复。

实际上它重复的起点总是 1:先回到 1,再从头来一遍。第一次回到 1 用了几步,就是这个元素的阶。

一步一步看

目标:用 4 在模 11 下逐步相乘,看出走 5 步回到 1,之后结果开始循环。

拿 4 来走。每一步用上一步的结果乘 4,再 mod 11。

  1. 4¹ = 4。

    1 到 10 排成一圈,4 用青绿圈出表示第 1 步落在 4,其余数是浅灰;右边写 4 的 1 次方等于 4

  2. 4² = 4 × 4 = 16 ≡ 5。

    同一圈数,4 变成近黑圈,一条箭头从 4 指到青绿的 5;右边写 4 的平方等于 4 乘 4 等于 16 同余 5

  3. 4³ = 5 × 4 = 20 ≡ 9。

    箭头从 4 到 5 再到青绿的 9;右边多一行 4 的 3 次方等于 5 乘 4 等于 20 同余 9

  4. 4⁴ = 9 × 4 = 36 ≡ 3。

    箭头依次连 4、5、9,最后指向青绿的 3;右边多一行 4 的 4 次方等于 9 乘 4 等于 36 同余 3

  5. 4⁵ = 3 × 4 = 12 ≡ 1。回到 1 了,一共用了 5 步。

    箭头依次连 4、5、9、3,最后指向青绿的 1;2、6、7、8、10 一直是浅灰,没被走到。底部注明第 5 步回到 1,之后只会重复 4、5、9、3、1 这一圈

  6. 再往下乘,4⁶ = 1 × 4 = 4,又从 4 开始,重复 4、5、9、3、1。

怎么算

元素 a 的阶 = 使 aᵏ ≡ 1 的最小正整数 k

意思是:从 a 开始一格一格往下乘,数到第一次出现 1 时停下,数了几步,阶就是几。

手算时别每次重新算整个幂,每次只拿上一格的结果乘 a 再 mod 11,数字不会变大。

常见误解

以为 4ⁱ 要算出 4 的 i 次方再取余

可以这样算,但数很快变大。每一步都先取余再往下乘,结果完全一样:4³ = 64 ≡ 9,用上一格算是 5 × 4 = 20 ≡ 9。

把元素的阶和群的阶混成一个东西

群的阶是群里有几个元素,Z₁₁* 是 10。元素的阶是这个元素自乘几步回到 1,4 是 5,7 是 10。两个都叫「阶」,看后面跟的是群还是元素。

试一下

在 Z₁₁* 里求 10 的阶,再求 5 的阶。

10¹ = 10,10² = 100 ≡ 1,所以 10 的阶是 2。

5¹ = 5,5² = 25 ≡ 3,5³ = 3 × 5 = 15 ≡ 4,5⁴ = 4 × 5 = 20 ≡ 9,5⁵ = 9 × 5 = 45 ≡ 1,所以 5 的阶是 5。

2. 循环群与生成元

它解决什么问题

一个群如果有十个元素,要描述它好像得把十个都列出来。循环群给出一个省事的说法:找到一个元素 g,它的幂恰好是整个群,那么整个群就是「g 的各次幂」,一句话说完。

第 4 讲的 ElGamal 和 DSA 一开头都要选这样一个 g,因为它保证 gˣ 能取到群里每一个值。

从哪来(补充)

生成元在数论里叫原根(primitive root)。高斯在 1801 年的《算术研究》第 57 条里定义了原根,并说明这个名字来自欧拉。

出处:Wikipedia: Primitive root modulo n

直觉

一个元素的阶有多大,它就能走到多少个不同的数。4 的阶是 5,只走到五个数。阶等于群的大小 10 的元素,走满十步才回来,路上必然把十个数全走了一遍,它就是生成元。

一步一步看

目标:用 7 在模 11 下乘满一圈,看出 10 个结果正好把 1 到 10 各走一次,所以 7 是生成元。

拿 7 来走,每一步乘 7 再 mod 11。

  1. 7¹ = 7。

  2. 7² = 7 × 7 = 49 ≡ 5。

  3. 7³ = 5 × 7 = 35 ≡ 2。

  4. 7⁴ = 2 × 7 = 14 ≡ 3,7⁵ = 3 × 7 = 21 ≡ 10。

  5. 7⁶ = 10 × 7 = 70 ≡ 4,7⁷ = 4 × 7 = 28 ≡ 6。

  6. 7⁸ = 6 × 7 = 42 ≡ 9,7⁹ = 9 × 7 = 63 ≡ 8。

  7. 7¹⁰ = 8 × 7 = 56 ≡ 1。回到 1,用了 10 步。

    1 到 10 排成一圈,箭头按 7、5、2、3、10、4、6、9、8、1 的顺序把十个数全部连起来,最后一步落在青绿的 1;右边逐行写出 7 的 1 次方到 10 次方的算法,底部写十个数各到一次,所以 7 是生成元

  8. 十个结果 7、5、2、3、10、4、6、9、8、1 正好是 1 到 10 各一次,所以 7 是 Z₁₁* 的生成元,记作 Z₁₁* = ⟨7⟩。

怎么判断

G = ⟨g⟩ 当且仅当 g 的阶等于 G 的元素个数

意思是:把 g 的幂一格一格列出来,直到回到 1。列出来的数个数等于群的大小,g 就是生成元,G 就是循环群;少于群的大小,g 只生成了一部分。

判断时要列满、数清,不能看前几格没重复就下结论。

常见误解

以为群里每个元素都是生成元

Z₁₁* 里只有 2、6、7、8 四个是生成元。4 走五步就回到 1,10 走两步就回到 1,1 原地不动。一个群是循环群,只要求至少有一个生成元。

以为 3 生成一个子群,就说 3 是 Z₁₁* 的生成元

3 的幂是 3、9、5、4、1,只走到五个数。它生成的是子群 {1, 3, 4, 5, 9},对这个子群它是生成元,对整个 Z₁₁* 它不是。说「生成元」时要讲清是谁的生成元。

试一下

列出 6¹ 到 6¹⁰ mod 11,判断 6 是不是 Z₁₁* 的生成元。

6, 36 ≡ 3, 3 × 6 = 18 ≡ 7, 7 × 6 = 42 ≡ 9, 9 × 6 = 54 ≡ 10, 10 × 6 = 60 ≡ 5, 5 × 6 = 30 ≡ 8, 8 × 6 = 48 ≡ 4, 4 × 6 = 24 ≡ 2, 2 × 6 = 12 ≡ 1。

十个数各一次,6 是生成元。

3. 指数 mod q

它解决什么问题

密码学里的指数动辄几百位。7¹¹⁵ mod 11 如果老老实实乘 115 次也能算,但指数再大就算不动了。生成元每走 q 步回到 1,利用这一点,可以把任何大指数先缩小到 0 到 q − 1 之间。

直觉

把 7 的幂排成一圈,一圈十格。往前走 10 步正好回到起点,等于没走。所以走 115 步,先扣掉整圈,只看剩下的零头。

一步一步看

目标:把 7¹¹⁵ 拆成整圈加零头,看出指数可以先模 10,逆元也能靠补满一圈找到。

  1. 7 的阶是 10,7¹⁰ ≡ 1,所以一圈是 10 格。

  2. 把 115 拆成整圈加零头:115 = 11 × 10 + 5。

  3. 11 整圈走完回到 1,(7¹⁰)¹¹ ≡ 1¹¹ = 1。

  4. 再走 5 格,停在 7⁵ = 10。所以 7¹¹⁵ ≡ 7⁵ = 10。

    7 的幂 7、5、2、3、10、4、6、9、8、1 顺时针排成一圈,每格旁边标 7 的几次方,顶上是 7 的 10 次方等于 1。右边写 115 等于 11 乘 10 加 5,先绕 11 整圈回到 1,再走 5 步;7 的 5 次方那一格的 10 用青绿圈出

  5. 逆元也能这样找。7³ = 2,再走 7 格就补满一圈:7³ × 7⁷ = 7¹⁰ ≡ 1,所以 7³ 的逆元是 7⁷ = 6。查乘法表 2 × 6 = 12 ≡ 1,对得上。

怎么算

gⁱ = g^(i mod q) (mod n),gⁱ 的逆元是 g^(q−i)

意思是:q 是生成元走一圈的步数(就是群的元素个数),n 是模数。指数部分只看除以 q 的余数;数值部分照常 mod n。gⁱ 再补 q − i 步正好走满一圈,回到 1,所以 g^(q−i) 是 gⁱ 的逆元。

在 Z₁₁* 里 n = 11、q = 10。两个模数各管一摊:指数 mod 10,数值 mod 11。

常见误解

指数也 mod 11

指数归群的大小管,是 mod 10。7¹¹⁵ 写成 115 mod 11 = 5 碰巧对了,换个数就会错。例如 7²⁰ 应按 20 mod 10 = 0 得 7⁰ = 1;按 mod 11 算成 7⁹ = 8 就错了。

以为 q 永远是 n − 1

q 是生成元的阶。7 生成整个 Z₁₁*,q = 10 = n − 1。3 只生成子群 {1, 3, 4, 5, 9},在这个子群里 q = 5 = (n − 1)/2。用哪个 q,看你在哪个群里算。

试一下

已知 7 是 Z₁₁* 的生成元,求 7²⁰⁰⁶ mod 11,再求 7⁴ 的逆元。

2006 = 200 × 10 + 6,所以 7²⁰⁰⁶ ≡ 7⁶ = 4。

7⁴ = 3,逆元是 7^(10−4) = 7⁶ = 4。验算 3 × 4 = 12 ≡ 1。

4. 加法写法下的循环群

它解决什么问题

前面都用乘法。下一讲的椭圆曲线把群运算写成加法,「自乘」变成「自加」。先在最熟悉的整数上看一遍加法版的循环群,到时候不会被记号绊住。

直觉

加法里,单位元是 0,逆元是相反数,「g 的 i 次方」变成「i 个 g 相加」,也就是 i·g。从 1 出发不停加 1,能走到所有正整数;不停减 1,能走到所有负整数。所以整数全体由 1 生成。

再加一个 mod n,数到 n 就绕回 0,数轴折成了一个圈。

一步一步看

目标:把生成元搬到加法写法里,看出 1 能走遍所有整数,在模 5 下也能走遍 0 到 4。

  1. 从 1 出发不停加 1:1、2、3、4、…;不停减 1:0、−1、−2、…。所有整数都能走到,ℤ = ⟨1⟩。

  2. 换成整数 mod 5:元素只有 0、1、2、3、4。

  3. 从 1 出发加 1:1、2、3、4,再加 1 得 5 ≡ 0,回到起点。

  4. 继续加:1、2、3、4、0,每 5 步重复一次。

    上行写整数 −2 到 7,下行写各自除以 5 的余数 3、4、0、1、2、3、4、0、1、2,整数 5 下面的 0 是青绿色,旁注数到 5 回到 0;右边 0 到 4 排成五边形的圈,箭头每次加 1,五步绕回 0

  5. 1 走满 5 步才回到 0,把 0 到 4 全走了一遍,所以 1 是整数 mod 5 加法群的生成元。

怎么判断

加法群 G = ⟨y⟩ 当且仅当 y 的倍数 …, −2y, −y, 0, y, 2y, … 恰好组成 G

意思是:乘法里看 g 的各次幂,加法里看 y 的各个倍数。判断方法一样,只是把「乘」换成「加」、把回到 1 换成回到 0。

记号 运算 单位元 a 的逆元 重复 i 次
乘法 × 1 a⁻¹ aⁱ
加法 + 0 −a i·a

常见误解

以为 ℤ 里随便一个数都能当生成元

2 的倍数只有偶数,⟨2⟩ 走不到 1。ℤ 的生成元只有 1 和 −1。

把「循环」理解成「元素排成环形」就够了

「cyclic」说的是生成元的倍数(或幂)走若干步回到起点、然后重复。ℤ 本身不回绕,也叫循环群,因为它由一个元素生成;它是无限循环群。

试一下

在整数 mod 6 的加法群里,列出 2 的倍数和 5 的倍数。哪个是生成元?

2 的倍数:2、4、6 ≡ 0,然后重复。只走到 {0, 2, 4},不是生成元。

5 的倍数:5、10 ≡ 4、15 ≡ 3、20 ≡ 2、25 ≡ 1、30 ≡ 0。六个数全走到,5 是生成元。

把它们串起来

一个元素反复自乘,必然回到 1,回来之前走过的那一圈有几格,就是它的阶。阶等于群的大小时,这一圈覆盖了整个群,这个元素就是生成元,群就是循环群。

Z₁₁* 里 7 和 4 是一对对照。7 的阶是 10,十格全走到,Z₁₁* = ⟨7⟩。4 的阶是 5,只走到 1、3、4、5、9。这五个数自成一个群,下一页 L07a-3 专门讲它。

阶还决定了指数怎么化简。7 走 10 步一圈,7 的任何次幂只看指数除以 10 的余数;逆元就是补满一圈还差的那几步。指数归群的大小管,数值归模数管。

换成加法写法,一切照搬:单位元换成 0,幂换成倍数。整数 mod n 由 1 生成,数到 n 回到 0,「循环」这个名字就是从这种回绕来的。下一讲的椭圆曲线点群,用的正是这套加法记号。

课件里的坑

  • [读图提醒] p.11 同一页的 n 有两个意思:aⁿ 里是指数,gⁱ mod n 里是模数。后面 p.12–14 的 n 都是模数,指数一律用 i。
  • p.13 的 7¹¹⁵:115 mod 11 和 115 mod 10 碰巧都等于 5,别因此以为指数也 mod 11。
  • p.14 写「q = n − 1 或 (n − 1)/2」,两种情况分别对应 7 生成整个 Z₁₁*(p.13)和 3 只生成一半(p.12)。
  • p.34–37 是视频截图,用加法记号,单位元是 0、逆元是 −a,和前面乘法记号对应着读。

课后 10 分钟:考点复习

这 10 分钟怎么用:先默写必背,再合上页面把 7 和 6 的幂 mod 11 各算一遍(每格用上一格乘底数再 mod 11);然后做完整例题,最后做变式题。

必背

  1. 循环群 G = ⟨g⟩:g 的幂跑遍 G,g 叫生成元,也叫原根
  2. 元素的阶是它自乘第一次回到 1 的次数;4 在 Z₁₁* 里的阶是 5,7 的阶是 10
  3. 7 是 Z₁₁* 的生成元;7¹¹ = 7,7¹¹⁵ = 7⁵ = 10
  4. gⁱ = g^(i mod q),gⁱ 的逆元是 g^(q−i);指数 mod q、数值 mod n
  5. 6 是 Z₁₁* 的生成元,6ⁱ 依次为 6, 3, 7, 9, 10, 5, 8, 4, 2, 1
  6. ℤ = ⟨1⟩ 是无限循环群;整数 mod n 的加法群也由 1 生成,数到 n 回到 0,「cyclic」由此得名

课件例题

例 1(课件 p.13):7ⁱ mod 11,求 7¹¹ 和 7¹¹⁵

见下方完整例题。

例 2(课件 p.27):Exercise-5,6 能当 Z₁₁* 的生成元吗

题面:填出 6¹ 到 6¹⁰ mod 11 的表,判断 6 能不能当 Z₁₁* 的生成元,给出理由。

提示

每格用上一格乘 6 再 mod 11。最后数一数十个结果里有没有重复。

解答
i 1 2 3 4 5 6 7 8 9 10
6ⁱ mod 11 6 3 7 9 10 5 8 4 2 1

能。6¹ 到 6¹⁰ 恰好是 1 到 10 各一次,6 的幂生成了整个 Z₁₁*。

也可以用 L07b 的定理一步判断:6⁵ ≡ 10,不等于 1,6 是生成元。考试时列表更稳,定理用来自查。

例 3(课件 p.34–36):ℤ = ⟨1⟩ 与 mod n 的回绕

题面:说明整数在加法下由 1 生成;再说明整数 mod n 的加法群为什么叫「循环」群。

提示

加法里「幂」换成「倍数」。mod n 之后,n 等于几?

解答

⟨1⟩ = {…, −2, −1, 0, 1, 2, …},1 不断加 1、不断减 1 能得到所有整数,所以 ℤ = ⟨1⟩,它是无限循环群。

整数 mod n 的加法群元素是 0 到 n − 1,同样由 1 生成。n ≡ 0、n + 1 ≡ 1、−1 ≡ n − 1,数到 n 又回到 0,每 n 个数重复一次,绕成一个圈。「cyclic」就是指这种回绕。

完整例题

题面(课件 p.13,第 (3) 问取自 p.14 的规则):G = Z₁₁*。(1) 填出 7¹ 到 7¹⁰ mod 11,判断 7 是不是生成元;(2) 求 7¹¹ 和 7¹¹⁵;(3) 求 7³ 的逆元并验证。

约定:每格用上一格乘 7 再 mod 11;指数 mod 10,数值 mod 11。

解法:

  1. 逐格算:7 → 49 ≡ 5 → 35 ≡ 2 → 14 ≡ 3 → 21 ≡ 10 → 70 ≡ 4 → 28 ≡ 6 → 42 ≡ 9 → 63 ≡ 8 → 56 ≡ 1。
i 1 2 3 4 5 6 7 8 9 10
7ⁱ mod 11 7 5 2 3 10 4 6 9 8 1
  1. 十个结果恰好是 1 到 10 各一次,7 是 Z₁₁* 的生成元。
  2. 7¹¹ = 7¹⁰ × 7 ≡ 1 × 7 = 7。
  3. 115 = 11 × 10 + 5,7¹¹⁵ = (7¹⁰)¹¹ × 7⁵ ≡ 7⁵ = 10。
  4. 7³ = 2。逆元是 7^(10−3) = 7⁷ = 6。验证 2 × 6 = 12 ≡ 1。

要点:「跑遍 1 到 10」才能下生成元结论;指数先 mod 10,数值 mod 11。

答题格式:先画表,再写「十格无重复,所以是生成元」;大指数写出「115 = 11 × 10 + 5」这一步;逆元写出 g^(q−i) 并验算。

变式题(先自己做)

(1) 改编自课件 p.13:已知 8 是 Z₁₁* 的生成元,求 8¹¹⁵。 (2) 求 8³ 和它的逆元,并验证。 (3) 求 8²⁰⁰⁶。

提示

先把 8 的幂算到 8⁵:8² = 64 ≡ 9,8⁴ = 81 ≡ 4。指数一律先除以 10 取余。

判分点与答案(非官方评分标准)

判分点:① 指数和数值用对模数;② 逆元用 g^(q−i) 并验算。

(1) 115 mod 10 = 5,8⁵ = 8⁴ × 8 = 32 ≡ 10。

(2) 8³ = 9 × 8 = 72 ≡ 6,逆元是 8⁷ = 8⁵ × 8² = 10 × 9 = 90 ≡ 2,验证 6 × 2 = 12 ≡ 1。

(3) 2006 mod 10 = 6,8⁶ = 10 × 8 = 80 ≡ 3。

闪卡自测

1. 什么叫循环群?什么叫生成元?

群里某个元素 g 的幂恰好组成整个群,这个群叫循环群,g 叫生成元,记作 G = ⟨g⟩(p.11)。

2. 4 在 Z₁₁* 里的阶是多少?

5,4 的幂是 4、5、9、3、1(p.15)。

3. 7 是 Z₁₁* 的生成元,7¹¹ 和 7¹¹⁵ 各是多少?

7¹¹ ≡ 7,7¹¹⁵ ≡ 7⁵ ≡ 10(p.13)。

4. gⁱ 的逆元怎么写?

g^(q−i),q 是生成元的阶(p.14)。

5. 6 能当 Z₁₁* 的生成元吗?

能,6 的幂 6, 3, 7, 9, 10, 5, 8, 4, 2, 1 跑遍 1 到 10(p.27)。

6. 为什么叫「循环」群?

生成元的幂(或倍数)走若干步后回到起点,绕成一个圈;整数 mod n 的加法群里 1 的倍数数到 n 又回到 0(p.35–36)。

下一讲

下一页 L07a-3 讲子群:4 只走到的那五个数 {1, 3, 4, 5, 9},为什么自己也是一个群。复习时先把 4 的幂默写熟。

下一讲 →
L07a-3 L07a-3 子群:走不遍全群的元素,绕出一个小群

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。