循环群模运算中逆元的计算方法
循环群模运算中逆元的计算方法
在密码学和信息安全领域，循环群模运算中的逆元计算是一个基础且重要的概念。本文将从群论的基本概念出发，详细介绍循环群、环、有限域等相关数学结构，并重点讲解扩展欧几里得算法和费马小定理在求解逆元中的应用。
一、算数模复合
假设N = p ⋅ q，其中 p 和 q 是质数 (prime)。
Z_N = {0, 1, 2, ..., N-1};(Z_N)^* = {invertible\ elements\ in\ Z_N}
定理：
Euler 定理：
二、群 循环群
1. 群 (Group)
群是一种代数结构，由一个集合和一个二元运算组成，满足以下条件 (下面默认为 乘法群)：
- 封闭性：对于所有 a, b 在群中，a⋅b 也在群中。
- 结合律：对于所有 a, b, c 在群中，(a⋅b)⋅c=a⋅(b⋅c)。
- 单位元：存在一个元素e在群中，对于所有 a 在群中，a⋅e = e⋅a = a。
- 逆元：在群中，对于的每个元素 a，存在一个元素b使得a⋅b = b⋅a = e，其中 e 是单位元。 如果运算满足交换律，群可以是阿贝尔群 (Abelian Group)。
2. 环 (Ring)
环是代数中的一个基本概念，它是一个集合，配备了两种运算：加法和乘法，满足以下性质：
- 加法和乘法的封闭性。
- 加法和乘法的结合律。
- 存在加法单位元(通常为0) 和乘法单位元(通常为1)。
- 具有加法的交换律。
- 每个元素都有 加法逆元。 环可以没有 乘法逆元，或者只有部分元素有 乘法逆元。
3. 循环群 (Cyclic Group)
循环群是一种特殊的群，它可以由单个元素生成。如果存在一个元素 g在群 G 中，使得群 G 中的每个元素都可以表示为 g 的幂，那么G 就是循环的。循环群可以是有限的或无限的，并且可以是阿贝尔群。
4. 多项式环 (Polynomial Ring)
多项式环是一个环，其中的元素是多项式，系数来自某个环 (通常是整数环或有理数环)。例如，Z[x]表示所有系数为整数的多项式构成的环。
多项式环中的运算是多项式的加法和乘法，它们遵循分配律和结合律。
5. 有限域 (Finite Field)
有限域，也称为伽罗瓦域 (Galois Field)，是一个具有有限个元素的域。域是一种特殊的环，其中每个非零元素 都有 乘法逆元。有限域在密码学中非常重要，因为它们提供了一个在其中可以进行代数运算的封闭系统。
6. 椭圆曲线 (Elliptic Curve)
椭圆曲线是密码学中的另一种群结构，它由满足特定方程的 点组成。椭圆曲线群在密码学中的应用包括椭圆曲线密码体系 (ECC)，它提供了与 RSA 相当的 安全性，但使用的密钥尺寸 更小。
三、求逆元
在密码学中，求逆元十分常见，尤其是在处理模运算的时候。
逆元的存在性取决于两个数是否互质，即它们的最大公约数 (GCD) 是否为 1。以下是几种求逆元的方法：
1. 扩展欧几里得算法
1.1 算法概述
这是最常用的方法，用于找到整数 a 和 b 的最大公约数，并找到整数 x 和 y使得：
a ⋅ x + b ⋅ y = g c d ( a , b )
如果gcd(a, b) = 1，则x 是 a 模 b 的逆元。
输入是 a, b (a 要小于 b)，输出是 x。
1.2 步骤
- 初始化
r_0 = a, r_1 = b, x_0 = 1, x_1 = 0, y_0 = 0, y_1 = 1
或者
r_0 = b, r_1 = a, x_0 = 0, x_1 = 1, y_0 = 1, y_1 = 0
这里的关键就在于，要求a ⋅ x_0 + b ⋅ y_0 = r_0 , a ⋅ x_1 + b ⋅ y_1 = r_1 成立。下面以前一种情况为例子。
- 迭代 (i 从 2 开始)
当r_{i-1}>0时，计算q_i = \lfloor \frac{r_{i-2}}{r_{i-1}} \rfloor，然后更新：
- r_i = r_{i-2} - q_i \cdot r_{i-1}
- x_i = x_{i-2} - q_i \cdot x_{i-1}
- y_i = y_{i-2} - q_i \cdot y_{i-1}
- 当r_i = 0时，x_{i-1} 就是a 模 b 的逆元。
1.3 示例
现在假设，我们要求3 在 mod 11 下的逆元。
- 问题转化：
首先，要求3在mod 11下的逆元，也就是要找到一个整数x，使得：
3 ⋅ x ≡ 1\ (mod\ 11)
这意味着，我们需要找到x和y，使得：
3 ⋅ x + 11 ⋅ y = 1
此时问题便转化为了上面的标准形式
- 初始化：
r_0 = 3\
r_1 = 11\
x_0 = 1\
x_1 = 0\
y_0 = 0\
y_1 = 1
- 第一次迭代：
首先判断r_1 > 0成立，然后计算：
q_2 = \lfloor \frac{r_0}{r_1} \rfloor = \lfloor \frac{3}{11} \rfloor = 0
更新：
r_2 = 3 - 0 * 11 = 3\
x_2 = 1 - 0 * 0 = 1\
y_2 = 0 - 0 * 1 = 0
- 第二次迭代：
首先判断r_2 > 0成立，然后计算：
q_3 = \lfloor \frac{r_1}{r_2} \rfloor = \lfloor \frac{11}{3} \rfloor = 3
更新：
r_3 = 11 - 3 * 3 = 2\
x_3 = 0 - 3 * 1 = -3\
y_2 = 1 - 3 * 0 = 1
- 第三次迭代：
首先判断r_3 > 0成立，然后计算：
q_4 = \lfloor \frac{r_2}{r_3} \rfloor = \lfloor \frac{3}{2} \rfloor = 1
更新：
r_4 = 3 - 1 * 2 = 1\
x_4 = 1 - 1 \cdot (-3) = 4\
t_4 = 0 - 1 \cdot 1 = -1
- 第四次迭代：
首先判断r_4 > 0成立，然后计算：
q_5 = \lfloor \frac{r_3}{r_4} \rfloor = \lfloor \frac{2}{1} \rfloor = 2
更新：
r_5 = 2 - 1 * 2 = 0
此时，可以发现，r_5 = 0，满足结束的条件了。于是乎得到 3 在 mod 11 的时候，逆元是x_3 = 4。
2. 费马小定理
如果 a 和 N 互质，且 N 是质数，费马小定理指出：
a^{n-1} \equiv 1\ (mod\ N)
因此，a 模 b 的逆元是a^{n-2}\ (mod\ n)。