← COMP5521 全部讲次
L07b · 第 8 周

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₁₁* 看每个元素的阶落在哪里。

  1. p − 1 = 10,10 的因数是 1、2、5、10。

  2. 1 的阶是 1,10 的阶是 2(10² = 100 ≡ 1)。

  3. 3、4、5、9 自乘 5 次回到 1,阶是 5。

  4. 2、6、7、8 要乘满 10 次才回到 1,阶是 10。

    四个面板按阶分组:阶 1 只有 1;阶 2 只有 10;阶 5 是 3、4、5、9;阶 10 是 2、6、7、8,这一格用青绿框出。底部写阶只能是 10 的因数,阶 10 的四个就是生成元

  5. 没有阶为 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。

  1. 核对前提:11 = 2 × 5 + 1,p₁ = 5 是素数,定理可用。

  2. 要算的幂是 α^((11−1)/2) = α⁵。

  3. 算 3⁵:3² = 9,3⁴ = 9² = 81 ≡ 4,3⁵ = 4 × 3 = 12 ≡ 1。

    四个格子从左到右:3 的 1 次方是 3,平方是 9,4 次方是 9 的平方 81 同余 4,5 次方是 4 乘 3 等于 12 同余 1,最后一格用青绿框出。底部写 3 的 5 次方同余 1,所以 3 不是生成元,换成 −3 等于 8 就是

  4. 3⁵ ≡ 1,所以 3 不是生成元。

  5. 算 2⁵ = 32 = 2 × 11 + 10 ≡ 10。不等于 1,所以 2 是生成元。

  6. 把 2 到 9 的 a⁵ 都算出来,结果只有 1 和 10 两种。

    a 从 2 到 9 排成一行,下面写 a 的 5 次方模 11:2、6、7、8 得 10,圈和字都是青绿色,标「是」;3、4、5、9 得 1,标「否」。底部写 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 两两配对时,每对恰好有一个生成元。

  1. 3 不是 Z₁₁* 的生成元,因为 3⁵ ≡ 1。

  2. −3 在模 11 下就是 11 − 3 = 8。

  3. 验证 8:8 的幂依次是 8、9、6、4、10、3、2、5、7、1,跑遍 1 到 10,是生成元。

  4. 把 2 到 9 按相反数两两配对:2 和 9、3 和 8、4 和 7、5 和 6。每一对相加都是 11。

    四对数 2 和 9、3 和 8、4 和 7、5 和 6 并排,下面写各自相加等于 11。2、6、7、8 用青绿圈出,是生成元,每对恰好一个。底部写 1 和 10 也是一对,两个都被前提排除

  5. 每一对里恰好一个是生成元,另一个不是。

怎么算

前提同定理一,且 α 不是生成元。则 −α ≡ 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),对照「把它们串起来」那张表;最后做变式题。

必背

  1. Z₁₁* 的生成元是 2、6、7、8;3、4、5、9 的幂只跑出子群 {1, 3, 4, 5, 9}
  2. p = 2p₁ + 1(p₁ 也是素数)且 α ≢ ±1:α 是生成元当且仅当 α^((p−1)/2) ≢ 1 (mod p);α 不是则 −α 是
  3. 一般找生成元很难,p − 1 的分解已知就不难
  4. 3⁵ ≡ 1,3 不是 Z₁₁* 的生成元,−3 = 8 是
  5. 比特币、以太坊的签名基于椭圆曲线点组成的循环群

课件例题

例 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。

解法:

  1. 核对前提:11 = 2 × 5 + 1,p₁ = 5 是素数,定理可用。3 ≢ ±1。
  2. 算 3^((11−1)/2) = 3⁵:3² = 9,3⁴ = 81 ≡ 4,3⁵ = 4 × 3 = 12 ≡ 1。
  3. 结果等于 1,按定理一,3 不是生成元。它的阶是 5,只生成子群 {1, 3, 4, 5, 9}。
  4. 按定理二,−3 ≡ 11 − 3 = 8 是生成元。
  5. 验证: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₁₁* 的幂次表默写熟。

下一讲 →
Lab6 Lab6 在 Regtest 上发比特币:挖币、钱包转账、手工拼一笔原始交易

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