L07b 判定生成元:p = 2p₁ + 1 时只算一个幂
为什么一般找生成元很难;p = 2p₁ + 1 时元素的阶只剩两种可能,于是只算 α^((p−1)/2) 就能判定;判出不是之后换成 −α 就是。最后用 Z₁₁* 的幂次表把整讲收在一起。
一句话版
判断一个元素是不是生成元,不必把它的幂全列出来。当 p = 2p₁ + 1、p₁ 也是素数时,只算 α^((p−1)/2):不等于 1 就是生成元,等于 1 就换成 −α,−α 一定是。
生成元、元素的阶见 L07a-2,子群大小整除群大小见 L07a-3。这一页只讲怎么快速判定生成元。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| Zₚ* | 读「Z p 星」 | 1 到 p − 1,配上「相乘再 mod p」,p 是素数 |
| 生成元 | generator,也叫原根 primitive root | 自乘能走遍 1 到 p − 1 每个数的那个元素 |
| 元素的阶 | order of an element | 自乘几次第一次回到 1 |
| p = 2p₁ + 1 | p₁ 也是素数 | 一类特殊素数,11 = 2 × 5 + 1 就是一例 |
| α^((p−1)/2) | 读「α 的 p 减 1 除以 2 次方」 | 判定时只需要算的那一个幂,p = 11 时就是 α⁵ |
| −α | 模 p 下的相反数 | 就是 p − α,例如模 11 时 −3 = 8 |
一个类比:只停两种站的环线
想象一条有 10 个站的环线,每趟车按自己的固定跳法前进。线路规定很死:除了原地不动的那趟(1)和来回折返的那趟(10),其余每趟车要么 5 站一圈,要么 10 站一圈,没有第三种。
要知道一趟车能不能跑遍全线,不用跟它坐满 10 站。坐 5 站看一眼:回到起点了,它就是 5 站一圈的小环线;没回到,它只剩 10 站一圈这一种可能,必然跑遍全线。
小环线的车,掉头开就是大环线。3 这趟车 5 站回到起点;反过来开的 −3 = 8,跑满 10 站。
类比在哪里失效:
- 「只有两种圈长」完全靠 p − 1 = 2p₁ 的因数很少。p − 1 的因数一多,圈长就有好几种,坐 5 站看一眼不够。
- 群里的「掉头」是乘以 −1,只在 −1 恰好把小圈元素送出小圈时才管用。
从零讲起
1. 生成元为什么难找
它解决什么问题
密码方案一开头常要选一个生成元。最笨的判定办法是把 α¹ 到 α^(p−1) 全列出来,看有没有走满。p 只有 11 时还行,真实系统里 p 有几百位,这样列一辈子也列不完。先要弄清楚:到底要查哪些东西,才能断定 α 走满了。
直觉
上一页讲过,元素的阶一定整除群的大小。Zₚ* 有 p − 1 个元素,所以 α 的阶只能是 p − 1 的某个因数。
α 是生成元,就是它的阶恰好等于 p − 1。只要排除掉所有更小的因数,就能断定。更小的因数不用一个个试,只要试「p − 1 除以某个素因数」这几个就够了。
一步一步看
目标:逐个找出 Z₁₁* 里元素的阶,看出阶只能是 10 的因数,阶为 10 的四个就是生成元。
拿 Z₁₁* 看每个元素的阶落在哪里。
-
p − 1 = 10,10 的因数是 1、2、5、10。
-
1 的阶是 1,10 的阶是 2(10² = 100 ≡ 1)。
-
3、4、5、9 自乘 5 次回到 1,阶是 5。
-
2、6、7、8 要乘满 10 次才回到 1,阶是 10。
-
没有阶为 3、4、7 的元素,因为它们不整除 10。阶 10 的四个就是生成元。
怎么算
α 是 Zₚ* 的生成元 ⟺ 对 p − 1 的每个素因数 r,都有 α^((p−1)/r) ≢ 1 (mod p)
意思是:α 的阶如果比 p − 1 小,它一定整除某个 (p − 1)/r,那么 α^((p−1)/r) 就会等于 1。把这几个幂都算一遍,全都不是 1,阶就只能是 p − 1。
难点在第一步:要先把 p − 1 分解成素因数,才知道有哪些 r。p − 1 分解不了,就列不出要检查的幂。所以课件说一般找生成元很难,p − 1 的分解已知就不难。
例:p = 11,p − 1 = 10 = 2 × 5,要检查 α⁵ 和 α²。
常见误解
以为一个元素的阶可以是任何数
阶一定整除 p − 1。Z₁₁* 里所有元素的阶只有 1、2、5、10 四种,没有阶为 3 或 7 的元素。
以为检查 α¹ 到 α^(p−2) 都不等于 1 才行
那是列全表的做法。只需要检查 α^((p−1)/r) 这几个幂,r 跑遍 p − 1 的素因数。p = 11 时只有两个。
试一下
p = 19 时 p − 1 = 18。要判断 α 是不是生成元,需要检查哪几个幂?
18 = 2 × 3²,素因数是 2 和 3。要检查 α^(18/2) = α⁹ 和 α^(18/3) = α⁶,两个都不等于 1,α 就是生成元。
2. 定理一:只算一个幂
它解决什么问题
上一个概念要检查 p − 1 的每个素因数。如果 p − 1 的素因数只有 2 和另一个素数 p₁,而且 α 已经排除了 ±1,检查就能缩成一个幂。
从哪来(补充)
p = 2q + 1 且 q 也是素数时,p 叫安全素数,q 叫 Sophie Germain 素数。名字来自法国数学家 Sophie Germain,她在研究费马大定理时用到这类素数。Diffie–Hellman 等密码方案常选安全素数,因为这样群里有一个很大的素数阶子群。
出处:Wikipedia: Safe and Sophie Germain primes
直觉
p − 1 = 2p₁,因数只有 1、2、p₁、2p₁。阶为 1 的只有 1,阶为 2 的只有 −1,这两个被前提排除了。剩下的 α 阶只能是 p₁ 或 2p₁。
阶是 p₁,α^(p₁) 就等于 1;阶是 2p₁,α 就是生成元。所以只看 α^(p₁) 这一个幂,就能把两种情况分开。p₁ 正好是 (p − 1)/2。
一步一步看
目标:用定理一在 p = 11 下只算 α⁵,看出结果等于 1 就不是生成元,所以 3 被排除、2 通过。
拿 p = 11 判断 3 和 2。
-
核对前提:11 = 2 × 5 + 1,p₁ = 5 是素数,定理可用。
-
要算的幂是 α^((11−1)/2) = α⁵。
-
算 3⁵:3² = 9,3⁴ = 9² = 81 ≡ 4,3⁵ = 4 × 3 = 12 ≡ 1。
-
3⁵ ≡ 1,所以 3 不是生成元。
-
算 2⁵ = 32 = 2 × 11 + 10 ≡ 10。不等于 1,所以 2 是生成元。
-
把 2 到 9 的 a⁵ 都算出来,结果只有 1 和 10 两种。
怎么算
前提:p = 2p₁ + 1,p₁ 是素数,α ≢ ±1 (mod p)。
α 是生成元 ⟺ α^((p−1)/2) ≢ 1 (mod p)
意思是:算一个幂 α^((p−1)/2)。结果不等于 1,α 就是生成元;等于 1,α 不是,它的阶是 p₁,只生成一个 p₁ 个元素的子群。
算这个幂用反复平方:先算 α²、α⁴,再拼出 α⁵ = α⁴ × α。每一步都先 mod p。
常见误解
把这个定理用到任意素数上
p = 13 时 p − 1 = 12 = 2² × 3,只检查 α⁶ 不够,还要检查 α⁴。定理的前提 p = 2p₁ + 1 必须先核对,答题时写出这一步。
忘了排除 ±1
10 ≡ −1,10⁵ ≡ 10,不等于 1,照定理会被误判成生成元。它的阶其实是 2。所以前提里写了 α ≢ ±1,先把 1 和 p − 1 排除掉。
试一下
用定理一判断 9 是不是 Z₁₁* 的生成元。
9² = 81 ≡ 4,9⁴ = 4² = 16 ≡ 5,9⁵ = 5 × 9 = 45 ≡ 1。等于 1,9 不是生成元。
3. 定理二:不是就换成 −α
它解决什么问题
定理一能判出「不是」,但判完还得接着找一个是的。定理二给出一个现成的答案:α 不是,那 −α 一定是,一步就找到。
直觉
p₁ 是奇数。α 不是生成元,意味着 α^(p₁) ≡ 1。换成 −α,(−α)^(p₁) = (−1)^(p₁) × α^(p₁) = −1 × 1 = −1,不等于 1。按定理一,−α 就是生成元。
一步一步看
目标:把不是生成元的 3 换成 −3 = 8 验一遍,再看 2 到 9 两两配对时,每对恰好有一个生成元。
-
3 不是 Z₁₁* 的生成元,因为 3⁵ ≡ 1。
-
−3 在模 11 下就是 11 − 3 = 8。
-
验证 8:8 的幂依次是 8、9、6、4、10、3、2、5、7、1,跑遍 1 到 10,是生成元。
-
把 2 到 9 按相反数两两配对:2 和 9、3 和 8、4 和 7、5 和 6。每一对相加都是 11。
-
每一对里恰好一个是生成元,另一个不是。
怎么算
前提同定理一,且 α 不是生成元。则 −α ≡ p − α 是生成元。
意思是:不是生成元的 α,用 p 减它就得到一个生成元。不用再算任何幂,最多验算一下。
常见误解
把 −α 当成负数去算幂
模 p 下 −α 就是 p − α,直接用 8 代替 −3 去算更不容易错。
以为反过来也成立:α 是生成元,−α 也是
不成立。2 是生成元,−2 = 9 不是。定理二只说「不是」的那个,取反后变成「是」。
试一下
4 和 5 都不是 Z₁₁* 的生成元。按定理二,各自换成谁?
−4 = 11 − 4 = 7,−5 = 11 − 5 = 6。7 和 6 都是生成元,和幂次表一致。
把它们串起来
上半讲的 Z₁₁* 在这里补成一张幂次表,下面只列 a⁵ 和阶两行:
| a | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| a⁵ mod 11 | 10 | 1 | 1 | 1 | 10 | 10 | 10 | 1 | 10 |
| a 的阶 | 10 | 5 | 5 | 5 | 10 | 10 | 10 | 5 | 2 |
| 生成元? | 是 | 否 | 否 | 否 | 是 | 是 | 是 | 否 | 否 |
这张表里能读出三件事。a⁵ 只取 1 和 10 两个值,除去 10 本身,a⁵ = 10 的恰好是四个生成元,这是定理一。生成元和非生成元按相反数配对,这是定理二。阶为 5 的四个元素加上 1,就是子群 {1, 3, 4, 5, 9}。
生成元一共四个,正好是 φ(10)。一般地 Zₚ* 有 φ(p − 1) 个生成元,这是补充结论,课件没讲,可以用来检查自己数得对不对。
课件最后一句话交代了这一讲的用途:比特币和以太坊的签名,建立在椭圆曲线上的点组成的循环群上。下一讲把「乘法」换成「点加法」,把「求幂」换成「点乘以整数」,循环群、生成元、离散对数这些概念原样搬过去。
课件里的坑
- [读图提醒] p.12 说 3 生成一个 5 阶子群,p.21 判定 3 不是生成元,两页不矛盾:前者对象是子群 {1, 3, 4, 5, 9},后者对象是整个 Z₁₁*。
- [读图提醒] p.29 题目写「using theorems in p19」,两个定理实际印在 p.20,p.19 是生成元的定义页。
- p.20 的两个定理只在 p = 2p₁ + 1、p₁ 是素数时成立,课件没有提醒换成别的素数要多检查几个幂。
- [板书笔误] p.21 Exercise-3 课堂速算写 3² = 9 ≡ −2,再 (−2)² × 3 = 12 ≡ 1,讲师把这一步标成「3⁴」。(−2)² × 3 = 3² × 3² × 3 = 3⁵,应标 3⁵;结论不变:3⁵ ≡ 1 (mod 11),3 不是生成元。
- p.22 表里 10 那一行的 a⁵ 也等于 10,但 10 就是 −1,被定理前提排除,它的阶是 2,不是生成元。
课后 10 分钟:考点复习
这 10 分钟怎么用:先默写必背,再合上页面把 Z₁₁* 的幂次表从 2 到 10 自己算一遍(每格用上一格乘 a 再 mod 11),对照「把它们串起来」那张表;最后做变式题。
必背
- Z₁₁* 的生成元是 2、6、7、8;3、4、5、9 的幂只跑出子群 {1, 3, 4, 5, 9}
- p = 2p₁ + 1(p₁ 也是素数)且 α ≢ ±1:α 是生成元当且仅当 α^((p−1)/2) ≢ 1 (mod p);α 不是则 −α 是
- 一般找生成元很难,p − 1 的分解已知就不难
- 3⁵ ≡ 1,3 不是 Z₁₁* 的生成元,−3 = 8 是
- 比特币、以太坊的签名基于椭圆曲线点组成的循环群
课件例题
例 1(课件 p.21):Exercise-3,3 是 Z₁₁* 的生成元吗
见下方完整例题。
例 2(课件 p.22):Z₁₁* 的幂次表,找出全部生成元
题面:课件给出 a = 1 到 10、指数 i = 1 到 10 的 aⁱ mod 11 表。从表中找出 Z₁₁* 的全部生成元,并写出每个元素的阶。
提示
一行里 1 到 10 都出现的才是生成元。阶就是每行第一次出现 1 的那一列。
解答
| a | a¹ | a² | a³ | a⁴ | a⁵ | a⁶ | a⁷ | a⁸ | a⁹ | a¹⁰ |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 4 | 8 | 5 | 10 | 9 | 7 | 3 | 6 | 1 |
| 3 | 3 | 9 | 5 | 4 | 1 | 3 | 9 | 5 | 4 | 1 |
| 4 | 4 | 5 | 9 | 3 | 1 | 4 | 5 | 9 | 3 | 1 |
| 5 | 5 | 3 | 4 | 9 | 1 | 5 | 3 | 4 | 9 | 1 |
| 6 | 6 | 3 | 7 | 9 | 10 | 5 | 8 | 4 | 2 | 1 |
| 7 | 7 | 5 | 2 | 3 | 10 | 4 | 6 | 9 | 8 | 1 |
| 8 | 8 | 9 | 6 | 4 | 10 | 3 | 2 | 5 | 7 | 1 |
| 9 | 9 | 4 | 3 | 5 | 1 | 9 | 4 | 3 | 5 | 1 |
| 10 | 10 | 1 | 10 | 1 | 10 | 1 | 10 | 1 | 10 | 1 |
一行跑遍 1 到 10 的是生成元:2、6、7、8,课件用星号标出的也是这四个。阶:1 的阶是 1,10 的阶是 2,3、4、5、9 的阶是 5,2、6、7、8 的阶是 10。所有阶都整除 10,a¹⁰ 一列全是 1。
例 3(课件 p.29):Exercise-7,用定理判断 2 是不是生成元
题面:在 Z₁₁* 中,用判定生成元的定理说明 2 是不是生成元。
提示
先核对 11 = 2 × 5 + 1,再算 2⁵ mod 11。
解答
11 = 2 × 5 + 1,5 是素数,定理可用。2 ≢ ±1。2⁵ = 32 = 22 + 10 ≡ 10,不等于 1,按定理一,2 是生成元。
对照幂次表,2 那一行是 2, 4, 8, 5, 10, 9, 7, 3, 6, 1,跑遍 1 到 10,结论一致。题目写的「p19」按 p.20 的定理作答。
完整例题
题面(课件 p.21 Exercise-3):在 (Z₁₁*, × mod 11) 中,用 p.20 的定理判断 3 是不是生成元;如果不是,给出一个生成元并验证。
约定:−α 写成 p − α;所有幂每一步都先 mod 11。
解法:
- 核对前提:11 = 2 × 5 + 1,p₁ = 5 是素数,定理可用。3 ≢ ±1。
- 算 3^((11−1)/2) = 3⁵:3² = 9,3⁴ = 81 ≡ 4,3⁵ = 4 × 3 = 12 ≡ 1。
- 结果等于 1,按定理一,3 不是生成元。它的阶是 5,只生成子群 {1, 3, 4, 5, 9}。
- 按定理二,−3 ≡ 11 − 3 = 8 是生成元。
- 验证:8 的幂依次是 8, 9, 6, 4, 10, 3, 2, 5, 7, 1,跑遍 1 到 10。
要点:先核对前提再用定理;3⁵ 要写出中间步骤。
答题格式:前提核对一行、3⁵ 计算一行、定理一结论一行、定理二给出 8、最后列 8 的幂验证。
变式题(先自己做)
(1) 改编自课件 p.21:p = 23 = 2 × 11 + 1。判断 2 是不是 Z₂₃* 的生成元,不是的话给出 −2 是否为生成元。 (2) Z₂₃* 一共有几个生成元?由 2 的幂组成的子群有几个元素? (3) 判断 5 是不是 Z₂₃* 的生成元。
提示
要算的是 α¹¹ mod 23。(1) 用 2⁵ = 32 ≡ 9 起步:2¹⁰ = 9² = 81 ≡ 12,再乘 2。(2) 生成元个数可以用 φ(p − 1) 来数(补充结论,课件没讲)。(3) 5² = 25 ≡ 2,再反复平方。
判分点与答案(非官方评分标准)
判分点:① 核对 23 = 2 × 11 + 1 且 11 是素数;② 幂的计算过程;③ 正确引用两个定理。
(1) 2¹¹ = 2¹⁰ × 2 ≡ 12 × 2 = 24 ≡ 1,所以 2 不是生成元;按定理二,−2 ≡ 21 是生成元。
(2) φ(22) = 10 个。2 的阶是 11,子群有 11 个元素。
(3) 5² = 2,5⁴ = 4,5⁸ = 16,5¹¹ = 5⁸ × 5² × 5 = 16 × 2 × 5 = 160 ≡ 22,不等于 1,所以 5 是生成元。
闪卡自测
1. 为什么一般情况下找生成元很难?
要先分解 p − 1,对每个素因数 r 检查 α^((p−1)/r);分解不了就无从检查(p.19)。
2. p = 2p₁ + 1 时怎样一步判定生成元?
α ≢ ±1 时算 α^((p−1)/2),不等于 1 就是生成元(p.20)。
3. 3 是 Z₁₁* 的生成元吗?不是的话谁是?
不是,3⁵ ≡ 1;按定理二 −3 = 8 是(p.21)。
4. Z₁₁* 的生成元有哪些?
2、6、7、8(p.22)。
5. 用定理判断 2 是不是 Z₁₁* 的生成元。
2⁵ ≡ 10,不等于 1,是生成元(p.29)。
6. 循环群和区块链有什么关系?
比特币、以太坊的签名建立在椭圆曲线上的点组成的循环群上(p.23)。
下一讲
下一讲 L08a 讲椭圆曲线:把这一讲的循环群搬到曲线上的点,「乘法」换成「点加法」,「求幂」换成「点乘以整数」。同周的 Lab 6 在 Regtest 上动手发比特币交易,那些交易的签名用的正是椭圆曲线群。复习时先把 Z₁₁* 的幂次表默写熟。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。