公钥算法的基本数论知识

type

status

包含内容

欧几里得算法、扩展的欧几里得算法、

欧拉函数、费马小定理、欧拉定理 http://www.huangjihao.com/index.php/archives/625

一、欧几里得算法（Euclidean Algorithm）

1、简介

欧几里德算法又称辗转相除法，是指用于计算两个正整数 a，b 的最大公约数。应用领域有数学和计算机两个方面。

计算公式 𝑔𝑐𝑑(𝑎,𝑏)=𝑔𝑐𝑑(𝑏,𝑎𝑚𝑜𝑑𝑏)

二、例子

，计算它们的最大公约数

三、代码实现

Python实现：

C语言实现：

二、扩展的欧几里得算法（Extended Euclidean algorithm）

1、简介

扩展的欧几里得算法是欧几里得算法的一个扩展。

通过扩展的欧几里得算法，我们不仅可以求出 𝑎 和 𝑏 的最大公约数，还可用找到整数 𝑥 和 𝑦,使得 𝑔𝑐𝑑(𝑎,𝑏)=𝑎𝑥+𝑏𝑦

2、原理

有两个数 𝑎,𝑏，对它们进行辗转相除法，可得它们的最大公约数。

此时欧几里得算法已经递归到了终点，𝑔𝑐𝑑(𝑎,𝑏)中的 𝑏 此时为 0。

也就是

此时的 𝑥=1,𝑦=0

那么我们可以反推上去，求得要解的 𝑥 和 𝑦

3、代码实现

Python实现：

三、欧拉函数

1、定义

ℤ𝑚 内与 𝑚 互素的整数的个数可以表示为 𝜙(𝑚)

2、例子

假设 𝑚=6m=6 对应的集合为 ℤ6=0,1,2,3,4,5

𝑔𝑐𝑑(0,6)=6

𝑔𝑐𝑑(1,6)=1

𝑔𝑐𝑑(2,6)=2

𝑔𝑐𝑑(3,6)=3

𝑔𝑐𝑑(4,6)=2

𝑔𝑐𝑑(5,6)=1

该集合有两个与 6 互素的数字 (1, 6)，所以欧拉函数的值为 2，即：𝜙(6)=2

四、费马小定理

1、定理

假设 𝑎 为一个整数，𝑝 为一个素数，则

2、推广

对有限域 𝐺𝐹(𝑝)内所有整数元素 𝑎 而言，此定理始终成立，此定理也可表示为以下形式：

这种形式在密码学中非常有用，其中一个应用就是计算有限域内某个元素的逆元。

此等式可写为

我们可以得到反转整数 𝑎 模一个素数的方法

*仅在 𝑝 为素数时有效

3、例子

假设，计算的逆元

解：

验证：

五、欧拉定理

1、定理

假设 𝑎 和 𝑚都是整数，且 𝑔𝑐𝑑(𝑎,𝑚)=1 ,则有

2、例子

假设 𝑚=12,𝑎=5 。首先计算 𝑚 的欧拉函数：

验证：

3、结论

很显然，费马小定理是欧拉定理的一个特例。

如果 𝑝 为一个素数，则成立。

如果将这个值用于欧拉定理，则