大学英语四级准考证-派出所实习总结

一种素数产生算法

曹云飞，杨 煜，邓小艳
（现代通信国家重点实验室，四川 成都，610041）

【摘 要
】 素数判定是许多公钥密码算法中的一个重要环节，当前在密码算法中所使用的素性测试方法都是概率素数测
试法。本文提出一种有效素数产生算法，该算法能在较快时间内产生任意比特长、从理论可以证明的素数。
【关键词
】AKS；椭圆曲线密码体制；素数；素性判定
【中图分类号】
TP309
【文献标识码】
A
【文章编号】
1002-0802(2007)08-0031-02

An Algorithm for Generation of Prime Number

CAO Yun-fei, YANG Yu, DENG Xiao-yan
（State Key Laboratory for Modern Communications, Chengdu Sichuan 610041, China）

【Abstract】The determination of prime number is an important part to lots of public-key cryptographic
algorithms. However,the methods for testing primality are all based on probability. In this article, an efficient
algorithm is proposed, which can generate prime number of any bit length in short time.
【Key words】AKS; elliptic curve cnyptography; primes; judging prime numer

0 引言
很多公钥密码算法都用到素数，特别是160位（二进制）
以上的大素数。 熟知，RSA的公共模数就是两个512位以上的
大素数的乘积；又如，基于有限域
F
P
上离散对数的公钥密码体
制，其中素数
p
要求在512位以上，且
p-1
有一个大素因子
q
（160比特以上）；再如，基于椭圆曲线离散对数的公钥密 码体
制（ECC）中，一般要求基点的阶是一个160位以上，且是一个
素数。由此可见对大数 的素性确定性要求的重要性。但当前既
没有一个有效的确定性素数检测算法，也没有一个高效确定性素数产生算法，当前使用的素数判定算法都是概率算法，速度
虽快，但可能会错判，即把合数判定成 素数，这将会影响系统
的可靠性以及安全性。
对于RSA来说，公开模数
n=pq< br>，这里
p
和
q
是素数，
如果
p
和
q
其中之一的素性判断发生错误，即有一个是合
数，那么欧拉（Euler）函数
s，因此在计算公私钥时候就会
，如果这样的话用
出错（原先按
ed=1
模
ϕ
(n)=
(
p-1
)
(q-1)
）
RS A的加密过的明文，就不能解密了。同样，正确的签名也
不能通过验证。
对于ECC来说， 现在使用最多得就是素数域以及二元扩
如果把
p
的素性判错，
域上ECC。对 于素数域
F
P
上ECC而言，
即
p
是合数，不妨设
p
=
r
×
s
（r，
s
值都大于1），那么
F
p
=
F
r
×
s
，椭圆曲线上有理点的个数（设为
#
E
(
F
p
)
）的因
子含有
#< br>E
(
F
s
)
以及
#
E
(
F
r
)
，即
#E(F
p
)=#E(F
s
)* #E(F
r
)
*x
(
x
是一个待定的数)。如果r和
s
都较大的话，密钥尺寸
将变小，严重影响ECC的安全强度。一般而言，ECC基点的阶都要求是一个素数，如果不是则可以用Pohlig-Hellman
算法进行有效攻击。 这样开展在多项式时间内判断一个正整数是否是素数
的确定性算法研究，以及快速素数产生算法的研 究是非常必
要和急需的，这对于公钥密码体制的应用以及增强保密通信
的可靠性以及安全性都有 重要意义。
文中提出一种高效、易实现的、任意比特长的素数产生
算法，该算法产生的数不 需进行素性判断，从理论上可以证
明该数一定是素数。

1 素性判定的发展历史
1975年Pratt
[1]
证明了数的素性在非确定性多项式时间
内可以判 别。
给
1976年Miller
[2]
假设在广义黎曼假设成立的条件下，

