费马小定理和素数在密码学的应用

陈政培

【摘要】素数一直以来都是数学界研究的重要课题，而素数的正确利用可以为密码学提供有效的工具。本文将要介绍获取并检验素数的方法，以及著名的RSA密码的原理。

【关键词】求模运算  RSA算法  米勒拉宾算法  密码学

【中图分类号】G642                              【文献标识码】A      【文章编号】2095-3089（2016）11-0199-02

公元前在古希腊就产生了早期的算术，直到20世纪初才开始使用数论这个词汇。而从早期到中期的这段时间数论却几乎没有什么发展，直到19世纪才由费马、梅森、欧拉、高斯、黎曼、希尔伯特等人发展起来。而且主要内容是寻找素数通项公式，由初等数论向解析数论和代数数论转变，但也产生很多无法解决的猜想。20世纪有些猜想得以解决，但现在仍然有很多结论是以黎曼猜想一类未能被完全证明的猜想为理论基础的，也就是说假使这些猜想是正确的很多理论也会随之正确并有可能上升为定理，一旦猜想是错误的很多理论也会随之覆灭。目前解决大多数猜想的瓶颈就是素数通项公式，有这样一个说法“如果找到一个素数通项公式，一些困难问题就可以由解析数论转回到初等数论范围”，可见，素数在当今还有很大的研究空间，尽管我们无法确定素数通项公式是否存在。而我想就当前日益发展的科技领域谈谈数论中素数的关键地位。

在这个科技化时代，计算机的地位不断上升，人们对计算机的诉求也不断增大，可能作为一个普通的程序员对于计算机内部的数据处理和优化没有太大的需求。而想要使计算机变得更加强大性能更加优异，除了在硬件方面的进步，在优化算法方面，数论方面的知识有着广泛的应用。例如在计算机算术、计算机设计、计算机理论、计算机复杂度等。而这之后，就会有大量的信息在网络世界中流通，而这之中不乏一些机密信息，信息安全就显得日益重要，密码学也就应运而生。20世纪中后期就产生了一种RSA码，这种神奇的密码正是利用了素数成为至今仍有实用价值的密码。

随着人们慢慢注意到素数的特殊性，人们对这种特殊数字的研究也更加深入，素数在密码学的作用也变得越来越大。

一、素数测试

如果用最普通的方法获得素数，无非就是随机获得一个数，然后对其进行素性测试。素数的定义就是除了1和它本身以外没有其它的因子。假定该数字为p。

用简单的计算机语言描述就是：

for （int i=1;i<p;++i）

if（p%i==0） continue;  //p≡0（mod i）即p能被i整除

则p不是素数。

但是这样的方法复杂度高达O（n）。如果加以优化，只需要试除到：

for （int i=1;i<sqrt（p）;++i）

if（p%i==0） continue;  //p≡0（mod i）即p能被i整除

这样复杂度就降到了O（sqrt（n））。

但是如果采用了米勒拉宾素性检测法，计算将更加简单。

数学原理如下：

若p为素数，a为整数，且a、p互质。

则有ap-1≡1（mod p）

其等价形式为：      ap≡a（mod p）

证明如下：          令ap-1=k×p+1

则ap=（k×p+1）*a

也即 ap≡a（mod p）

引理：若p为素数（p>2），

如果 x2 ≡1 （mod p） 且x既不是1也不是p-1，则称x为“1模p的非平凡平方根”

欲证明素数没有满足模p余1的非平凡平方根存在。

证明：假设x是一个模p余1的非平凡平方根，则有：

x2≡1（mod p）

（x+1）（x-1）≡0（mod p）

因为x是非平凡的，就有（x+1）与（x-1）和x互质，就是说（x+1）和（x-1）都不能被p整除，因此（x+1）（x-1）不能被p整除，矛盾。证毕

素数没有满足模p余1的非平凡平方根。

即如果一个数模p余1下有非平凡平方根，则n必为合数。

由该引理可知，若存在x2≡1（mod p），则p必为合数。

利用以上这些性质，产生了著名的米勒-拉宾素性检测算法：

定义

x02≡1（mod n）

x12≡1（mod n）

…

xtt-12≡1（mod n）

xi是满足1<xi<n-1的随机数，在这一计算过程中，如果有任意一个xi≡1（mod n），根据引理，则n必为合数。

二、RSA码

RSA码的发明就是对素数实际运用的例子。由欧几里得证明的算数基本定理可知任何一个自然数都可以分解为素数的乘积。但是将一个大整数分解只能用较小的素数依次尝试，这种方法无疑是很耗时的。大可在一段固定的时间就更换一次，这样的密码策略堪称无懈可击。

接下来有N、a、X、p、q，其获得过程如下：

1.任意选取素数p、q，N=p×q。

2.中间量r=（p-1）×（q-1）。

3.选取a和X两个互质的数，使之满足aX≡1（mod r）。

4.彻底销毁p、q，公开N和a，将X作为解密关键。

小明想把数字A（A要小于N）传送给小芳，他并不是直接把A发出去因为这样有可能会被其他人截获，于是我将A连续乘a次，再除以N，将余数发给小芳。小芳手里有一个小明都不知道的数字X，她将余数连乘X次，然后除以N，得到的余数就是A。

即小明需要执行的程序是：

temp=pow（A，a）; temp=temp%N; //temp是一个中间量

然后将temp发给小芳，小芳需要执行的程序是：

temp=pow（temp，X）; B=temp%N;

答案B就是当时小明实际想表达的A。

只要素数p、q足够大，N也就很大，a和X的推导过程都是由p和q决定的，只要我销毁p、q，破密的人则需要对N进行整数分解，那将是一个非常庞大的计算量。而且只要N足够大，可以表达的A也就非常大。

这种加密方式其实是公开了打乱一个特定信息的方式，任何人都可以用我公开的方法加密信息，但是由于计算量太大，最终能够整理混乱的信息解出最终答案的人只有我自己。可是有人会说利用现有的费马小定理加上概率测试素数法，在一个较短的可以接受的时间内是可以算出几十位数的分解结果的。即便是一百多位的数，利用现在的网络技术无数台电脑通过交流信息将这个庞大的计算任务细分化，也就是云计算的方式，也是可以解决的。但是试想现在已经计算出的素数位数早已上千位，两个千位级别的素数相乘之后得到的数字恐怕计算机技术有再大的突破也是难以匹敌的。

综上所述RSA码成功的秘诀就是能够获得很大的素数，米勒算法就是一个获得素数的不错算法。将两者结合起来就形成了著名的RSA密码。

参考文献：

[1]张尔光.正整数的方幂的方阵与费马定理——费马定理不成立的必要条件[J].数学学习与研究，2012.12.

[2]袁树雄，韩凤英.密码学基础研究[J].科技资讯，2008.5.

[3]张丽媛.RSA密码算法的研究与实现[D].山东科技大学，2005.5.