L08a-2 模 p 上的椭圆曲线:13 个点绕成一个循环群
把实数曲线搬到模 11 上:先补模逆和平方剩余,再逐个数出曲线上的点,用乘模逆代替除法做点加法,最后看生成元和点的阶。
一句话版
密码学不用实数,用模素数 p 的整数。把曲线方程放到模 p 下,曲线就变成格子上的一堆散点,但上一页的加法公式一个字不改照样能用,只是「除以某个数」要换成「乘以它的模逆」。
这一页用 y² = x³ + x + 6 (mod 11) 一路算到底:数出 13 个点,用公式算出 α 的倍数,看着它们绕成一个循环群。公式和几何画法见 L08a,循环群和生成元的说法见 L07a。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 模 p | mod p | 只留除以 p 的余数,数字永远落在 0 到 p − 1 |
| 模逆 | modular inverse | 模 p 下和 d 相乘得 1 的那个数,记作 d⁻¹ |
| 平方剩余 | quadratic residue, QR | 模 p 下能写成某个数平方的数 |
| 生成元 | generator | 一直加自己就能走遍群里所有元素的点 |
| 阶 | order | 一个点加自己几次第一次回到 O |
| α | 读「阿尔法」 | 课件给这条曲线选的生成元 (2, 7) |
一个类比:只有 11 格的钟面
模 11 就像一块只有 0 到 10 共 11 格的钟面。走过 10 再往前就绕回 0,任何算式算完都要看指针停在哪一格。
在这块钟面上,「除以 3」没有小数可用。办法是找一个数,乘 3 正好让指针停在 1,这个数就是 3 的逆元。之后所有「除以 3」都改成「乘它」。
曲线上的点也被放到这块钟面上:横坐标、纵坐标都只能是 0 到 10 的整数,满足方程的格子才算曲线上的点。原来连续的一条线,只剩零零星星的十几个格子。
类比在哪里失效:
- 钟面只有一个指针,曲线上的点有两个坐标,两个坐标各自在钟面上绕。
- 钟面上每个数都能除以别的数吗?只有 p 是素数时,非零数才都有逆元,所以课件要求 p 是素数。
- 钟面看不出「连线」:模 p 下的直线会在格子里折成好几段平行线,几何直觉基本用不上,只能靠公式。
从零讲起
1. 先补一块:模逆和平方剩余(补充)
它解决什么问题
上一页的公式里到处是除法:λ = (y₂ − y₁)/(x₂ − x₁)。模 p 下没有分数,必须有办法把除法变成整数运算,这就是模逆。
列曲线上的点时,要判断「右边算出来的数能不能开平方」。模 p 下能开平方的数叫平方剩余,提前把它们列出来,后面查表就行。
直觉
模逆就是「倒数」在钟面上的替身。实数里 3 × (1/3) = 1;模 11 下找不到 1/3,但 3 × 4 = 12,绕一圈后停在 1,所以 4 就扮演 1/3。
平方剩余可以这样找:把 0 到 10 每个数平方一遍,看结果落在哪些格子上。落到的格子就是平方剩余,落不到的就开不了方。因为 y 和 11 − y 平方后结果相同,每个非零平方剩余正好被落到两次。
一步一步看
目标:先在模 11 下查出 3 的逆元,再把 0 到 10 全部平方,看出哪些数是平方剩余、各对应几个 y。
-
求 3 在模 11 下的逆元:把 3 × 1 到 3 × 10 逐个算出来,找结果是 1 的那一列。
-
第 4 列是 1,所以 3⁻¹ = 4。以后模 11 下「除以 3」就是「乘以 4」。
-
把 0 到 10 全部平方再模 11,看结果分布。
-
非零结果只有 1、3、4、5、9 五个,这就是模 11 的平方剩余,每个对应两个 y。
怎么算
模逆的定义:
d × d⁻¹ ≡ 1 (mod p)
意思是:d⁻¹ 是 0 到 p − 1 里乘 d 之后余数为 1 的那个数。p 小时直接试;p 大时用第 2 讲的扩展欧几里得算法。
分数就这样换掉:
a/d ≡ a × d⁻¹ (mod p)
意思是:模 p 下「a 除以 d」等于「a 乘 d 的逆元」,结果再取余数。例如模 11 时 13/14 先化成 2/3,再算 2 × 4 = 8。负数也先取余:−3 ≡ 8 (mod 11)。
模 11 的平方表只要算到 5:1² = 1,2² = 4,3² = 9,4² = 5,5² = 3。6 到 10 的平方和 5 到 1 对称重复。
常见误解
以为 13/14 模 11 可以先算成小数再取整
模 p 下没有小数这回事。正确做法是先把分子分母各自取余,13 ≡ 2、14 ≡ 3,再乘逆元:2 × 3⁻¹ = 2 × 4 = 8。
以为每个数都有模逆
0 没有逆元,任何数乘 0 都是 0。p 是素数时,1 到 p − 1 才全都有逆元。这也是公式里 x₁ = x₂ 或 y₁ = 0 时要单独处理的原因。
试一下
模 11 下,2⁻¹ 和 10⁻¹ 各是多少?5 是不是平方剩余?
2 × 6 = 12 ≡ 1,所以 2⁻¹ = 6。10 × 10 = 100 = 99 + 1,所以 10⁻¹ = 10。
4² = 16 ≡ 5,5 是平方剩余,对应 y = 4 和 y = 7。
2. 数出曲线上的点
它解决什么问题
要把曲线上的点当成一个群,先得知道群里有哪些元素、一共几个。模 p 下点是有限的,可以一个不漏地列出来,这也是考试的固定题型。
直觉
方程是 y² = 右边。只要逐个试 x,算出右边,再问「这个数能不能开平方」。能开就得到两个 y,开不了这个 x 就没有点。
两个 y 加起来正好是 p,比如 4 和 7 加起来是 11。这就是实数图像「关于 x 轴对称」在模 p 下的样子:点集关于直线 y = p/2 上下对称。
一步一步看
目标:把 x 从 0 到 10 逐个代入曲线再查平方表,数出这条模 11 曲线上一共 13 个点。
曲线 y² = x³ + x + 6 (mod 11)。
-
先查非奇异:4 × 1 + 27 × 36 = 976 ≡ 8,不为 0。
-
x 从 0 到 10 逐个代入,算右边,查平方表:
x x³ + x + 6 mod 11 平方剩余? y 0 6 否 1 8 否 2 5 是 4, 7 3 3 是 5, 6 4 8 否 5 4 是 2, 9 6 8 否 7 4 是 2, 9 8 9 是 3, 8 9 7 否 10 4 是 2, 9 -
6 个 x 各贡献 2 个点,共 12 个,再加 O,一共 13 个点。
-
把 12 个点画在格子上,能看到它们关于 y = 5.5 上下成对。
怎么算
列点的固定流程:
- 对每个 x ∈ {0, …, p − 1} 算 r = x³ + ax + b mod p
- r 是平方剩余:得两个点 (x, y) 和 (x, p − y)
- r = 0:只有一个点 (x, 0)
- r 不是平方剩余:这个 x 没有点
- 最后加上 O
意思是:点数等于「平方剩余的 x 个数 × 2」加上「r = 0 的 x 个数」再加 1。
点数大致在 p + 1 附近。课件画了同一条曲线 y² = x³ − 7x + 10 在四个素数下的散点图,程序数出的点数(含 O)是:
| p | 19 | 97 | 127 | 487 |
|---|---|---|---|---|
| 点数 | 24 | 82 | 133 | 474 |
这个「在 p + 1 附近」的规律叫 Hasse 定理,课件没讲。
常见误解
数完 12 个点就交卷
还差无穷远点 O,群里一共 13 个元素。O 不在格子里,散点图上画不出来,但它是单位元,不能漏。
以为每个 x 都对应两个点
只有右边是平方剩余的 x 才有点。这条曲线 11 个 x 里有 5 个一个点都没有。右边恰好为 0 时只有一个点。
试一下
在同一条曲线上,x = 4 为什么没有点?(8, 3) 的上下伙伴是谁?
x = 4 时右边是 64 + 4 + 6 = 74 ≡ 8,8 不在 {1, 3, 4, 5, 9} 里,开不了方。
(8, 3) 的伙伴是 (8, 11 − 3) = (8, 8)。
3. 模 p 下的点加法
它解决什么问题
有了点集,还要算两个点的和。实数上靠画图,模 p 下画不了直线,只能照搬公式。这一步演示公式在模 p 下怎么跑,顺便把 α 的倍数全部算出来。
直觉
公式一字不改,只做两件事:分数换成乘模逆,每一步都取余数。负数加 p 变回正数。
课件在 y² = x³ − x + 3 (mod 127) 上画了 (16, 20) 和 (41, 120) 之间的「直线」:它在格子里撞到边就从另一头绕回来,折成好几段平行线。图看着乱,公式算起来和实数一样干净。
一步一步看
目标:从 α = (2, 7) 出发算出 2α 和 3α,看出模 p 下点加法照用原公式,只是除法换成乘逆元。
曲线 y² = x³ + x + 6 (mod 11),α = (2, 7)。
-
2α 用倍点公式。λ = (3 × 2² + 1)/(2 × 7) = 13/14 ≡ 2/3 ≡ 2 × 4 = 8。
-
x = 8² − 2 × 2 = 60 ≡ 5;y = 8 × (2 − 5) − 7 = −31 ≡ 2。2α = (5, 2)。
-
3α = 2α + α 用加法公式。λ = (7 − 2)/(2 − 5) = 5/(−3) ≡ 5/8 ≡ 5 × 7 = 35 ≡ 2,这里 8⁻¹ = 7。
-
x = 2² − 5 − 2 = −3 ≡ 8;y = 2 × (5 − 8) − 2 = −8 ≡ 3。3α = (8, 3)。
-
照这样一直加 α,12 步走遍所有点,第 13 步回到 O。
怎么算
公式和上一页完全相同,两点相加:
λ ≡ (y₂ − y₁) × (x₂ − x₁)⁻¹,x₃ ≡ λ² − x₁ − x₂,y₃ ≡ λ(x₁ − x₃) − y₁ (mod p)
意思是:先用模逆算出斜率,再套同一个模板,每一步结果都取余到 0 到 p − 1。倍点时把 λ 换成 (3x₁² + a) × (2y₁)⁻¹。
α 的倍数全表:
| k | kα | k | kα |
|---|---|---|---|
| 1 | (2, 7) | 7 | (7, 2) |
| 2 | (5, 2) | 8 | (3, 5) |
| 3 | (8, 3) | 9 | (10, 9) |
| 4 | (10, 2) | 10 | (8, 8) |
| 5 | (3, 6) | 11 | (5, 9) |
| 6 | (7, 9) | 12 | (2, 4) |
自查规律:kα 和 (13 − k)α 横坐标相同、纵坐标相加为 11,因为它们相加得 13α = O,互为逆元。1α 和 12α、6α 和 7α 都是这样的一对。
常见误解
算 5/(−3) 时直接用 3 的逆元
分母是 −3,先取余变成 8,再求 8 的逆元 7。直接用 3⁻¹ 会差一个负号,得出错误的点。
算完不验证,错了也不知道
每算出一个点,把它代回方程检查一次。例如 (5, 2):右边 125 + 5 + 6 = 136 ≡ 4,左边 2² = 4,对上了。也可以对照 kα 和 (13 − k)α 的对称规律。
试一下
用 α 表求 (2, 7) 的逆元,并用表算 5α + 9α。
(2, 7) 的逆元是 (2, 11 − 7) = (2, 4),也就是 12α。
5α + 9α = 14α = 13α + α = O + α = α = (2, 7)。
4. 生成元和点的阶
它解决什么问题
密码学要用的是循环群:选一个点当基点,用它的倍数表示群里所有元素。要知道哪个点能当基点,就得看点的阶。
直觉
一个点的阶,就是从它出发一直加自己,第几步第一次回到 O。阶等于群的大小,这个点就能走遍全群,它是生成元。
上一讲讲过:每个元素的阶整除群的大小。13 是素数,因数只有 1 和 13,O 的阶是 1,其余每个点的阶只能是 13。所以课件说「任取一个非 O 的点都是生成元」,在这条曲线上成立。
一步一步看
目标:把 8 个点逐个自加到回到 O,看出哪几个点阶为 8 是生成元,(8, 0) 为何阶只有 2。
换一条曲线 y² = x³ + 10x + 2 (mod 11),课件给了完整加法表。
-
曲线上的点:O 加 (3, 2)、(3, 9)、(5, 1)、(5, 10)、(6, 5)、(6, 6)、(8, 0),共 8 个元素。
-
8 不是素数,阶可以是 1、2、4、8 中任何一个。
-
逐个点一直加自己,记下第几步回到 O。
-
只有横坐标是 3 和 5 的四个点阶为 8,它们是生成元。
-
(8, 0) 的纵坐标是 0,它就是自己的逆元,加自己一次就得 O,阶为 2。
怎么判断
一个点 P 是不是生成元:
- 先数出群的大小 N(含 O)
- N 是素数:每个非 O 点都是生成元
- N 不是素数:算 P 的阶,阶等于 N 才是生成元
意思是:不用把倍数全部算完,只要看 P 是否在 N 之前就回到了 O。阶一定是 N 的因数,只需检查这些因数。
纵坐标为 0 的点阶一定是 2。这对应上一页倍点公式要求 y₁ ≠ 0 的那一句。
常见误解
以为任何曲线上任取一点都是生成元
只在群的大小是素数时成立。这条 8 元曲线的群里 (6, 5) 阶为 4,(8, 0) 阶为 2,都不是生成元。
把「群的大小」当成 p
群的大小是点数加 O,和 p 不是一回事。模 11 的两条曲线,一条 13 个元素,一条 8 个。
试一下
在 y² = x³ + x + 6 (mod 11) 上,(3, 5) 是生成元吗?它的阶是多少?
群有 13 个元素,13 是素数,(3, 5) 不是 O,所以阶是 13,是生成元。查表 (3, 5) = 8α。
把它们串起来
模逆把除法变成乘法,平方表让我们能判断哪些 x 有点。有了这两样,就能列出曲线上的全部点。点加法照搬上一页公式,只是每一步取余,于是能算出 α 的所有倍数。点的阶告诉我们哪个点能当基点。
整条线可以压成一张表:
| 步骤 | 用到的工具 | 在 mod 11 例子里的结果 |
|---|---|---|
| 查曲线能不能用 | 判别式 | 976 ≡ 8,可以用 |
| 列点 | 平方表 | 12 个点加 O |
| 算倍数 | 公式 + 模逆 | 2α = (5, 2),3α = (8, 3) |
| 选基点 | 阶和群大小 | 13 是素数,任意非 O 点都行 |
下一页把 13 换成一个 256 位的数。数一大,「已知 kα 求 k」就从翻表变成了难题,椭圆曲线密码就建立在这上面。
课件里的坑
- [适用条件] p.20「任取一个非 O 的点都是生成元」只对群大小是素数时成立,p.22 的 8 元群就是反例。
- [漏 O] p.18 的表只列了 12 个点,O 要自己加上,群里一共 13 个元素。
- [补算] p.25 图上画出了 R 的位置,但没有写出坐标。按公式补算是 (86, 81)。
- [读图提醒] p.25 的「直线」在格子里折成好几段平行线,这是模 127 绕回来的结果,不是画错了。
- [条件] p.17 要求 p > 3:公式里有 2y₁ 和 3x₁²,模 2、模 3 时 2 或 3 本身是 0,不能求逆。
课后 10 分钟:考点复习
这 10 分钟怎么用:先默写模 11 的平方表;然后合上页面,把 p.18 的点表从头列一遍,再把 α 表从 2α 算到 6α,后半张用对称规律补齐;最后做变式题。
必背
- 模 p 曲线:p > 3 素数,4a³ + 27b² ≢ 0 (mod p),公式里的除法换成乘模逆
- 列点:逐个 x 算右边,是平方剩余就贡献两个点,最后加上 O
- y² = x³ + x + 6 (mod 11) 有 13 个点(含 O),α = (2, 7) 是生成元
- 2α = (5, 2),3α = (8, 3),13α = O
- kα 和 (13 − k)α 横坐标相同、纵坐标相加为 11,互为逆元
- 群的大小是素数时每个非 O 点都是生成元;y² = x³ + 10x + 2 (mod 11) 有 8 个元素,(8, 0) 阶为 2
课件例题
例 1(课件 p.18):列出 y² = x³ + x + 6 (mod 11) 的所有点
提示
x 从 0 到 10 逐个算右边,对照平方剩余 {1, 3, 4, 5, 9}。
解答
右边依次是 6, 8, 5, 3, 8, 4, 8, 4, 9, 7, 4。是平方剩余的 x 有 2, 3, 5, 7, 8, 10,得到 (2, 4)、(2, 7)、(3, 5)、(3, 6)、(5, 2)、(5, 9)、(7, 2)、(7, 9)、(8, 3)、(8, 8)、(10, 2)、(10, 9),再加 O,共 13 个。
例 2(课件 p.21):α 的倍数表
提示
2α 用倍点公式,其余用 kα = (k − 1)α + α;后半张用 kα 和 (13 − k)α 的对称关系。
解答
1α 到 6α:(2, 7)、(5, 2)、(8, 3)、(10, 2)、(3, 6)、(7, 9)。7α 到 12α 由对称得到:(7, 2)、(3, 5)、(10, 9)、(8, 8)、(5, 9)、(2, 4)。13α = O。
例 3(课件 p.22):y² = x³ + 10x + 2 (mod 11) 中各点的阶
提示
群有 8 个元素,阶只能是 1、2、4、8。
解答
(3, 2)、(3, 9)、(5, 1)、(5, 10) 阶为 8,是生成元;(6, 5)、(6, 6) 阶为 4;(8, 0) 阶为 2,O 阶为 1。
例 4(课件 p.25):y² = x³ − x + 3 (mod 127) 上 (16, 20) + (41, 120)
提示
斜率是 100/25,这一题恰好能整除。
解答
λ = 100/25 = 4。x₃ = 16 − 16 − 41 = −41 ≡ 86。y₃ = 4 × (16 − 86) − 20 = −300 ≡ 81。P + Q = (86, 81),与图上 R 的位置相符;课件没写坐标,这是补算。
例 5(课件 p.22,课堂批注):在 y² = x³ + 10x + 2 (mod 11) 上,从 P = (3, 2) 出发写出 2P 到 8P
提示
课堂上讲师直接用 p.22 的加法表:P + P 查 (3, 2) 那一行、(3, 2) 那一列;之后每次拿上一个结果所在的列和 P 那一行相交。
解答
2P = (6, 6),3P = (5, 10),4P = (8, 0),5P = (5, 1),6P = (6, 5),7P = (3, 9),8P = O。讲师把这串标在加法表的列头上,并在表旁写 8,表示群一共 8 个元素,(3, 2) 走满 8 步才回到 O,所以它是生成元。7P = (3, 9) 和 P 横坐标相同、纵坐标相加为 11,正好是 P 的逆元。这串结果用点加法公式逐个验算过。
例 6(课件 p.13,课堂批注):在 y² = x³ + x + 6 (mod 11) 上,α = (2, 7),先平方再取模算 2α 的横坐标
提示
课堂上讲师没有先把 λ 化简,而是把 λ² 写成一个分数,分子分母各自取模,再乘分母的逆元。
解答
x₂ = λ² − 2x₁ = (13/14)² − 4 = 169/196 − 4。169 mod 11 = 4,196 mod 11 = 9,9⁻¹ ≡ 5(5 × 9 = 45 ≡ 1),所以 169/196 ≡ 4 × 5 = 20 ≡ 9,x₂ = 9 − 4 = 5。和第 3 个概念里先算 λ ≡ 8、再算 64 − 4 = 60 ≡ 5 的结果一致。两条路都对,分数先约到模 11 以内再求逆,数字更小、不容易算错。
完整例题
题面(课件 p.21):曲线 y² = x³ + x + 6 (mod 11),α = (2, 7),用公式算出 2α 和 3α。
约定:所有运算模 11;负数加 11 变正;分数先化简再乘模逆。
解法:
- 2α 是倍点,a = 1:λ = (3 × 4 + 1)/(2 × 7) = 13/14。
- 13 ≡ 2,14 ≡ 3,λ = 2 × 3⁻¹ = 2 × 4 = 8。
- x = 8² − 2 × 2 = 64 − 4 = 60 = 55 + 5,所以 x = 5。
- y = 8 × (2 − 5) − 7 = −24 − 7 = −31 = −33 + 2,所以 y = 2。2α = (5, 2)。
- 3α = 2α + α,取 P = (5, 2)、Q = (2, 7):λ = (7 − 2)/(2 − 5) = 5/(−3)。
- −3 ≡ 8,8⁻¹ = 7(8 × 7 = 56 = 55 + 1),λ = 5 × 7 = 35 = 33 + 2,所以 λ = 2。
- x = 2² − 5 − 2 = −3 ≡ 8;y = 2 × (5 − 8) − 2 = −8 ≡ 3。3α = (8, 3)。
- 核对 (8, 3):右边 512 + 8 + 6 = 526 = 517 + 9,左边 3² = 9,在曲线上。
要点:2α 用切线斜率、3α 用两点斜率;每个分母都要先取余再求逆;结果代回方程。
答题格式:每个点写三行 λ、x、y,每行末尾写「≡ 结果 (mod 11)」,最后一行验证。
变式题(先自己做)
(1) 改编自课件 p.21:β = (3, 5),算 2β,并用 α 表说明结果为什么对。 (2) 改编自课件 p.18:在 y² = x³ + x + 6 (mod 11) 上,x = 9 有没有点? (3) 改编自课件 p.22:在 y² = x³ + 10x + 2 (mod 11) 上,(8, 0) + (8, 0) 等于什么?
提示
(1) 2y₁ = 10,10⁻¹ = 10。(2) 算右边查平方表。(3) 纵坐标为 0。
判分点与答案(非官方评分标准)
判分点:① 求出正确的模逆;② 每一步取余;③ (1) 能和 α 表对照。
(1) λ = (3 × 9 + 1)/(2 × 5) = 28/10 ≡ 6 × 10⁻¹ = 6 × 10 = 60 ≡ 5。x = 25 − 6 = 19 ≡ 8。y = 5 × (3 − 8) − 5 = −30 ≡ 3。2β = (8, 3)。查表 β = 8α,2β = 16α = 13α + 3α = 3α = (8, 3),一致。
(2) 右边 729 + 9 + 6 = 744 = 737 + 7,7 不是平方剩余,没有点。
(3) (8, 0) 的逆元是 (8, −0) = (8, 0),它就是自己的逆元,(8, 0) + (8, 0) = O。
闪卡自测
1. 模 p 曲线对 p 有什么要求?
p > 3 且是素数;判别式改成模 p 下不为 0(p.17)。
2. 模 p 下怎么做除法?
乘以分母的模逆,模逆用扩展欧几里得算法求(p.17)。
3. 模 11 的平方剩余有哪些?
1、3、4、5、9 五个(p.18)。
4. y² = x³ + x + 6 (mod 11) 一共几个点?
12 个仿射点加 O,共 13 个(p.18、p.20)。
5. 这条曲线为什么任取非 O 点都是生成元?
群大小 13 是素数,非 O 点的阶只能是 13(p.20)。
6. 2α 和 3α 各是多少?
2α = (5, 2),3α = (8, 3)(p.21)。
7. 怎样快速写出 α 表的后半张?
kα 和 (13 − k)α 横坐标相同、纵坐标相加为 11(p.21)。
8. 模 p 曲线的点集关于哪条线对称?
y = p/2:(x, y) 在曲线上,(x, p − y) 也在(p.24)。
9. y² = x³ + 10x + 2 (mod 11) 里哪个点阶为 2?
(8, 0),纵坐标为 0,自己就是自己的逆元(p.22)。
下一讲
从小群走到 256 位的大群:已知 kP 求 k 变成难题,比特币用 secp256k1 曲线,两个人可以靠交换点算出同一个密钥。见 L08b。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。