一、摘要
大数素性检测一直是数论界、密码学界等经久不衰的研究方向，实现大数素性检测的算法也在不断地被改进。目前已经出现了很多大数素性检测的算法，而Miller-Rabin算法在其中显得十分耀眼。本文调研了常见的大素数判断算法，并详细介绍了Miller-Rabin大素数判断算法的原理，然后结合相关的数论知识，以生成一个512bits的大素数为例，编程实现了该大素数判断算法。
二、引言
i.研究的问题及其背景
素数是除了自身和1以外，没有其他素数因子的自然数。在我们以前的数学学习过程中，我们知道了很多素数。但这些我们认知范围内的素数，无论是在数值还是个数方面，相对于整个素数集，都是十分受限的。自从欧几里得证明了有无穷个素数以后，人们就企图寻找一个可以构造所有素数的公式，寻找判定一个自然数是不是素数的方法。尤其是对于一个数值很大的数，要判断其是否为素数，单靠直觉或者查询相关素数表是远远达不到我们的期望的。而素数的应用十分广泛，地位尤其重要，因此确定一个大数是否为素数是数学发展史上一个无法回避的问题。故而，大素数的检测方法应运而生，并随着时间的推移而快速发展。
素性检测可分为两大类，即确定性素性检测和随机素性检测。前者可给出确定的结果但通常较慢，后者则与之相反。本篇文章主要介绍三种常见的大素数判断算法，并给出Miller-Rabin算法的编程实现。
ii.研究的目的及其意义
素数在密码学中发挥着十分重要的作用。密码学完全是关于数论的，所有整数(0和1除外)都由质数组成，因此在数论中处理质数很多。素数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。
给出两个大素数，很容易就能将它们两个相乘。但是，给出它们的乘积，找出它们的因子就显得不是那么容易了。这就是许多现代密码系统的关键所在。如果能够找到解决整数分解问题的快速方法，几个重要的密码系统将会被攻破，包括RSA公钥算法和Blum Blum Shub随机数发生器。尽管快速分解是攻破这些系统的方法之一，仍然会有其它的不涉及到分解的其它方法。所以情形完全可能变成这样：整数分解问题仍然是非常困难，这些密码系统却是能够很快攻破。有的密码系统则能提供更强的保证：如果这些密码系统被快速破解（即能够以多项式时间复杂度破解），则可以利用破解这些系统的算法来快速地（以多项式时间复杂度）分解整数。换句话说，破解这样的密码系统不会比整数分解更容易。这样的密码系统包括 Rabin密码系统（RSA的一个变体），以及 Blum Blum Shub 随机数发生器。
对一个很大的数进行素性判断，对于解决整数分解问题是有极大的助推作用的，也是一个十分关键的环节。可以说，如果我们能够首先快速准确地解决大数素性检测的问题，那么才会有找到解决整数分解问题的快速方法的可能。因此本次研究Miller-Rabin大素数判断算法的原理及其实现是很有实际意义的。
三、研究方法和研究过程
本次研究，我主要使用了文献研究法、经验总结法和实验研究法。首先通过阅读大量相关的文献，形成对大素数判断算法的科学认识；然后总结出前人研究大素数判断算法的一些宝贵经验，在此基础上编写代码并运行，根据运行结果不断改进程序，最终实现了Miller-Rabin大素数判断算法。
下面是研究的内容和过程：
1.三种大素数判断算法
我调研了三种大素数判断算法，它们分别是：费马（Fermat）素性检验、Miller-Rabin素数测试算法和AKS素数测试。前面两者属于随机素性检测，而AKS属于确定性素性检测。
i.费马（Fermat）素性检验
费马素性检验是一种素数判定法则，利用随机化算法判断一个数是合数还是可能是素数。
费马素性检验的原理如下：
根据费马小定理：如果p是素数，1<=a<=p-1，那么有
。如果我们想知道n是否是素数，我们在中间选取a，看看上面等式是否成立。如果对于数值a等式不成立，那么n是合数。如果有很多的a能够使等式成立，那么我们可以说n可能是素数，或者伪素数。
在我们检验过程中，有可能我们选取的a都能让等式成立，然而n却是合数。这时等式
被称为Fermat liar。如果我们选取满足下面等式的a: 
，那么a也就是对于n的合数判定的Fermat witness。
由于费马小定理的逆定理并不正确，对于卡迈克尔数即满足费马小定理的逆定理但是不为素数的数，虽然卡迈克尔数很少，在1~100000000范围内的整数中，只有255个卡迈克尔数，但是已经使他的效果落后于Miller-Rabin和Solovay-Strassen素性检验。
由于属于随机性算法，故费马素性检验并不是保证完全正确的。在选取底数a时，有二分之一的概率出错，但是可以通过多次选取底数来使出错概率降下期望值。
在重复k次成立的情况下，n为合数的可能性小于1/2k。
ii.AKS素数测试
AKS素数测试是一个决定型素数测试算法 ，由三个来自印度坎普尔理工学院的计算机科学家在2002年8月6日发表于一篇题为素数属于P的论文。这个算法可以在多项式时间之内，决定一个给定整数是素数或者合数。
AKS 素数测试主要是基于以下定理：整数n(≥ 2)是素数，当且仅当
这个同余多项式对所有与n互素的整数a均成立。这个定理是费马小定理的一般化，并且可以简单的使用二项式定理跟二项式系数的这个特征: 
，对任何0<k<n，当且仅当n是素数来证明出此定理。
为了减少计算复杂度，AKS改为使用以下的同余多项式：
这个同余式可以在多项式时间之内检查完毕。这里我们要注意所有的素数必定满足此条件式。然而，有一些合数也会满足这个条件式。有关AKS正确性的证明包含了推导出存在一个够小的r以及一个够小的整数集合A，令如果此同余式对所有A里面的整数都满足，则n必定为素数。
iii.Miller-Rabin素数测试算法
Miller-Rabin素性检验是一种素数判定法则，利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授Gary Lee Miller首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯来大学的Michael O.Rabin教授作出修改，提出了不依赖于该假设的随机化算法。
米勒-拉宾检测依赖以下定理：
如果p是素数，x是小于p的正整数，且x^2 = 1 mod p，则x要么为1，要么为p-1。简单证明：如果x^2 = 1 mod p，则p整除x^2 – 1，即整除(x+1)(x-1)，由于p是素数，所以p要么整除x+1，要么整除x-1，前者则x为p-1，后者则x为1。
素性检测首先利用了因数分解式，将幂次n-1降低为以2为阶的各次幂，再利用中国剩余定理，推出强伪素数的满足条件，在算法优化中，采用模平方算法降低复杂度，这也是该算法的优势之一，大大提高了效率。
具体操作如下所示：
在k次检测通过的情况下，n为合数的概率小于1/4k。相比之下，这样的出错概率遥遥低于费马素性检测。而且需要注意的是，这是个很保守的估计，实际使用的效果要好得多。
2. Miller-Rabin大素数判断算法的实现
有了前面的理论基础，现在我就可以开始进行编程来实现Miller-Rabin大素数判断算法了。
i.首先编写一个python程序来验证Miller-Rabin大素数判断算法
我用python编程实现了Miller-Rabin大素数判断算法，由于此时我无法找到很大的素数，所以只对一些较小的、常见的素数进行判断，这样有利于后续判断大数是否为素数。程序在pycharm中如下所示（完整代码见附录1）：
下面是我每次随机输入一个数，程序对该数是否为素数的判断（prime为素数，composite为合数）：
可以看到，该Miller-Rabin素数判断程序对上述输入的数字进行判断的结果都是正确的。那么这个程序是否能够对很大的素数进行判断呢？目前还没有确定的答案，因为我现在不能找到一个很大的素数作为程序的输入来进行判断，比如找到一个512bits的大数。那么，下一步便是编写生成大素数的程序，我们在该程序运行后得到一个很大的素数后，再把该素数放入上面的Miller-Rabin素数判断程序中，观察判断的结果，从而能够确认Miller-Rabin素数判断程序对很大的数进行素性检测是否有效。
ii.使用GMP库生成随机大素数
通过调研发现，可以直接使用GMP库来生成一个512bits的大素数，在DevC++中的程序如下（p为512bits的大素数，完整代码见附录2）：
运行该程序后，我得到了一个512bits的大素数，其十进制表示如下：
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006083527
然后我将该大素数作为输入，运行上面的Miller-Rabin素数判断程序，结果如下：
可以看到，该程序将输入判定为素数，这与事实是相符的，说明上面的Miller-Rabin素数判断程序在一定程度上的准确率是比较可靠的。
当然，这里使用的是GMP库来生成512bits的大素数，其实用python也能得到大素数，附录3中给出了使用python生成512bits大素数的核心函数。
四、研究结果及其分析
从上面的研究内容可以看到，将Miller-Rabin素性检测算法用于大素数的判断是能够得到较好的结果的。Miller-Rabin素性检测其实就是Fermat算法加入二次探测定理的一种实现，它的理论基础是由Fermat定理引申而来，因此它具备了Fermat检测算法的优势，同时进一步降低了判断的错误率。在运行python程序对较小的数进行素性检测时，得到结果的速度很快，这也是Miller-Rabin素性检测算法的一个优点。在使用GMP库获取512bits的大素数时，耗费的时间会长一点，但当我把512bits的大数作为输入运行Miller-Rabin大素数判断程序时，得到结果的速度依然很快，且结果是正确的。因此，本次编程实现Miller-Rabin大数素性检测取得了一定的成功。
当然，本次研究还有需要改进的地方，比如在获取512bits的大素数的方法上，除了使用GMP这个现有的库来实现，还可以自己编写程序，从更加底层的角度，来得到大素数。对于Miller-Rabin大素数判断程序，因为我查阅的资料有限，精力也有限，所以我认为一定还可以在此程序基础上进行改进，使得判断的准确性更高，即错误率更低。这些都是通过本次研究结果看到的不足，后续我会持续进行研究和改进。
五、结论
在本次研究中，我熟悉了三种常见的大数素性检测的算法，同时理解了大数生成的原理，利用GMP库生成512bits的大素数，使用python语言编写了Miller-Rabin大素数判断算法的程序，将大素数作为输入，运行程序，得到了正确的判断结果。
研究结果说明，Miller-Rabin算法用于大数素性检测的优势很明显：速度快，错误率低；同时，获取大素数的方法不只一种，还可以去探索新的方法，我编写的python程序也有可以改进的地方，通过后续的研究，我相信能够把程序的素数判断错误率降得更低。
通过本次研究，我对素数在密码学中发挥的重要性有了更深刻的理解，对
Miller-Rabin大素数判断算法的原理有了较为熟悉的掌握，在编写程序实现该算法的过程中，我强化了对其的理解，也提高了自己的动手能力，收获颇丰。
六、参考文献
[1] 谢建全.一种实用的大素数快速生成方法[J].信息安全与通信保密.2006,(9).56-58.
[2] 耿海飞,苏锦海.大素数的快速生成研究与实现[J].电脑与信息技术.2005,(2).9-11,32.
[3] 韦萍萍,戎士奎.判定素数的新方法及程序[J].贵州教育学院学报(自然科学).2005,(2).1-3.
[4] 朱文余.AKS算法及关于它的一种改进算法的实现分析[J].四川大学学报（自然科学版）.2005,(3).459-466.
[5] 瞿白.大数的生成和素性检验[J].电脑知识与技术.2010,(6).7353-7356.
七、附录
1.验证Miller-Rabin大素数判断算法的python程序
import random
def isprime(n):
k,p=0,n-1
while (p&1)==0:
p=p>>1
k+=1
for j in range(6):
a=random.randint(1,n-1)
b=pow(a,p,n)
flag=0
if b==1:
continue
for i in range(k):
if (b+1)%n==0:
flag=1
break
else:
b=(b*b)%n
if flag==1:
continue
else:
return False
return True
n=int(input())
if isprime(n):
print(n,’is prime’)
else:
print(n,’is composite’)
if __name__ == ‘__main__’:
isprime(n)
2.使用GMP库生成随机大素数的C语言程序（p为512bits的大素数）
#include <stdio.h>
#include <gmp.h>
#include<time.h>
int main()
{
clock_t time = clock();
gmp_randstate_t grt;
gmp_randinit_default(grt);
gmp_randseed_ui(grt, time);
mpz_t p;
mpz_init(p);
mpz_urandomb(p, grt, 512);
mpz_nextprime(p, p);
gmp_printf(“p = %Zd\n\n”, p);
return 0;
}
3.使用python生成512bits大素数的核心函数
i.生成伪素数
def proBin(w): # w表示希望产生位数
list = []
list.append(1) #最高位定为1
for i in range(w – 2):
c = randint(0, 1)
list.append(c)
list.append(1)
ls2 = [str(j) for j in list]
ls3 = ”.join(ls2)
b = int(ls3[0])
for i2 in range(len(ls3) – 1):
b = b << 1
b = b + int(ls3[i2 + 1])
d = long(b)
return d
ii.产生512位素数
def pro512(): # 产生512位素数
while 1:
d = proBin(512)
for i in range(50): # 伪素数附近50个奇数都没有真素数的话，重新再产生一个伪素数
u = testMillerRabin(d+2*(i), 5)
if u:
b = d + 2*(i)
break
else:
continue
if u:
return b
else:
continue
文章出处登录后可见！
