快速寻找大素数的算法分析与实现

《快速寻找大素数的算法分析与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、快速寻找大素数的算法分析与实现宋阳秋黄华林龚成清（广东女子职业技术学院计算机系，广东广州511450）摘要：RSA是目前最优秀的公钥方案之一，其安全性建立在大整数分解为两个素数之积的困难性假设基础之上。由于RSA进行的都是大数运算，因此受到素数产生技术的限制，产生密钥困难。从超大整数在内存中的表示方法及基本运算方法开始，讨论了两种产生素数的方法：试除法和测试法，根据产生素数范围的不同，使用试除法和测试法可有效地解决快速产生大素数的技术难题。关键词：素数；模运算；大数求幂中图分类号：TP311文献标识码：A文章编号：在现代密码学中

2、，一些加密方法的安全性主要基于复杂数学问题的难解性假设，以其发明者RonRivest、AdiShamir和LenAdleman的名字命名的基于大整数因子分解的公钥密码系统RSA就是其中很具代表性的一类，它是第一个既能用于数据加密也能用于数字签名的算法，其安全性建立在大整数分解为两个素数之积的困难性假设基础之上，从提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。由于RSA进行的都是大数运算，如常用的RSA密钥长度为512比特（约为十进制的154位），而目前认为RSA的密钥长度在102

3、48比特（约为十进制的3000位）以上才是足够安全的，因此，RSA的主要缺点之一就是受到素数产生技术的限制，运算代价高、速度慢，产生密钥困难，难以做到一次一密。快速产生大素数成为RSA算法的关键技术之一。一、大整数在内存中的存储形式在C++语言中，整数类型共有6种，分别是有符号的短整型（short）、无符号的短整型（unsignedshort）、有符号的整型（int）、无符号的整型（unsignedint）、有符号的长整型（long）和无符号的长整型（unsignedlong）。它们的属性如下：类型名长度(字节)取值范围shor

4、t2-32768~32767unsignedshort20~65535int4-2147483648~2147483647unsignedint40~4294967295long4-2147483648~2147483647unsignedlong40~4294967295图1由上表可以看出，C++语言中整型的最大值是4294967295，当参与运算的所有大整数不超过这个最大值时，可以采用相应的类型对大整数进行定义。而在RSA算法中参与运算的大整数远大于C++语言中所能直接表示的最大值，因此，我们可以考虑用一维数组来存储大整数，

5、数组中的任一个元素对应于大整数中的一位数字，即0~9之间的任一个数字，数组类型可以采用short类型或unsignedshort类型，但是，这两种类型使得数组中的每一个元素在内存中要占用两个字节，这样做不仅在存储大整数上浪费内存空间，更主要的是大整数在运算过程中需要消耗更多的内存资源。由于字符型与整型是互相通用的，因此，我们可以考虑采用char或unsignedchar数据类型代替short或unsignedshort类型来存储大整数，以达到节省内存的目的。这里，我们选择char作为数组的类型。二、数字字符表示的大整数运算数字字

6、符0~9在内存中是以ASCII码形式存放的，对应的十六进制值分别是30H~39H，其特点是这10个字符的高四位值是3，低四位的值与数字值正好相同，因此，进行数字与数字字符转换时只需加上或减去“0”字符的ASCII码值即可。根据这一规则，用一维字符数组表示的大整数的基本四则运算就容易实现了。做加法时，对应的数组元素减去数字字符’0’，然后再相加，如果和大于9则表示有进位，否则无进位。做减法时，对应的数组元素直接相减，如果差小于0，则表示有借位，否则无借位。做乘法运算时，采用按位相乘的方法，将结果对10取模取得相应的位值，对10整除

7、取得进位值。除法运算不能采用按位相除的方法，但可以将除法转换为减法来实现，具体做法是：用被除数减去除数，每减一次，商加1，差再赋给被除数，如此循环，直到被除数小于除数为止。除了这四种基本运算外，设计算法时，还要较多的用到比较运算，做两个大整数比较运算时，要优先比较数字字符串的长度，串长则表示的大整数较大，如果串长相等，则按正常规则比较两个字符串的大小。三、系统运行环境说明虽然是超大整数的运算，但系统对运行的环境并没有过高的要求，计算机主要的软、硬件性能指标如下：指标性能CPUPentiumⅢ级主频800MHz内存128MB硬盘8

8、0GB虚拟内存8500MB操作系统Windows2000程序开发环境VisualC++6.0图2四、寻找大素数方法分析（一）试除法试除法是判别一个整数是否为素数的常用算法，即任意给定一个整数x，用y从2开始来试除它，如果能整除，则这个整数不是素数，否则，用下一个