基于VB的大素数Solovay-Strassen检测的设计与实现

彭韬 陈文庆

（1.广东茂名幼儿师范专科学校 广东省高州市 525200 2.岭南师范学院数学与统计学院 广东省湛江市 524048）

在互联信息时代的今天，网络改变了我们的生活方式，但随之而来的网络信息安全也存严重威协，信息安全也成为互联网世界的热点问题。信息的加密和解密码是解决网络信息安全的主要技术手段之一，而密钥的选取是密码学的关键。目前，对信息加密和解密的算法很多，但公钥密码体制是目前信息加密、解密和数字签名技术中较为广泛应用，因为公钥密码体制中具有较高的安全性(如RSA、ElGamal 等算法)。但RSA、ElGamal 等算法的公开密钥和私有密钥都需要大素数，因此，对大素数的选取在RSA、ElGamal应用中十分重要。信息的高度保密对密钥位数要求越来越多（512位、1024 位或更多位数），也就是对素数的位数要求越来越大，而要判断一个大整数是否为素数的难度也在不断加强。此时，能否快速、有效地判断一个大整数的属性就显得极为重要。

目前，大素数检测方法有Solovay-Strassen 检测法、Lehman 检测法和Miller-Rabin 检测法。而Solovay-Strassen 检测法最为常用，而且该方法相对于其它概率性检测法来说准确率更高[1-5][7-8]。本文主要探讨如何在Visual Basic 环境下实现大素数的检测，解决在应用系统开发时实现数据的加密和解密，以保证系统的信息安全。

1 Visual Basic整型数据类型和大整数的存储

Visual Basic 有3 种整型基本数据类型，它们的性质和表示范围如表1所示。

由表1 可以看出，长整型long 是Visual Basic 中最大整型数据类型，其存储长度为4 字节即32 位二进制数，这样的有效位数的整数远远不能满足各种密码体制的密钥位数的需要，而Visual Basic不能直接存储和运算超过32 位的整型数据。为了解决在Visual Basic 中可以实现大整数的存储和运算，利用Visual Basic 中的动态数组来存放大整数，而且数组中每个元素的数据类型是long，其定义如下：

Dim Number( ) as Long

采用这种数据结构存储整型数据，数组的元素个数是动态的，不受数量限制，理论上可以实现任位数的整型数据的存储和运算。数组中每个元素存放4 字节整数，即是说每个数组元素就相当于存放32 位二进制数，且数组的元素个数不受限制，可以动态增加和减少，这样大大提高了Visual Basic 中整型数据的表示范围。

2 大素数的检测方法

在公钥密码体制中，大素数的选取是构造公钥和私钥的关键。目前，大素数检测方法可以分为确定性大素数检测和概率性大素数检测，但目前还没有有效的确定性大素数检测方法，概率性大素数检测是目前大素数检测的主要方法。

2.1 素数检测方法的分类

目前，大素数的检测方法有确定性和概率性大素数检测两种，确定性大素数检测方法主要有基于Lucas 和Pocklington 定理的确定性素数检测方法[3]。确定性大素数检测方法产生的大整数必然是大素数，该方法的优点在于产生的数一定是大素数，但缺点是生成的大素数位数受到的限制(一般位数比较少等)，特别是如果算法设计不当，非常容易产生出有规律的素数，素数的变化规律非常容易被密码破译者破译，直接破解到密码系统所使用的素数，从而影响密码的安全性。确定性大素数检测方法的效率低且安全性非常差，因此，目前大素数检测方法主要采用概率性检测方法，其理论基础是Fermat 小定理：若n 是素数，则对所有1 ≤a ≤n-1 的整数a，有a(n-1)mod n=1；该定理的逆否命题也成立，即a(n-1)mod n ≠1，则n 为合数。但从大量数据统计来看，如果满足a(n-1)mod n=1，则n 为素数概率较大，但也存在n 原来是合数而被认为素数的可能性（小概率），即n 为伪素数。

这种方法的优点是：检测大素数速度较快，构造的大素数没有规律性，安全性能好，但其缺点就是其检测的大素数具有一定的误判，所以其检测的素数又称为伪素数。其中较为常用的算法有Fermat 检测法、Lehman 检测法和Solovay-Strassen 检测法[1][3][6]。

2.2 Solovay-Strassen素数检测的基本原理

Solovay-Strassen 素数检测建立在以下两个定理基础之上的：

定理1：如果n>2 是一个素数，则对于任意整数a(0

成立[6]。

定理2：如果n>2 是一个奇合数，则至少有50%的，即，使得同余式不成立。

2.3 Solovay-Strassen素数检测的基本算法

根据上述两定理，Solovay-Strassen素数检测算法具体描述如下：

对于待检测奇整数n，执行以下操作：

2.3.1 对i 从1 到t 做循环

（1）选择一个小于n 的随机整数a(0

（3）如果r ≠1 或-1，则返回n 不是素数；

（4）计算Jacobi 符号[9,10]J(b,n)=(b/n)；

（5）如果r ≠(b/n)，返回n 不是素数。

2.3.2 返回n 是素数

2.4 Solovay-Strassen素数检测算法分析

3 Solovay-Strassen大素数检测程序的实现

在Solovay-Strassen 素性检测算法中关键一步就是r=a(n-1)(mod n)，如果采用逐次求幂取模的计算方式，时间复杂度是O(n)，为了提高素数检测效率，本文对算法作了优化。充分利用每次循环过程中的中间结果为下一步计算提供数据。例如计算过程a2(mod n)，a4(mod n)，a8(mod n)，……，等中间结果可以保存到数组中。这样，其后的计算可以充分这些中间结果，例如计算a254(mod 255)时，就可以根据已保存的中间结果计算a254= a128*a64*a32*a16*a8* a4*a2(mod 255)。

本文为了提高模幂计算效率，先计算ai(mod n)的记录于一个表中，其i 是2 的幂次，然后将n-1 转化为二进制表示并由低位到高位存储于数组中，初始值为1，遍历数组，如果某位是1 时则把表中对应位置的ai(mod n)乘以r 并赋值给r，如此循环，即可得到a(n-1)(mod n)值，大大提高了计算模幂运算速度。例如，计算a64(mod n)则要循环64 次模幂运算，改进后则需要进行a2，a4，a8，a16，a32，a64(mod n)共计6 次模幂计算即可。大大提高了测试效率，时间复杂度也由原来的O(n)降到O(logn)。

大素数Solovay-Strassen 测试方法的Visual Basic 程序如下：

4 结束语

本文主要讨论了Solovay-Strassen 检测大素数方法的基本理论和算法，并在Visual Basic 环境下采用动态数组实现了大素数Solovay-Strassen 检测算法。本文中只给出了Solovay-Strassen 大素数检测方法的核心代码，在完整的检测代码包括大整数运算、模幂运算等函数，篇幅较长，本文没有详尽给出。