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

Algorithmn Analysis and Realization for Fast Finding Big Prime Number

RSA是目前最优秀的公钥方案之一,其安全性建立在大整数分解为两个素数之积的困难性假设基础之上。由于RSA进行的都是大数运算,因此受到素数产生技术的限制,产生密钥困难。本文从超大整数在内存中的表示方法及基本运算方法开始,讨论了两种产生素数的方法:试除法和测试法,根据产生素数范围的不同,使用试除法和测试法可以有效地解决快速产生大素数的技术难题。

RSA is the best solution of public key, at present. Its security is based on the assumption that it is very difficult for big integer transforming into a product of two prime numbers. RSA is making calculation of big number which is restricted to produce prime number by technology, so it is difficult to produce secret key. This article starts from the expression and the basic calculation of super big integer in memory, and discuss two methods of producing prime number：the trial division method and the test method. According to the different scope of producing prime number, the trial division and the test method can solve the problem of producing prime number effectively.