出确定多项式时间算法来检测素性，所需时间为
Ο(logn)
。
1977年Solovay和Strassen
[3]
,1980年Rabin
[4]
分别运
用费马小定理和二次剩余证明了在任意的多项式时间内可
以判定一个合数。 < br>1986年Goldeasser和Kilian
[5]
证明了绝大部分数的素
性可以在任意的多项式时间内给出判定。
直到2002年，由Manindra Agrawal,Neeraj Kayal and
4

收稿日期：2007-06-15。
作者简介：曹云飞（1971-），男，硕士，高级工程师,主要研究方为密码理由与应用；杨 煜， 男,主要研究方为信息安全等；邓小艳（1976-），
女，硕士，讲师,主要研究方为系统理论、编码 密码学等。

31

Nitin Saxena提出的AKS算法，才 提供了一个可以在多项
式时间内完成对指定数进行素数判定的确定性算法，该算法
的运行时间为
Ο(log
12
n)
。他们采取了全新的思路，不是直
接去研究某个 数是否为素数，而是从被检验的数出发，构造
一系列的小问题或者说等式，若所有等式都成立，则这个数
是素数；若其中任何一个等式不成立，则该数不是素数。后
来许多科学家对该算法进行了改进( Lenstra 2002
Pomerance 2002, Berrizbeitia 2003, Cheng 2003,
Bernstein 2003ab, Lenstra and Pomerance 2003)，其中
有一个比较好的改进是由Bernstein 2003a出的(简称
Bernstein算法), 它比原始的AKS算法要好，主要体现在寻
找r上。AKS算法和Bernstein算法的不同之处主要在于
while循环中寻找r的不等式 不同，按照Bernstein算法找
到的r及for循环的次数
s
均比AKS算法找 到的要小得多，
于是运行速度也要快得多。但从现目前研究工作以及实现中
的实验数据和对算法 本身的分析可以看出，AKS算法和
Bernstein算法离实际应用尚有很大距离。
目前，国内外用于测试整数素性的概率算法，通常有两
个，即Solovay- Strassen算法和Miller-Rabin算法。

[6]
11.3
设
i
为
E
的比特数；

11.4
如果
i
大于
n
；

11.4.1
R=R
2
；

11.4.2
E=
2
PR+
1
；

11.4.3
i
为
E
的比特数；

1.
如果
i≠n
转到 6；

2.
mod
=
2
E
-1
(
E
)
；

3.
如果
mod
≠
1
，转到 6；

4.
mod=gcd(mod-1,E)
；

5.
如果
mod
≠
1
，转到 6；

6.
P
2
=
2*
P
；

7.
x=R P2
；

P
；
8.
y=R
% 2
9. *tp=yy-4*x
；

10.
如果
tp=0
或者
tp=4
，转到 6；

11.
tp=E
(4*
P
*
P
*
P
)
；

12. for i=1 to tp do
；

23.1
E
；

=RM
；
23.2
mod %
23.2
如果
mod
=i
，转到 6；
24
输出
E
。

算法的几点说明：
(1)算法步骤1和2的目的是产生一个32 bit的素数
P
，
即引理中所 说的素数
P
。对
P
进行试除判定就是穷尽小于
P
每一个素数 ，看是否能整除
P
。通过程序搜索可知小于
2
16
的素数一共
6 541
个。由于数目不多，测试数字较小，故
2 素数产生算法
引理
[7]
：设P是一个素数，R是任意整数，E
=
2
PR
+
1
，
则
e
是一个素数的充要条件为：

(1)
存在一个整数
a
满足
:
a
E
-1
≡
1mod
E
,
gcd(a
2
R
-1,
E
)
≡
1
。

(2)
如果
R=2Px+y
（其中
x
和
y
是整数且有
，则
y
2
-4x
既不等于
0
也不等于
a
2
。

0≤y<2P
）
产生
32
比特随机素数的速度很快。
(2)算法中的步骤3到12的目的是产生
n
比特的随机数
E
，且能分解 成
2
PR+
1
，也就是引理中
E
。
(3) 对于所有满足
1
≤
m
<
e4P
3
的
m
有：
R≠m mod 2Pm+1
。

