信息安全基础综合实验讲义(素性检测)-2011版

《信息安全基础综合实验讲义(素性检测)-2011版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一部分数论基础实验1.2素性检测的实现素性检测被广泛运用于密码学算法，以寻找算法中需要的大素数（例如RSA）。另外，素性检测除了用于判断一个大于1的正整数是否为素数外，还可以用于寻找在给定范围内3264（例如[2,2]）的素数。一、实验目的熟悉常用的素性检测算法。运用高级程序设计语言实现一种素性检测算法的程序，加深对素性检测方法的理解。二、实验原理1.基于Eratosthenes筛法的素性检测古希腊数学家Eratosthenes(公元前276~公元前195)发现了一种找出不超过一个给定正整数n的所有素数的方法，称为Eratosthenes筛法（SieveofEratosthe

2、nes）。所谓筛法就是将不合条件的整数筛掉，而将符合条件的整数“捉住”。Eratosthenes筛法筛选由大于1并且小于或等于n的所有自然数组成的数列。首先取第一个素数2，划去所有除2以外的2的倍数。在余下的正整数中，大于刚刚取到的素数2的第一个正整数，即正整数3被认定为素数，其倍数(不包括自身)同样从数列中划去。这一过程持续到找到一个大于n的素数为止。在数列中没有被划去的正整数就是小于或等于n的素数。算术基本定理断言每一个大于1的正整数都可以唯一分解为有限多个素数的乘积。由此可见，素数是大于1的正整数的基石。以此断言为依据，为确定一个正整数n是否为素数，基于Eratosthe

3、nes筛法的素性检测算法是一种最为朴素的判定方法，即让n试除所有小于n的平方根的素数，若找不到因子，则n为素数，否则n为合数。基于Eratosthenes筛法的素性检测是一种确定性的素性检测算法。下面通过一个例子具体说明基于Eratosthenes筛法的素性检测算法。【举例】判断2543是否为素数第一步：求2543的平方根，254350.~=第二步：使用Eratosthenes筛法求出小于51的所有素数，即2，3，5，7，11，13，17，19，23，29，31，37，41，43，47。1第三步：2543除以这15个素数，结果都不能整数。第四步：得出结论，2543为素数。对于较

4、小的正整数（小于10，000，000），使用Eratosthenes筛法做素性检测是一种非常有效的方法。对于较大的正整数，Eratosthenes筛法因算法效率低而变得不实用。这是因为素数的个数是无限的，随着数据范围增大，素数分布变得越来越稀疏。表1-2为十亿以内的素数分布及其概率。可以看出，数据范围越大，是素数的概率越小。为了“捉住”一个较大的素数，Eratosthenes筛法需要付出大量的时间筛除不符合要求的数。表1-2十亿以内素数的分布及其概率数据范围素数的个数素数的比例10440%10025%25100016.8%16810000122912.29%1000009.59

5、2%959210000007.8498%78498100000006645796.64579%1000000005.761455%576145510000000005.0847544%508475442.Miller-Rabin概率素性检测Miller-Rabin算法是Fermat算法的一个变形改进，它的理论基础由Fermat定理引申而来。n-1【Fermat定理】n是一个素数，a是正整数，并且a和n的最大公约数gcd(a,n)=1，则a≡1(modn)。n-1费马小定理的逆否命题是成立的，即对于正整数n和a，如果gcd(a,n)=1，但不满足a≡1(modn)时，可以确定n是

6、一个合数。但是费马小定理的逆命题不成立，即对于正整数n和a，n-1gcd(a,n)=1，满足a≡1modn时，n不一定是素数，还可能是合数。这样的合数称为以a为底的伪素数。为此，可以尝试以不同的a作为底，进行二次或多次探测，以确保取得高正确n-1率的素性检测结果。在伪素数中，有一类合数以任何与n互素的a为底都满足a≡1modn。这样的伪素数以其发现者RobertDanielCarmichael命名，称为Carmichael数。前3个最小的Carmichael数是561,1105,1729。在1~100000000范围内的整数中，只有255个Carmichael数，可见Carmi

7、chael数非常少。tMiller-Rabin算法的理论基础是：如果n是一个奇素数，将n-1表示成2•q的形式(q是奇q数)，设a是和n互素的任何整数，那么a≡±1(modn)或者对某个e(0≤e≤t-1，j∈Z)等式j2⋅ran≡−1(mod)成立。Miller-Rabin算法描述如下：输入：一个大于3的奇整数n和重复检验的次数k。2-k输出：返回n是否是素数(k次重复检验所达到的错误概率小于4)t(1)将n-1表示成2•q，(其中q是奇数，t是2的指数)(2)对i从1到k循环作下面的操作