搜索
第一部分数论基础实验1.2素性检测的实现素性检测被广泛运用于密码学算法，以寻找算法中需要的大素数（例如RSA）。另外，素性检测除了用于判断一个大于1的正整数是否为素数外，还可以用于寻找在给定范围内（例如[232,264]）的素数。一、实验目的熟悉常用的素性检测算法。运用高级程序设计语言实现一种素性检测算法的程序，加深对素性检测方法的理解。二、实验原理1.基于Eratosthenes筛法的素性检测古希腊数学家Eratosthenes(公元前276~公元前195)发现了一种找出不超过一个给定正整数的所有素数的方法，称为Eratosthenes筛法（SieveofEratosthenes）。所谓筛法就是将不合条件的整数筛掉，而将符合条件的整数“捉住”。Eratosthenes筛法筛选由大于1并且小于或等于n的所有自然数组成的数列。首先取第一个素数2，划去所有除2以外的2的倍数。在余下的正整数中，大于刚刚取到的素数2的第一个正整数，即正整数3被认定为素数，其倍数(不包括自身)同样从数列中划去。这一过程持续到找到一个大于nn的素数为止。在数列中没有被划去的正整数就是小于或等于n的素数。算术基本定理断言每一个大于1的正整数都可以唯一分解为有限多个素数的乘积。由此可见，素数是大于1的正整数的基石。以此断言为依据，为确定一个正整数是否为素数，基于Eratosthenes筛法的素性检测算法是一种最为朴素的判定方法，即让n试除所有小于n的平方根的素数，若找不到因子，则n为素数，否则n为合数。基于Eratosthenes筛法的素性检测是一种确定性的素性检测算法。下面通过一个例子具体说明基于Eratosthenes筛法的素性检测算法。n【举例】判断2543是否为素数第一步：求2543的平方根，254350.~=第二步：使用Eratosthenes筛法求出小于51的所有素数，即2，3，5，7，11，13，17，19，23，29，31，37，41，43，47。1第三步：2543除以这15个素数，结果都不能整数。第四步：得出结论，2543为素数。对于较小的正整数（小于10，000，000），使用Eratosthenes筛法做素性检测是一种非常有效的方法。对于较大的正整数，Eratosthenes筛法因算法效率低而变得不实用。这是因为素数的个数是无限的，随着数据范围增大，素数分布变得越来越稀疏。表1-2为十亿以内的素数分布及其概率。可以看出，数据范围越大，是素数的概率越小。为了“捉住”一个较大的素数，Eratosthenes筛法需要付出大量的时间筛除不符合要求的数。表1-2十亿以内素数的分布及其概率数据范围素数的个数素数的比例10440%1002525%100016816.8%10000122912.29%10000095929.592%1000000784987.8498%100000006645796.64579%10000000057614555.761455%1000000000508475445.0847544%2.Miller-Rabin概率素性检测Miller-Rabin算法是Fermat算法的一个变形改进，它的理论基础由Fermat定理引申而来。【Fermat定理】n是一个素数，a是正整数，并且a和n的最大公约数gcd(a,n)=1，则an-1≡1(modn)。费马小定理的逆否命题是成立的，即对于正整数n和a，如果gcd(a,n)=1，但不满足an-1≡1(modn)时，可以确定n是一个合数。但是费马小定理的逆命题不成立，即对于正整数n和a，gcd(a,n)=1，满足an-1≡1modn时，n不一定是素数，还可能是合数。这样的合数称为以a为底的伪素数。为此，可以尝试以不同的a作为底，进行二次或多次探测，以确保取得高正确率的素性检测结果。在伪素数中，有一类合数以任何与n互素的a为底都满足an-1≡1modn。这样的伪素数以其发现者RobertDanielCarmichael命名，称为Carmichael数。前3个最小的Carmichael数是561,1105,1729。在1~100000000范围内的整数中，只有255个Carmichael数，可见Carmichael数非常少。Miller-Rabin算法的理论基础是：如果n是一个奇素数，将n-1表示成2t•q的形式(q是奇数)，设a是和n互素的任何整数，那么aq≡±1(modn)或者对某个e(0≤e≤t-1，j∈Z)等式成立。21(mod)⋅≡−jranMiller-Rabin算法描述如下：输入：一个大于3的奇整数n和重复检验的次数k。2输出：返回n是否是素数(k次重复检验所达到的错误概率小于4-k)(1)将n-1表示成2t•q，(其中q是奇数，t是2的指数)(2)对i从1到k循环作下面的操作：(2.1)随机选择一个整数a(2≤a≤n-1)。(2.2)e←0，计算b←aqmodn(2.3)如果b≠1并且b≠n-1作下面的操作，否则当ik时转2.1；当i=k时转3:(2.3.1)e←e+1(2.3.2)当et并且b≠1，b≠n-1时，循环作下面操作，否则跳到2.3.3：计算b=b2modn；如果b=1则返回“是合数”；否则e←e+1；(2.3.3)如果b≠n-1,返回“是合数”；(3)返回“是素数”。说明：在本算法(2.3.2)的循环中，当b=1时有。此时其前一步有成立。由b=1返回“是合数”的理论基础如下：21(mod)⋅≡eqann121(mod)−⋅≠±eqa【事实】x，y和n是整数，如果x2≡y2(modn)，但是x≠±y(modn)，则是n的一个非平凡因子。12gcd(1,)−⋅−eqanMiller-Rabin是概率算法，一次将检测得到结果的正确率为75%，所以为了检测结果的正确率应该多次调用该函数。对于k次重复的Miller-Rabin概率素性检验，Miller-Rabin概率素性检测的正确率为1-(1/4)k。三、实验环境操作系统：Windows2000/XP/2003或以上版本。应用软件：VC++6.0或以上版本。四、实验内容和任务本实验要求学生掌握常用的素性检测算法的实现方法，并运用高级程序设计语言实现一种素性检测算法。表1-3给出Eratosthenes筛法素性检测函数的接口定义，作为编程实现参考。Eratosthenes筛法素性检测的程序流程图如图1-5所示。3图1-5Eratosthenes筛法素性检测程序流程图表1-3Eratosthenes筛法素性检测函数接口函数intEratosthenes(unsignedlongn)功能Eratosthenes筛法检测正整数n是否是素数输入n(待检正整数)输出0，表示n不是素数；1，表示n是素数。引入布尔类型数组a[i]，数组下标i组成Eratosthenes筛法检测的数列。首先，将数组的所有元素a[i]=true，划掉数列中的某个元素i表示成a[i]=false。Eratosthenes筛法检测结束后，如果i是质数，那么a[i]=true，否则a[i]=false。在C++中，开方函数为sqrt(n)。基于筛法的Miller-Rabin函数接口的定义示例如表1-4所示：表1-4素性检测函数接口函数intMillerRabin(unsignedlongn,unsignedintno_of_smallprimes,unsignedintk)功能带除法筛的Miller-Rabin概率素性检测函数，检测正整数n是否素数输入n(待检测对象)，no_of_smallprimes(小素数表中的素数个数)，k（循环检验次数）输出0，表示n不是素数，n可能是合数或者等于1N4Y1，表示n是素数（错误概率4-k）函数int*twofact(unsignedlongn)功能把n分解成形如n=2t*q,q是奇数的形式，即求n=2t*q中的t和q输入n(待分解的正整数)输出数组首地址twofact[0]（存放指数t）twofact[1]（存放奇数q）函数intsieve(unsignedlongn,unsignedintno_of_smallprimes)功能筛法函数，即用小素数依次作因子检测n的素性输入n(待分解的正整数)，no_of_smallprimes(小素数表中的素数个数)输出2,表示n不是素数1，表示n是素数0，表示在检测过程中n不包含小素数的因子全局变量intsmallprimes[]={2,1,2,2,…};长度为6542。MillerRabin函数程序流程图如图1-6所示。图1-6基于筛法的Miller-Rabin素性检测程序流程图素性检测的界面实例如图1-7所示。输入n的值，选择素性检测算法，进行检测。点击重置按钮，可清空输入，以便重新输入测试值。【举例1】n=725519,返回结果：是素数，错误概率4-k。【举例2】n=725637,返回结果：不是素数。5图1-7素性检测示例界面【问题】判别n=547676767的素性，并比较两种方法进行素性检测的时间。6