对引理进行适当修改，一些条件适当控制，得到一个高
效，可行的一个素数产生算法。

2.1素数产生算法
输入：所产生素数的比特数为
n
。

(3)由于如果
E
为素数，可知对于任意
a
,有
a
E
-1
≡
1
(
E
)
。
故为了加快计算速度，在算法 1中
a=2
，这不会影响引理
本身的正确性。

(4)为了使得引理 (3)的循环次数不太大，在算法中进行
控制，其循环次数在
2
16
次以内。
2.2素数产生算法
输入：所产生素数的比特数为
n
。


输出：
n
比特的素数
E
。

产生一个
32
比特的随机数
P
。

对这一个随机数进行试除判定，如果没有通过，则转到
1
：

1.
计算
R
=
2
n
+
1
；

2.
计算
min
=
R(2*P)
；

3.
计算
max=(2
n
+
1

输出：
n
比特的素数
E
。

1.
产生
n
比特的随机数
E
；

2.
对E
进行小素数试除
(
一般在
50
以内
)
，如果 能被某
一个小素数整除转到
1;
-1)(2*
P
)
；

4.
产生一个与
min
比特数相同的随机数
R
；

5.
产生一个与
max
比特数相同的随机数
tp
；

6.
R=(tp+R)2
；

E=
*
P
*
R+
1
；

7. 2
8.
设
i
为
E
的比特数；

；
9.
如果
i
大于
n
（
11.1～
11.4
）
3.
使用
Miller-Rabin
算 法对
E
进行素性判断，如果没有
通过，则转到
1
；

4.
输出
E
。

算法2是现目前使用得最广泛、速度最快 的通过素
性检测方法来产生的素数，该算法产生的数是一个概率
素数。

（下转第35页）

11.1
R=R2
；

11.2
E=
2*
P
*
R+
1
；

32

(10
k
-10
k
-1
)
个,故任取一个
k
位整数,该整数为素数的概率为
基点的生成同时完成，而且不改变 传统的安全椭圆曲线生成
算法的时间复杂度，是目前最快的理想椭圆曲线密码体系参
数生成算法 。
m
,
m
=(10
k
ln10
k
-10
k
-1
ln10
k
-1
) (10
k
-10
k
-1
)
。
（3）在时间为n
(
t
1+
t
2+
t
3+
t
4)
内产生
n
条
k
位阶的椭
圆曲线中,阶为素数的椭圆曲线 可能有
[nm]
条,设
f
为
[nm]
的十进制位数，则[
nm
]∈(10
f
-1
,10
f
)
。
（4）产生素阶椭圆曲线的条数与
p
有关,与参数
a
,
b
无
关。该算法同时降低了时间复杂度和计算复杂度。
2.3.2 (算法3和算法4)的测试数据分析
用c++调用NTL快速数论算法库
[3～4]
，在Windows 2000、
Celeron1.4 GHZ、256 RAM 下，对时间
t1
，算法 3平均10
毫秒，算法4平均20毫秒；至于后面的步骤4、5、6、7、8
涉及到的点乘和模 逆运算，NTL更有计算速度上的优势
[3～4]
，
对算法3，
t1
+
t2
+
t4
平均为70毫秒，对算法4，
t1
+
t2
+
t4
平均为80毫秒，算法3、算法4与算法1的时间复杂度相同。
（1）当
p
为具有密码学意义的大素数时，例如取
p
=
2
1 60
-47
，
n
=
2617
，则
k
=49
，
[nm]
=
23
；文献[2]的

参考文献

