RSA系列之<数论上>
2023-7-17 09:12:0 Author: xz.aliyun.com(查看原文) 阅读量:14 收藏

前言：

在 CTF 的密码题目中，[RSA][https://so.csdn.net/so/search?q=RSA&spm=1001.2101.3001.7020]以其加密算法之多且应用之广泛，所以在比赛中是最常见的题目。学习RSA首先得打好数学基础，并在攻破密码的学习之路上持之以恒。今天我们就来打开 RSA 加密世界的第一扇门 《数论》，这些都是我近一年学习RSA的经验总结，如有不足敬请指正。由于内容较多，分为较简单的上篇和较复杂的下篇。

数论1：素数

定义：一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为素数（质数）；否则称为合数。并存在以下事实：
(1) 如果p是素数，且p | ab (表示 ab 能被 p 整除)，则p | a或 p | b，即 p 至少整除 a 与 b 中的一个。
(2) 每个整数n ≥ 2，均可分解成素数幂之积：若不计因数的顺序，这个分解式是唯一的。其中 k ≥ 1， 是两两互不相同的素数， 是正整数。
(3）素数有无穷多个。

数论2：最大公约数与最小公倍数

最大公约数（Greatest Common Divisor，缩写为GCD）是指两个或多个整数中能够同时整除它们的最大正整数。
最小公倍数（Least Common Multiple，缩写为LCM）是指两个或多个整数中能够同时被它们整除的最小正整数。

数论3：三大数学名词

在这里先介绍一下常见的三大数学名词，其中有关联也有区别。

模反元素（Multiplicative Inverse in Modular Arithmetic）：定义是如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a的“模反元素”。
比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。
欧拉定理可以用来证明模反元素必然存在。可以看到，a的 φ(n)-1 次方，就是a对模数n的模反元素。
$$
(a * b) ≡ 1 (mod n)
$$

用途：

  1. 解决同余方程：模反元素可以用于解决类似 a * x ≡ b (mod n) 的同余方程，其中 a、b 和 n 是已知的整数。如果 a 在模 n 下存在模反元素，那么可以通过乘以该模反元素来解出 x 的值。
  2. 素数测试和因数分解：模反元素也与素数测试和因数分解相关。例如，在费马小定理中，如果一个数 p 是素数，则对于任意不整除 p 的整数 a，a^(p-1) ≡ 1 (mod p)。在这种情况下，模反元素可以用来检测潜在的素数。

逆元（Inverse Element）：逆元是指对于某个二元运算，存在一个元素与给定元素进行运算后得到单位元。逆元存在的运算一般是可逆的。逆元是一个更一般的概念，适用于各种代数结构和数学运算。

乘法逆元（Multiplicative Inverse）：乘法逆元是指对于乘法运算，存在一个元素与给定元素相乘后得到单位元。乘法逆元通常用符号 a⁻¹ 表示。乘法逆元是逆元的一个特例，特指乘法运算下的逆元。
是不是有一点熟悉？这就是倒数啊，从小学到大的倒数，这样说是不是一下子就懂了。但是请记住，这里是特指在乘法运算下的逆元，而在模运算下的，就是模反元素。但也显然我们经常用的就是后者。

区别与联系：

  • 逆元是一个更一般的概念，可以适用于各种代数结构和数学运算。乘法逆元和模反元素是逆元的特殊情况，分别指乘法运算和模运算下的逆元。
  • 乘法逆元和模反元素都是乘法运算的逆元，乘法逆元指乘法运算中某个元素的逆元，而模反元素指模运算中某个整数的逆元。
  • 模反元素通常与同余关系一起讨论，例如在数论和密码学中，用于解决同余方程和加密解密操作。乘法逆元广泛应用于抽象代数和数域理论中的群论。
  • 对于整数的乘法逆元，必须满足整数与模数互质的条件，才能存在模反元素。而在实数和有理数的乘法中，除了零之外的元素都有唯一的乘法逆元。

总结而言，逆元是一个更一般的概念，乘法逆元和模反元素是逆元的特例，分别适用于乘法运算和模运算。乘法逆元和模反元素在不同的数学领域和应用中具有重要的意义和运用。

数论4：同余与模运算

同余（Congruence）是数论中的一个重要概念，它是指两个数在给定的模数下具有相同的余数。

具体来说，对于任意整数a、b和正整数m，如果它们满足 (a - b) 能够被 m 整除，即 (a - b) mod m = 0，那么我们就说 a 和 b 是在模 m 下是同余的，记作 a ≡ b (mod m)。
换句话说，如果两个整数 a 和 b 除以正整数 m 的余数相等，那么我们就说 a 和 b 在模 m 下是同余的。

同余关系具有以下特性：

  1. 自反性：对于任意整数 a，a ≡ a (mod m)。
  2. 对称性：若 a ≡ b (mod m)，则有 b ≡ a (mod m)。
  3. 传递性：若 a ≡ b (mod m) 且 b ≡ c (mod m)，则有 a ≡ c (mod m)。

模运算（Modular arithmetic）是一种特殊的整数运算，它与同余关系密切相关。模运算是在给定模数（一般用正整数m表示）下进行的运算，它的结果是一个非负整数，范围在0到m-1之间。

在模m下进行的运算主要有加法、减法、乘法和取模等。

  1. 加法：a + b ≡ c (mod m)，表示a加上b再对m取模的结果是c。
  2. 减法：a - b ≡ c (mod m)，表示a减去b再对m取模的结果是c。
  3. 乘法：a * b ≡ c (mod m)，表示a乘以b再对m取模的结果是c。
  4. 取模：a mod m，表示a对m取模的余数。

模运算具有一些特性：

  1. 同余关系：如果a ≡ b (mod m)，那么对于任意的模运算（加法、减法、乘法、取模），a与b的结果也是同余的。
  2. 模运算的可分配性和结合性：对于任意的整数a、b、c，以及正整数m，满足以下关系：
    • (a + b) mod m ≡ (a mod m + b mod m) mod m
    • (a - b) mod m ≡ (a mod m - b mod m) mod m
    • (a b) mod m ≡ (a mod m b mod m) mod m
    • (a b c) mod m ≡ (a mod m b mod m c mod m) mod m

模运算在计算中具有重要的作用，特别是在解决循环计数、周期性问题、密码学中的加密算法和校验算法等领域。它能够简化计算、减小数值范围，并且帮助我们发现一些有用的数论性质。

补充：

  1. 在数学上，这两种表示方式的结果是等价的，即 c ≡ m^e (mod n) 和 c ≡ m^e mod n 是等价的。它们都表达了对 m^e 进行取模运算的意思。在实际应用中，选择哪种形式取决于具体的编程语言、上下文和个人偏好。无论是 “c ≡ m^e (mod n)” 还是 “c ≡ m^e mod n”，它们都表示对 m^e 进行取模运算，但在具体的编程上下文中，可能有些微的差别。在使用时，应根据具体的编程语言和上下文进行理解和应用。
  2. 在数学中，“c ≡ m^e (mod n)” 和 “c = m^e (mod n)” 是等价的表达方式。
    c ≡ m^e (mod n)：这个表达式表示 c 和 m^e 在模 n 意义下具有相同的余数。也就是说，它们在模 n 下同余。这强调了同余关系的性质，即它们的差值是 n 的倍数。这种符号 “≡” 更常用于表示同余关系。
    c = m^e (mod n)：这个表达式表示 c 等于 m^e 在模 n 下的值。它表示等号关系，即 c 的值与 m^e 在模 n 下的计算结果相等。这种符号 “=” 更常用于一般的等式关系。
    它们都表示在模 n 意义下 c 等于 m^e 的计算结果。这意味着 c 和 m^e 在模 n 下具有相同的余数，满足同余关系。因此，这两种表示方式并没有本质上的区别，只是符号的不同表达形式。在数论和模运算中，“≡”符号更常用于表示同余关系，而“=”符号则更常用于一般的等式关系。

数论5：欧拉函数

定义： 欧拉函数φ(n)是一个定义在正整数集上得函数，φ(n)的值等于序列0，1，2，…，n-1中与n互素的数的个数。（通常情况下，欧拉函数φ(n)的定义是对大于1的正整数n进行计算，即计算与n互质的正整数的个数。因此，在计算欧拉函数时，一般不考虑0作为参数。对于0，由于它没有定义因数，因此欧拉函数φ(0)是没有意义的。在数论中，常规的定义是将欧拉函数φ(n)限定在正整数范围内，不包括0）

1.关系（互素关系）

我们知道一个大于1的自然数如果只能被1和他本身整除，那么这个数就叫质数（比如1，2，3，5......）。而两个正整数之间除了1以外，再无其他公因子，我们就称这两个数是互质关系（比如1和4，4和3......），这说明，不是质数也能构成互质关系。由互质关系的性值，我们得出如下性质：

  1. 任意两个质数构成互质关系，比如13和61。

  2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。

  3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。

  4. 1和任意一个自然数是都是互质关系，比如1和99。

  5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。

  6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

2.函数

知道了互质关系后那么请问，如果任意给定一个正整数n，请问在小于等于n的正整数之中，有多少个数与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）。计算这个值的方法就是欧拉函数，用φ(n)表示。如果一个个的列举：1，2，3，4，5，6，7，8中只有1，3，5，7与8互质，因此φ(n)=4。那么我们如何列出通用的公式直接求φ(n)呢？接下来我们进一步分析：

①第一种情况：如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。

②第二种情况：如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。（与RSA相呼应）

③第三种情况：如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则 φ(n) = φ(p^k) =p^k - p^(k-1) 比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 - 4 = 4。
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
进一步变形得：
$$
φ(n) = φ(p^k) =p^k - p^(k-1) =p^k * (1-1/p)
$$
由此也能看出（n是质数，则 φ(n)=n-1）是k=1时的特例。

④第四种情况：如果n可以分解成两个互质的整数之积，n = p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)，即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。记住结论就好了。

⑤第五种情况：因为任意一个大于1的正整数，都可以写成一系列质数的积（数论只研究正整数）。
n=p1^k1 p2^k2 ..... pr^kr，由④可得，φ(n) =φ(p1^k1) φ(p2^k2) ..... φ(pr^kr)，由③可得，φ(n) =p1^k1 p2^k2..... pr^kr (1-1/p1) (1-1/p2).... (1-1/pr)，代入化简可得，
$$
φ(n) =n (1-1/p1) (1-1/p2).... (1-1/pr)
$$
举例说明就是：φ(1323) =φ(3^3 7^2) =1323 (1-1/3) * (1-1/7) = 756。
这个就是欧拉函数的一般性公式。因此，想求出一个正整数的欧拉函数首先要进行因数分解，随后带入一般性公式即可求解。

3.用途

密钥生成：
在RSA算法中，首先需要选择两个大素数p和q。根据欧拉函数的性质，如果p和q是素数，那么φ(pq) = (p-1)(q-1)。因为当p和q是素数时，n = pq的所有小于n的正整数都与p和q互质，因此满足条件的数有(p-1)个与p互质，以及(q-1)个与q互质。所以，总共有(p-1)(q-1)个与n互质的正整数。选择满足这个条件的p和q有助于保证RSA算法的安全性。

加密/解密操作：
在RSA算法中，加密和解密操作涉及到对明文或密文进行指数运算。具体来说，加密时使用公钥对明文进行加密，解密时使用私钥对密文进行解密。而私钥和公钥的生成依赖于欧拉函数。

  • 公钥：公钥的选择涉及到欧拉函数φ(n)和一个与φ(n)互质的整数e。公钥包括 (n, e)，其中n=pq是两个大素数的乘积。在选择e的时候，通常会选择一个较小的值，常见选择是使用质数65537。
  • 私钥：私钥的选择依赖于欧拉函数φ(n)和公钥中的指数e。私钥包括 (n, d)，其中d是满足ed ≡ 1 (mod φ(n))的整数。d的计算通常使用扩展欧几里得算法进行求解。

数论6：欧拉定理（欧拉公式）

欧拉定理（Euler’s theorem）是数论中一个重要的定理，它与模运算和指数运算有关。也被称为费马-欧拉定理或欧拉-费马定理。

对于任意正整数a和模m，如果a和m互质，即它们的最大公因数为1，则n的欧拉函数 φ(n) 可以让等式成立：
$$
a^ϕ(n) ≡ 1(modn)
$$
也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。欧拉定理可以大大简化某些运算。

特例：

欧拉定理有一个特殊情况。假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成:
$$
a^(p-1)≡1(mod p )
$$
这就是著名的费马小定理。它是欧拉定理的特例。下面对其详细说明。

数论7：费马小定理

费马小定理：假如 a是一个整数， p 是一个质数，那么 a^p-a 是 p 的倍数，也可以表示为 a^p≡a(mod p)。如果 a 不是 p 的倍数的话，这个定理可以改写成我们常看的形式： a^p−1≡1 (mod p)。

对于正整数a和p，a和p互质，如果有a^(p-1)≡1(mod p ) ，那么称x的最小整数解为a模p的逆元。
$$
a^(p-1)≡1(mod p )
$$
简单来说，费马小定理指出，在给定一个素数p的情况下，对于任意不是p的倍数的整数a，a^(p-1)在模p下与1同余。也就是说，如果a和p互质，那么在模p下，对a进行(p-1)次幂运算，结果与1同余。然而，需要注意的是费马小定理仅对素数成立，当p为合数时该定理不成立。同时，费马小定理只能提供的是一个充分条件而非必要条件，也就是说可能存在一些合数a，满足a^(p-1) ≡ 1 (mod p)，但它们不是p的倍数。这就是费马的最后定理（费马大定理）所指出的问题，费马大定理在RSSA的应用不多，这里放上链接，有兴趣的自行查看。

证明：

若a是整数,p是质数,且gcd(a,p)=1,其中gcd(a,p)表示求a,p的最大公约数，即a,p互质

我们先假设如果a=5,p=7有

1 × 5 = 5 , 5 mod 7 = 5
2 × 5 = 10 , 10 mod 7 = 3
3 × 5 = 15 , 15 mod 7 = 1
4 × 5 = 20 , 20 mod 7 = 6
5 × 5 = 25 , 25 mod 7 = 4
6 × 5 = 30 , 30 mod 7 = 2

欸是不是发现了什么，看起来,余数集合刚好就是{1,2,3,⋯,6}里的元素打乱顺序后的集合。如果a=1的话,计算后的余数集合就是1,2,3,⋯ ,6，顺序都没变。为什么会这样？如果我们把次数增多，变成14，21，28，计算之后会出现什么？它居然又循环了，而且余数出现的顺序也是一样的！范围就是在0~p-1，从5~2，很是让人震惊。事实上，这里是循环群的概念，我们在则会不作过多赘述，有兴趣的可以自行了解。根据我们高中学过的数学归纳法，我们只需要记住这样一个规律。

所以，到这一步我们就知道了在1×a,2×a,3×a,⋯,(p−1)×a,共有(p−1)个数，都分别 mod p ，假设其结果是{r1,r2,r3,⋯,rp−1}，就是{1,2,3,⋯ ,p−1}这个集合的重新排序，记住这些，我们进行下一步。

我们将1×a,2×a,3×a,⋯,(p−1)×a,共(p−1)个数相乘，再用乘积对p求余：
$$
(1×a,2×a,3×a,⋯,(p−1)×a)mod p = (1,2,3,...(p-1))
$$
那么根据乘法交换律和结合律，可以写成：
$$
(1×2×3×....×(p-1)×a^(n-1))mod p = (1×2×3×...×(p-1))
$$
我们令1×2×3×....×(p-1)＝W，那么就有：
$$
(Wa^(p-1))modp=W
$$
很想然W不为零，整个式子除以W：
$$
Wa^(p-1)≡W(modp)➡➡➡a^(p-1)≡1(modp)
$$
就出现了我们的费马小定理： a^p−1≡1 (mod p)，也可以写成 a^p≡a (mod p)，到此证毕！

数论8：欧几里得算法

欧几里得算法（Euclidean algorithm）是一种用于求解两个非负整数最大公约数（Greatest Common Divisor，简称GCD）的算法。该算法基于欧几里得提出的思想，也被认为是最古老的算法之一。

欧几里得算法的基本思想是通过反复使用两个整数的余数计算来求解它们的最大公约数。该算法的步骤如下：

  1. 首先，选取两个非负整数 a 和 b（a ≥ b），其中 a 是被除数，b 是除数。
  2. 用 a 除以 b，并计算出商 q 和余数 r（a = bq + r）。
  3. 如果 r 等于 0，则 b 就是最大公约数。
  4. 如果 r 不等于 0，则将 a 替换为 b，b 替换为 r，然后重复步骤 2 和步骤 3。
  5. 当余数 r 等于 0 时停止计算，此时的 b 就是 a 和 b 的最大公约数。

简单来说，欧几里得算法通过不断地计算两个数的余数，然后将较小的数替换为余数，直至余数为 0，得到的最后一个非零余数的除数就是最大公约数。
几里得算法非常高效，并且能够被扩展用于更复杂的计算，如计算最小公倍数、求解线性同余方程等。
需要注意的是，欧几里得算法要求输入的是非负整数。对于负数，可以先取绝对值再进行计算。

例如，使用欧几里得算法计算出 48 和 18 的最大公约数：
步骤 1：选择 a = 48，b = 18
步骤 2：48 ÷ 18 = 2 余 12
步骤 3：非零余数，继续
步骤 4：将 a 替换为 b，b 替换为 r，即 a = 18，b = 12
步骤 5：18 ÷ 12 = 1 余 6
步骤 6：非零余数，继续
步骤 7：将 a 替换为 b，b 替换为 r，即 a = 12，b = 6
步骤 8：12 ÷ 6 = 2 余 0
步骤 9：零余数，停止计算，最大公约数为 6

因此，48 和 18 的最大公约数为 6。

下面用两种简单的代码对其进行实现：

#递归实现
def euclidean_gcd(a, b):
    if b == 0:
        return a
    else:
        return euclidean_gcd(b, a % b)

#迭代实现
def euclidean_gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

事实上，对于在python中的算法实现，我们往往会使用gmpy2.gcd(a,b) 库和Crypto.Util.number库来精简代码。

用途：

  1. 求两个大素数的最大公约数：RSA算法的安全性依赖于两个大素数之间的乘积难题。为了生成私钥，用户需要选择两个大素数，并计算它们的最大公约数。这一步通常使用欧几里得算法来完成，确保选择的两个素数互质。
  2. 计算模反元素：在RSA算法中，用户需要计算一个数的模反元素。模反元素是指在某个模数下，某个数的乘法逆元。在RSA算法中，模反元素的计算使用了扩展的欧几里得算法（Extended Euclidean Algorithm）来实现。扩展的欧几里得算法不仅可以计算最大公约数，还可以找到一组整数解，使得两个数的线性組合等于它们的最大公约数。

补充：（辗转相除法）

当我们在网上查询欧几里得算法时，往往会提到辗转相除法，这两者有所区别也有所联系。

欧几里得算法是基于递归迭代的思想，通过反复计算两个数的余数，然后将较大的数替换为较小的数，直到余数为 0 时停止计算，得到的最后一个非零余数的除数就是最大公约数。
辗转相除法则是欧几里得算法的一种变种形式，具体步骤如下：

  1. 初始化两个非负整数 a 和 b（a ≥ b），其中 a 是被除数，b 是除数。
  2. 计算两个数的余数 r（a ÷ b = q … r）。
  3. 如果余数 r 等于 0，则说明 b 是最大公约数。
  4. 如果余数 r 不等于 0，则将 a 替换为 b，将 b 替换为 r，并重复步骤 2 和步骤 3。
  5. 当余数 r 等于 0 时停止计算，此时的 b 就是 a 和 b 的最大公约数。

这里可以看出，辗转相除法与欧几里得算法的步骤基本相同，区别在于辗转相除法没有使用商 q，而是直接用被除数除以除数得到余数 r。

两者的本质思想一致，都是通过不断计算两个数的余数来缩小问题规模，直到得到最大公约数。在实际运用中，它们的结果是一致的，但辗转相除法更简化了计算步骤，因此在求解最大公约数时，辗转相除法更常被使用。

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

数论9：拓展欧几里得算法

此算法基于欧几里得算法，在正式介绍该算法前，需要了解一下贝祖等式。

贝祖等式（Bézout’s identity），也称为贝祖定理（Bézout’s lemma），是一个关于整数最大公约数的定理，它描述了两个整数的线性组合与它们的最大公约数的关系。

贝祖等式：对于任意的整数a和b，存在整数x和y，使得ax + by = gcd(a, b)。其中，gcd(a, b)表示整数a和b的最大公约数。
$$
ax + by = gcd(a, b)
$$
贝祖等式的意义在于它给出了一种方法，可以用整数的线性组合来表示它们的最大公约数。具体地说，ax + by的形式中，x和y为整数，可以表示a和b的最大公约数的线性组合。贝祖等式的一个重要应用是在数论中的扩展欧几里得算法中，可以通过递归地求解贝祖等式，从而找到满足等式的整数解x和y，并利用这些解来解决一些数论问题。

总结起来，贝祖等式是关于整数最大公约数的一个重要定理，描述了两个整数的线性组合与它们的最大公约数之间的关系。

基本了解贝祖等式之后，我们再开始介绍拓展欧几里得算法：

拓展欧几里得算法（Extended Euclidean Algorithm）是求解两个整数的最大公约数（GCD）以及求解贝祖等式的一种方法。该算法的名称来自于古希腊数学家欧几里得。

算法描述如下：

假设我们要求解整数a和b的最大公约数，可以使用下面的递归形式：

  1. 如果b等于0，则返回a作为最大公约数。
  2. 否则，用a除以b得到商q和余数r。
  3. 对于a和b的最大公约数，可以递归地通过求解b和r的最大公约数来确定，即gcd(a, b) = gcd(b, r)。
  4. 使用递归的结果，我们可以找到满足贝祖等式的一组整数x和y，即ax + by = gcd(a, b)。

拓展欧几里得算法的主要思想是在递归求解过程中，通过相关性质计算出对应的x和y的值，使得ax + by = gcd(a, b)成立。

同样，该算法也可以用gmpy2 库函数 gcdext()实现，下面是拓展欧几里得算法的伪代码实现：

function extendedEuclidean(a, b):
if b = 0:
return a, 1, 0
else:
d, x, y = extendedEuclidean(b, a mod b)
x, y = y, x - (a // b) * y
return d, x, y

在该算法中，返回的d即为a和b的最大公约数，返回的x和y满足贝祖等式ax + by = d。

请注意，算法中的“//”代表整数除法，而“%”则代表取模运算。

使用拓展欧几里得算法，我们可以求解整数a和b的最大公约数，并找到满足贝祖等式的一组整数解。这在解决一些与数论相关的问题中非常有用。我们用欧几里得算法可以求出最大公约数，而拓展拓展，这二字体现在的就是满足贝祖等式上，我们可以求出gcd（a，b）和x，y，这十分方便。

用途：

当整数a和模数m互质（即它们的最大公约数为1，记作(a, m) = 1）时，可以使用扩展欧几里得算法来计算a的逆元。

回忆一下，逆元是指在模m下，与a相乘后得到1的整数x。数学表示为a * x ≡ 1 (mod m)。

以下是使用扩展欧几里得算法来计算a的逆元的步骤：

  1. 使用扩展欧几里得算法找到整数x和y，使得 ax + my = 1。其中，x和y分别是扩展欧几里得算法中方程 ax + my = gcd(a, m) 的解。
  2. 对上述方程两边同时取模m，得到 ax ≡ 1 (mod m)。这里如果x的值为负数，可以将其转化为对应的正数。

通过上述步骤，我们可以得到a的逆元x，满足ax ≡ 1 (mod m)。这意味着在模m下，a和x互为逆元。

需要注意的是，这里的模m必须是正整数，并且与a互质，才能确保逆元的存在。

在RSA算法中，寻找模的逆元很常见，用于计算私钥指数。通过使用扩展欧几里得算法，可以高效地找到a在模m下的逆元。


文章来源: https://xz.aliyun.com/t/12706
如有侵权请联系:admin#unsafe.sh