- 在线时间
- 8 小时
- 最后登录
- 2016-1-23
- 注册时间
- 2004-5-7
- 听众数
- 1
- 收听数
- 0
- 能力
- 0 分
- 体力
- 610 点
- 威望
- 0 点
- 阅读权限
- 30
- 积分
- 218
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 70
- 主题
- 26
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   59% TA的每日心情 | 怒 2014-2-22 20:49 |
|---|
签到天数: 13 天 [LV.3]偶尔看看II
 群组: 2014美赛MCMA题备战群 群组: 2014美赛MCMB题备战群 |
Solovag-Strasson , j- c! ^# H; [6 u1 h* J
Robert Solovag和Volker Strasson开发了一种概率的基本测试算法。这个算法使用了雅可比函数来测试p是否为素数: 1 O; E/ z6 [3 j+ J
" G \ Q2 r0 m7 I( h
(1) 选择一个小于p的随机数a。 ; q9 h* W" u0 {( k8 ~. ?
(2) 如果GCD(a,p)<>1,那么p通不过测试,它是合数。
. q9 i1 U; b" }2 s& y. c(3) 计算j=a^(p-1)/2 mod p。 - \0 G) T+ e) \2 B9 @
(4) 计算雅可比符号J(a,p)。 " W! i' o2 t9 ?1 o
(5) 如果j<>J(a,p),那么p肯定不是素数。 # h4 ?1 {: k1 U0 s8 n
(6) 如果j=J(a,p),那麽p不是素数的可能性值多是50%
' `8 i* t0 V" n" y) r+ O. K% L' v* e
数a被称为一个证据,如果a不能确定p,p肯定不是素数。如果p是合数。随机数a是证据的概率不小于50%。对a选择t个不同的随机值,重复t次这种测试。p通过所有t次测试后,它是合数的可能性不超过1/2^t。 ' V& A! w4 n9 x# w8 k; l2 {
1 ^# a3 X. p( r/ a" `Lehmann . m7 U( H: ?' Z, U. q6 Y m
另一种更简单的测试是由Lehmann独自研究的。下面是它的测试算法: * X6 @% E5 G+ b1 u; O+ p
# w+ C. w% O: ?0 _" z( J
(1) 选择一个小于p的随机数a。 $ j8 A, P1 I' y5 B. @+ _) `6 @6 C
(2) 计算a^(p-1)/2 mod p 3 U7 `! m: S0 J) ^5 ?5 [( }
(3) 如果a^(p-1)/2<>1或-1(mod p),那么p肯定不是素数。 4 I, q- ?# c/ |1 L& T
(4) 如果a^(p-1)/2=1或-1(mod p),那麽p不是素数的可能性值多是50% 2 c0 @- M& y: E+ S5 J2 m0 h
3 Q$ E# M6 P9 T0 \0 f# L同样,重复t次,那麽p可能是素数所冒的错误风险不超过1/2^t。 9 P- z4 ~: }; Q+ Q: ^: _; L
. h# B, [+ @6 b, oRabin-Miller
9 A% z! Z y) d) I7 J/ a6 I这是个很容易且广泛使用的简单算法,它基于Gary Miller的部分象法,有Michael Rabin发展。事实上,这是在NIST的DSS建议中推荐的算法的一个简化版。
* Z" N5 Y3 _5 D4 K* h( ~8 J V2 j, h& h# N$ `" M) s7 ?
首先选择一个代测的随机数p,计算b,b是2整除p-1的次数。然后计算m,使得n=1+(2^b)m。 ; S/ i/ g5 c% x
, k8 P$ {; ?( I8 b5 e, b(1) 选择一个小于p的随机数a。 - R# K" R# n2 ?* Q' `; J5 T* ^% x
(2) 设j=0且z=a^m mod p
9 G( _: ], _/ B# O9 I, K& C6 i(3) 如果z=1或z=p-1,那麽p通过测试,可能使素数 % |8 b1 A& M; P a" T$ ? {
(4) 如果j>0且z=1, 那麽p不是素数
+ ]/ y; |. K( r0 @8 ^! X7 K(5) 设j=j+1。如果j<b且z<>p-1,设z=z^2 mod p,然后回到(4)。如果z=p-1,那麽p通过测试,可能为素数。 ) |# O+ \" M& [( t9 b
(6) 如果j=b 且z<>p-1,不是素数 $ Y0 S: {7 S8 D7 T) \( j B
/ [; v. ]. X- A2 q1 i" }5 J- Z% L
这个测试较前一个速度快。数a被当成证据的概率为75%。这意味着当迭代次数为t时,它产生一个假的素数所花费的时间不超过1/4^t。实际上,对大多数随机数,几乎99.99%肯定a是证据。
8 y/ x4 E! s) \5 {6 a; w: U5 B- Y: l( t
实际考虑:
, _1 z( M$ S7 q6 [" u! [6 h在实际算法,产生素数是很快的。
3 Y0 D; A7 \1 [, q% p, z3 \7 k, g" S: F- _( Y
(1) 产生一个n-位的随机数p
' n4 i6 J1 \* V# J/ W( D(2) 设高位和低位为1(设高位是为了保证位数,设低位是为了保证位奇数)
6 d; G) ?; t" ?' ~' x' o d(3) 检查以确保p不能被任何小素数整除:如3,5,7,11等等。有效的方法是测试小于2000的素数。使用字轮方法更快 % R+ o9 e ~) m0 @2 r4 l& ^
(4) 对某随机数a运行Rabin-Miller检测,如果p通过,则另外产生一个随机数a,在测试。选取较小的a值,以保证速度。做5次 Rabin-Miller测试如果p在其中失败,从新产生p,再测试。 ) Z( ]3 U b5 T; _4 N" E' }6 W
! s) f6 u: @" Y3 l
3 z5 M1 h4 Y* C/ j6 ^
在Sparc II上实现: 2 .8秒产生一个256位的素数 $ {2 V; j. k# F! L+ ]
24.0秒产生一个512位的素数 ) P5 H( J3 V, o3 f& W6 _
2分钟产生一个768位的素数 $ K) t; a1 Y7 e: B3 C9 @/ A
5.1分钟产生一个1024位的素数 |
zan
|