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。
-
4¹ = 4。
-
4² = 4 × 4 = 16 ≡ 5。
-
4³ = 5 × 4 = 20 ≡ 9。
-
4⁴ = 9 × 4 = 36 ≡ 3。
-
4⁵ = 3 × 4 = 12 ≡ 1。回到 1 了,一共用了 5 步。
-
再往下乘,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。
-
7¹ = 7。
-
7² = 7 × 7 = 49 ≡ 5。
-
7³ = 5 × 7 = 35 ≡ 2。
-
7⁴ = 2 × 7 = 14 ≡ 3,7⁵ = 3 × 7 = 21 ≡ 10。
-
7⁶ = 10 × 7 = 70 ≡ 4,7⁷ = 4 × 7 = 28 ≡ 6。
-
7⁸ = 6 × 7 = 42 ≡ 9,7⁹ = 9 × 7 = 63 ≡ 8。
-
7¹⁰ = 8 × 7 = 56 ≡ 1。回到 1,用了 10 步。
-
十个结果 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,逆元也能靠补满一圈找到。
-
7 的阶是 10,7¹⁰ ≡ 1,所以一圈是 10 格。
-
把 115 拆成整圈加零头:115 = 11 × 10 + 5。
-
11 整圈走完回到 1,(7¹⁰)¹¹ ≡ 1¹¹ = 1。
-
再走 5 格,停在 7⁵ = 10。所以 7¹¹⁵ ≡ 7⁵ = 10。
-
逆元也能这样找。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、2、3、4、…;不停减 1:0、−1、−2、…。所有整数都能走到,ℤ = ⟨1⟩。
-
换成整数 mod 5:元素只有 0、1、2、3、4。
-
从 1 出发加 1:1、2、3、4,再加 1 得 5 ≡ 0,回到起点。
-
继续加:1、2、3、4、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);然后做完整例题,最后做变式题。
必背
- 循环群 G = ⟨g⟩:g 的幂跑遍 G,g 叫生成元,也叫原根
- 元素的阶是它自乘第一次回到 1 的次数;4 在 Z₁₁* 里的阶是 5,7 的阶是 10
- 7 是 Z₁₁* 的生成元;7¹¹ = 7,7¹¹⁵ = 7⁵ = 10
- gⁱ = g^(i mod q),gⁱ 的逆元是 g^(q−i);指数 mod q、数值 mod n
- 6 是 Z₁₁* 的生成元,6ⁱ 依次为 6, 3, 7, 9, 10, 5, 8, 4, 2, 1
- ℤ = ⟨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。
解法:
- 逐格算: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 到 10 各一次,7 是 Z₁₁* 的生成元。
- 7¹¹ = 7¹⁰ × 7 ≡ 1 × 7 = 7。
- 115 = 11 × 10 + 5,7¹¹⁵ = (7¹⁰)¹¹ × 7⁵ ≡ 7⁵ = 10。
- 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 的幂默写熟。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。