Miller-Rabin大素数判断算法的原理及其实现_miller rabin算法

一、摘要

        大数素性检测一直是数论界、密码学界等经久不衰的研究方向，实现大数素性检测的算法也在不断地被改进。目前已经出现了很多大数素性检测的算法，而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