当前位置:   article > 正文

Miller-Rabin大素数判断算法的原理及其实现_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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/75292
推荐阅读
相关标签
  

闽ICP备14008679号