【论文】solovay-strassen素数判定算法

《【论文】solovay-strassen素数判定算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、网络信息安全的研究主要有W个研究方句，一个是网络协议的分析，通过分析网络I•办议检测出网络I•办议屮存在的漏洞，然后冇效的修改这些网络I办议，弥补这些漏洞。另一个就是通过对信息进行加密，把需耍通过网络传输的信息加密沿再进行传输和把机密的信息加密后再进行存储。近年来，随着计算机运算速度的不断提升利黑客攻击手段的不断改进，保密通信和信息安全越来越受到人们的重视，直接促进了密码学的发展和应用。在现代密码系统中，大素数的判别和寻找对一些加密系统起着关键作用。很多公钥密码算法都用到素数，特别是160位（二进制）以上的大素数。熟知，RSA的公共模数就是W个512（近年来乂有了对1

2、024,乃至2048）位以上的大素数的乘积；又如，基于有限域［上离散对数的公钥密码体制，其中素数p要求在512位以上，且p-1有一个大素冈子q（160比特以上）；再如，基于椭圆曲线离散对数的公钥密码体制（ECC）中，一般要求基点的阶是一个160位以上的大整数，且是一个素数。由此可见大数的素性判断的重要性。侶当前既没有一个有效的确定性素数检测算法，也没奋一个高效确定性素数产生算法。当前使用的高效的素数判定算法都是概率算法，速度虽快，但可能会错判误判，即把合数判定成素数，这将会严重影响系统的可靠性以及安全性。而RSA算法是目前最优秀的公钥解决方案之一，其安全性建立在大整数

3、分解为两个素数之积的困难性假设基础之上。凶此，RSA算法的核心闷题是要解决通过何种方式能快速的找到W个大的随机素数。这样既有利于提高RSA加密的安全性，乂有利于提高加密效率。因此，开展在多项式吋间内判断一个正整数是否是素数的确定性算法研究，以及快速素数产生算法的研究是非常必要和急需的，这对于促进公钥密码体制的应用以及增强保密通信的可靠性以及安全性都有重要意义。2算法概述素数就是一个除了1和它a身以外不能被其它数整除的数。关于素数的一个基本w题是如何冇效地确定一个数是否是一个索数，即素性测试m题。素性测试问题不仅在数学上是一个有挑战性的问题，而且在实际应用系统屮也具有十

4、分重要的地位。例如，很多现代密码学应用通常需要确定一个儿百位的素数。如果不采用一些快速冇效的素性测试方法，即使人们使用运行速度最快的计算机来测试一个100位的十进制整数，花费的时间也将可能超过宇宙可能存在的时间。判定一个整数是否是素数，最为简单的办法就是直接利用素数的定义，用比耍判断的数小的整数去一一试除，如果冇一个数能整除耍判别的数的话，那就能确定该整数为合数。统计表明，大约宥76%的奇数宥小于100的素因子，可见这种最平凡的方法有吋十分有效。但是对于大素数來说，由于计算量太大，根本无法实现用于具体的应用系统屮。所以科学家们根据素数判断的理论发明Y许多新的算法，提高

5、了素数判断的效率。数学家们设计快速冇效的素数测试方法的历史已经长达两下多年了。Eratosthenes筛法是对于所奋素数都奋效的最古老的素数测试算法，然而它的吋问复杂性与输入整数的关系是关于输入整数的规模的幂指数关系，因此在实际中使用它来测试大的素数是不合适的。实践屮常见的素数检测方法大致分为两类，一类是确定性的，例如Lehmer的N—1检测，Lucas的N+I检测，椭圆曲线素性证明(ECPP)等等，当输出结果为“素数”时，能够保证被检测数一定为素数。另一类是概率性的，如Miller-Rabin检测，Baillie-PSW检测等等，当输出结果为“素数”时，仅以一定的高

6、概率保证被检测数的素性。不过概率性检测一般要比确定性检测快得多。目前，国外用于测试整数素性的概率算法常见的有两个，即Solovay-Strassen算法和Miller-Rabin算法。3Solovay-Strassen概率素数测试法Solovay-Strassen概率素数测试法是建立在以卜两个定理之.卜.的。定理1:设p>2是一个素数，则对任意整数a>0，a㈣(―)=a2(modp)oP定理2:如果n〉2是一个奇合数，则至少冇50%的aeZ,即lSa^/2-l,使得同余式a社(―)=a2(modn)n不成立1.算法描述根掘以上两个定理，Solovay-Strassen

7、素数测试法描述如卜：(1)随机均匀的选取ue{1，2,..…(2)计算gcd(a,n)；(3)如果gcd(a，n)关1，贝1Jn不是素数;a(4)计算(一)和a2(modn)；na(5)如果2(modzi),则n可能是素数；否则，n不是素数。n2.算法分析如果对一个大整数n找到一个任意的a,使得不成立,则可证明n不是素数，否则n是素数的概率至少为50%。如果对n进行k次Solovay-strassen素性测试，如果甸次输岀都为n可能是素数，则n是合数的概率小于1，当k足够大时，1是一个十分小的数。2"2"3Solovay-Strassen算法的实现细