形如2kp+1的数的素性检验

• 作者: 周光明 张韶华 杨金凤 陈恭亮
• 来源期刊: 数学杂志
• 学科: 数学
• 关键词: 素性检验 多项式时间算法 安全素数 RSA密码系统
• 年，卷（期）: 2005,（1）
• 页码范围: 30-32
• 页数: 3页
• 分类号: O156.1
• 字数: 837字
• 语种: 中文
• DOI: 10.3969/j.issn.0255-7797.2005.01.006

摘要

本文初步探讨了如何快速检验一个大数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的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张韶华	武汉大学数学与统计学院	2	5	2.0	2.0
3	周光明	湘潭大学数学与计算机科学学院	19	89	3.0	9.0
6	陈恭亮		1	3	1.0	1.0
7	杨金凤	武汉大学数学与统计学院	1	3	1.0	1.0