本章涉及知识点

1、素数的定义

2、寻找素数算法—短除法

3、寻找素数算法—筛选法

4、互质关系

5、欧拉函数的证明

6、欧拉定理

7、费马小定理

8、模反元素

9、欧几里得算法—求最大公约数

10、贝祖定理

11、欧几里得扩展算法—求二元一次方程的解

12、大整数快速幂算法

13、大整数快速幂取模算法

14、总结

一、素数的定义

质数又称素数，指在一个大于1的自然数中，除了1和本身之外，无法被其他自然数整除的数

素数具有下列独特的性质：

（1）素数p的因子有且只有两个：1和p

（2）素数一定是奇数

（3）任意一个大于1的正整数N，一定可以质因式分解为它的有限个质因子之积

（4）素数的个数是无限的

（5）所有大于10的素数中，其个位数只能是1,3,7,9其中之一

（6）一个充分大的偶数一定可以写成：一个素数加上一个最多由2个质因子所组成的合成数

如果将素数p表示成极坐标方程

素数p的极坐标方程

我们将第500到第5000的素数画在笛卡尔坐标系来观察其分布：

素数螺旋

可以看到素数的分布呈螺旋形状，这种现象又叫质数螺旋

几百年之间，无数世界顶级的数学家，研究一生始终无法精确的证明素数的表达式以及其分布的规律

二、寻找素数算法—短除法

问题定义：在给定范围n之内，找到所有素数

（1）方法一：

最直接的方法就是从定义出发，对于任意整数p，用[2，p-1]去整除p，如果发现p可以被整除，p就不是素数

显然，这个方法的效率简直低的让人难以接受，优化空间非常大

（2）方法二：

显然偶数不是素数，对于任意奇数p，用[3，5，...，p-2]去整除p，如果发现p可以被整除，p就不是素数

这个方法的效率稍微高了一些，但是其本质和方法一没有任何区别，只是整除系数范围缩小到奇数

（3）方法三：

利用质因式分解的思想，对于任意奇数p，用小于p的素数去整除p，如果发现p可以被整除，p就不是素数

这个方法的计算效率又提高了一些，将奇数级别的除数缩小到质数范围

（4）方法四：

利用平方根条件，对于任意奇数p，用小于p的平方根的素数去整除p，如果发现p可以被整除，p就不是素数

这个方法将素数级别的除数又缩小到不大于其平方根的范围，我们称之为短除法

我们用python实现短除算法，并测试寻找在[2，2^22]范围内所有的素数的算法效率

短除算法

寻找结果

从短除算法寻找结果中，可以看到该算法花费了13秒，找到295947个素数

三、寻找素数算法—筛选法

除了上述的短除算法，是否存在更加高效的算法来寻找素数？

的确存在一个非常高效的算法—筛选法，其设计思想是：

（1）将n个数字全部放进数组，并都置为肯定状态

（2）将数组下标是偶数的数字全部置为否定状态

（3）依次遍历数组长度的平方根个数字

（4）如果当前数字处于被肯定的状态，则将其倍数的数字状态置为否定

我们用python实现筛选算法，并测试寻找在[2，2^22]范围内所有的素数的算法效率

筛选算法

寻找结果

从筛选算法寻找结果中，可以看到该算法只花费了1.16秒，就找到295947个素数

至此我们可以总结出比较上述找寻素数的两种算法

（1）短除算法：使用了严进宽出的思想，对每个数字的判断非常严格，保证每次找到的数字都是素数，时间复杂度较高

（2）筛选算法：使用了宽进严出的思想，一步步筛选（否定），最后保留下来的数字才是素数，利用空间换取时间来大大降低了时间复杂度

四、互质关系

公因数只有1的两个数字，称为互质关系

互质具有下列独特的性质：

（1）任意两个素数一定是互质关系

（2）如果一个数是素数，另一个数字不是它的倍数，则二者互质

（3）较大的数是素数，则二者互质

（4）相邻的两个自然数一定互质

（5）相邻的两个奇数一定互质

（6）1和任意数互质

五、欧拉函数的证明

问题的提出：

给定任意正整数n，问在小于等于n的正整数之中，有多少个数字与n构成互质关系？

我们定义欧拉函数φ(n)来表示这个值，则分析讨论φ(n)可能存在的情况

（1）当n等于1的情况：

则根据互质的性质6可以得到

n=1的情况

（2）当n等于素数p的情况：

则n以下的数字和n都互质

n=p的情况

（3）当n等于素数的某一个次方，即n = p^k的情况：

则小于等于p^k且与p^k不互质的个数有

小于等于p^k且与p^k不互质的个数

则φ(n) = （p^k个数字） -  （小于等于p^k且与p^k不互质的个数），即

n=p^k的情况

（4）当n等于两个素数的乘积，即n=p*q（p和q互质）的情况：

则φ(n) =φ(pq)满足乘法分配律，即 

n=p*q的情况

（5）当n等于任意大于1的正整数的情况：

由素数的性质3（质因数分解）可以得到

正整数n的质因数分解

其中p1、p2...pr都是n的质因数

则根据上述(3)和(4)的分析结果，可以推导出

n等于任意大于1的正整数的情况

综上分析，我们得到欧拉函数的通用计算方式为

欧拉函数的通用计算方式

六、欧拉定理

欧拉定理是解决同余的性质，其定义为：

如果p和q为正整数，且pq互质，则

欧拉定理

显然，我们可以用欧拉函数来判断两个正整数是否互质

七、费马小定理

费马小定理是欧拉定理的特殊情况，其定义为：

如果p和q为正整数，且pq互质，且q是素数，则q的欧拉函数为

q的欧拉函数

则欧拉定理可以写为

费马小定理

八、模反元素的定义

模反元素指：如果两个正整数p和q互质，那么一定存在一个或多个整数b，使得

模反元素

我们可以通过欧拉函数的定义来证明模反元素的必然存在

明模反元素的必然存在

可以看到p的φ(n) -1次方就是p的一个模反元素

九、欧几里得算法—求最大公约数

问题提出：计算两个正整数a和b的最大公约数？

欧几里得算法，又称辗转相除法，其定义最大公约数满足：

欧几里得算法

下面我们来证明该算法

设a>b>1，则

商和余数的形式

其中k为a除以b的商，r为a对b取模，即

商和余数

设d是a和b的一个公因数，则d可以整除a和b，即

d可以整除a和b

又因为r = a - kb，则

d可以整除r

可以看到d也可以整除r，即

d可以整除r

综上，我们可以证明出

欧几里得算法

十、贝祖定理

贝祖定理是初等数论里提出的一个定理，它的定义为：

如果有两个正整数a和b，则存在若干整数对x，y，使得

贝祖定理

该定理说明：a和b的最大公约数满足a和b的线性组合

其中当gcd(a,b)=1时，则证明a和b都是素数，即

a和b都是素数

十一、欧几里得扩展算法

欧几里得扩展算法是用来求解出贝祖等式ax+by=gcd(a，b)的一个解(x，y)，即求解二元一次线性方程

算法证明：

令

设置参数变量

则c可以表示为商q和余数r的线性形式

c表示为商q和余数r

我们已知线性方程组为

已知线性方程组

将c带入第一个方程，得到

化简1

将d的表达式带入上式，得到

化简2

下面我们将参数表做如下变化

参数表变化

经过上述变化，将参数变化带入化简2，得到

变化1

将参数变化带入线性方程组的第二个方程，得到

变化2

综上所述，可以看到线性方程组经过参数表变化后保持了原线性方程组的正确性

至此，我们总结出欧几里得扩展算法的步骤为：

（1）初始化参数：x' = y = 1，x = y' = 0，c = a，d = b

（2）令q和r表示d除以c得到的商和余数

（3）如果余数r不为0，则进入循环，按照变化参数列表更新参数，返回第(2)步

（4）如果余数r为0，则算法终止，返回x和y即为所求

我们用python实现欧几里得扩展算法，并测试求解：47x + 30y = 1的解？

欧几里得扩展算法

计算结果

可以看到x=-7，y=11，带入到方程计算得-7*47+30*11=1，确实是该二元方程的一组整数解

十二、大整数快速幂算法

如果我们要计算a的11次方，则按照幂运算的定义，需要执行11次乘法

如果将指数11写成二进制，则

快速幂原理

可以看到经过上述变化，计算a的11次方只需要执行3次乘法即可，这就是快速幂算法的原理

快速幂算法步骤为：

（1）将幂指数视为二进制进入循环

（2）判断指数二进制权位是否为奇数，如果为奇数，则累乘结果

（3）每次循环对指数进行左移位运算，以及对底数进行累乘运算

我们用python实现欧几里得扩展算法，并测试求解：12345678^56789

快速幂算法

比较快速幂算法和直接连乘法的效率

比较结果

可以看到，快速幂算法的效率非常高

十三、大整数快速幂取模算法

快速幂取模算法基于下面这个取模等价式子

快速幂取模算法的核心

它的思路和快速幂算法一致，在循环过程加入取模运算即可

我们用python实现欧几里得扩展算法，并测试求解：123456789^987654 % 65537

快速幂取模算法

比较结果

可以看到，加入取模计算后，快速幂取模算法几乎是瞬间完成计算

至此，有了上述数论的基础知识和相应的算法，将这些数学理论和算法串联，我们就可以开始RSA算法的实战

案例代码见：RSA加密解密算法—数论基础