[1] 谷勇浩，刘勇.一种椭圆曲线参数生成的快速算法［DBOL］.
http:?UID=DWV1_WOUID
_URL_203905&TOC=COLUMN _203905&OBJ=223355.2005.
[2] 祝跃飞， 顾纯祥，裴定一 .SEA算法的有效实现[J].软件学报，2002,
（13）6：1115～1116.
[3] 彭长根.有限域GF（2^m）上椭圆曲线密码体制的运算分析及NTL实
现［J］. 贵州大学学报(自然科学版),2005,1:6～11.
[4] 彭长根.基于NTL算法库的椭圆曲线密码模逆与点乘运算
[J].2005,7:120～122.
[5] 周玉洁，冯登国.公开密钥密码算法及其快速实现[M]. 国防工业出
版社，2002,9:106～109.
[6] Douglas n.密码学原理与实践[M]. 第二版,电子工业出版
社,214
[7]

刘靓.电子商务的加密技术分析[DBOL].http:
applicZL1 .
[8] 肖攸安.椭圆曲线密码体系研究[M].武汉:华中科技大学出版社，
2006:19 0,192～193.
[9] 卢忱,周秦武,卞正中，等.椭圆曲线密码体制基点选取算法的设计与
实现[J].2001,6(34):27～30.
[10]张金山.用分布式并行算法选取 GF[p]上椭圆曲线的基点
[J].2004,(4):56～57.
实验数据为生成10条 素数阶的安全椭圆曲线。理论值23与
10非常接近，因为10,
23∈(10
f-1
,10
f
)
，这里
f
=2
。
（ 2）当
p
为不具有密码学意义的素数时，例如取
p
=12090817,n
=1559
，则
k
=8,[
nm
]=83
； 实验数据为生
成54条素数阶的椭圆曲线。理论值83与54非常接近，因
为83,
5 4
∈
(10
f
-1
,10
f
)
，这里f
=
2
。

3 结语

首次创立准 基点理论，充分利用该理论，改进了传统的
安全椭圆曲线生成算法，改进后的算法使得安全椭圆曲线和< br>
（上接第32页）
没有通过(2)以及(3)的概率。

参考文献
[1] Pratt V R. Every prime has a succinct certificate[J]. SIAM
., 1975,(4):214～220.
[2] Mille G L Riemann’s hypothesis and tests for primality[J].
., 1976,(13):300～317.
[3] Solovay R,Strassen V. A fast Monte-Carlo test for primality[J].
SIAM Journal on Computing, 1977,(6):84～86.
[4] Rabin M O. Probabilistic algorithm for testing primality[J].
Theory, 1980,(12):128～138.
[5] Goldwasser S , Kilian J. Almost all primes can be quickly
certified[J]. In Proceedings of Annual IEEE Symposium on
Foundations of Computer Science, 1986,(3):16～329.
[6] Agrawal M, Kayal N,Saxena N, PRIMES is in Ｐ，-Preprint［D
BOL］.Available at . http:.i-nnewsprim
，2002 August.
[7] 柯召,孙琦. 数论讲义［M]. 北京：高等教育出版社,2003.


3 实验结果

现已成功实现算法1和算法2。通过大量的数据测试发
现：当产生的素数比特数较小（一般而言 小于200比特）时，
两个算法都很快。但随着比特的数的增加，算法2的速度优
势越明显。表 1给出在CPU2.8G，内存为512兆的个人PC机
上的实现速度统计（200次的平均时间，这些 时间与实现技
术关系也很大）。
表1：算法1和算法2实现速度统计表

比特长度
512 比特
1024比特
2048比特
算法1（秒） 算法2（秒）
1.55
15.34
85.21
4.23
142.51
1262.27
时间关系(算
法2／算法1)
2.73
9.29
14.81 < br>从表1可以看出，使用算法2产生素数，在时间上还是
可以接受，算法2已成功应用在RSA以及 ECC中。

经过大量测试还没有发现通过引理中的条件(1)，但没
有可以通过引理 条件(2)以及(3)的情况。这说明素性保证主
要在引理中的条件(1),下一步我们将重点研究通过 （1）但

35