|
|||||
|
|
| 形如2kp+1的数的素性检验 | |
| 引用本文： | 张韶华,陈恭亮,周光明,杨金凤.形如2kp+1的数的素性检验[J].数学杂志,2005,25(1):30-32. |
| 作者姓名： | 张韶华 陈恭亮 周光明 杨金凤 |
| 作者单位： | 1. 武汉大学数学与统计学院,武汉,430072;中船重工集团武汉船泊通信研究所,武汉,430079 2. 上海交大信息安全工程学院,上海,200052 3. 湘潭大学数学与计算机科学学院,湖南,湘潭,411105 4. 武汉大学数学与统计学院,武汉,430072 |
| 基金项目： | A Project Supported by Scientific Research Fund of Hunan Provincial Education Department |
| 摘 要： | 本文初步探讨了如何快速检验一个大数n是素数(这里n-1含有大的素因子)的算法问题以及如何生成一个大素数p使得p-1有大的素因子q的算法问题.我们给出了形如n=2kp+1的数的素性检验的多项式时间算法,这里p是一个给定的大素数,k是正整数满足22k＜2kp.该算法的计算量为O(log32n).然后我们给出了生成一个大素数p使得p-1有大的素因子q的算法,其中q满足q＞(p-1)/log2(p-1).特别地,我们给出了判定并生成一个安全素数p的算法. |
| 关 键 词： | 素性检验 多项式时间算法 安全素数 RSA密码系统 |
DETERMINATION OF THE PRIMALITY OF 2kp+1 |
|
| Abstract.DETERMINATION OF THE PRIMALITY OF 2kp+1[J].Journal of Mathematics,2005,25(1):30-32. | |
| Authors: | Abstract |
| Abstract: | In this paper, we preliminarily explore how to determine quickly whether a large number n is prime, where n-1 has a large prime factor, and how to generate a large prime p such that p-1 has a large prime divisor q. We give a deterministic polynomial-time algorithm that determines whether n=2kp+1 is prime, where p is a given odd prime and k is a positive integer satisfying 2 2k<2kp. The algorithm we present runs in O(log3 2n) time. Then we give algorithms for generating a prime p such that p-1 has a large prime divisor q, where q satisfies q>(p-1)/log 2(p-1). Especially, we give the algorithm that determines and generates a safe prime p. |
| Keywords: | primality testing safe prime RSA cryptosystem polynomial-time algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |