数学建模社区-数学中国
标题:
[转帖]产生素数的算法
[打印本页]
作者:
lckboy
时间:
2004-6-7 11:54
标题:
[转帖]产生素数的算法
Solovag-Strasson
+ a* a$ I1 D( F0 H1 `/ [
Robert Solovag和Volker Strasson开发了一种概率的基本测试算法。这个算法使用了雅可比函数来测试p是否为素数：
$ i6 J% K4 ^5 z0 a5 p
0 }: h; _0 r4 K, ~* T0 Y% J- W2 r
（1） 选择一个小于p的随机数a。
6 R4 k" H2 N0 g( l9 m0 F% |
（2） 如果GCD（a,p）<>1，那么p通不过测试，它是合数。
- ]5 J& V* l. P2 b% U
（3） 计算j=a^(p-1)/2 mod p。
6 ~1 t x3 g& x8 c e' O
（4） 计算雅可比符号J（a,p）。
% F; U2 S3 C0 _0 Q8 Y
（5） 如果j<>J（a,p），那么p肯定不是素数。
# h1 o0 \/ d. d
（6） 如果j=J(a,p),那麽p不是素数的可能性值多是50%
: I+ N" i; b. x, z1 }- z% N
) g8 f* [0 X a4 \( ], p) `
数a被称为一个证据，如果a不能确定p，p肯定不是素数。如果p是合数。随机数a是证据的概率不小于50%。对a选择t个不同的随机值，重复t次这种测试。p通过所有t次测试后，它是合数的可能性不超过1/2^t。
. ?- f4 b! [" o% O1 d
: k- S' N. m z
Lehmann
& x4 [1 B- x- @: d# z
另一种更简单的测试是由Lehmann独自研究的。下面是它的测试算法：
, [( d% X- z+ d% @) H( e: H" {
! s, e7 o' q1 j$ g6 \4 s: K
（1） 选择一个小于p的随机数a。
4 `9 q# R! m- ]; w! E
（2） 计算a^(p-1)/2 mod p
C' `0 ]& y: [7 t
（3） 如果a^(p-1)/2<>1或-1（mod p），那么p肯定不是素数。
3 {) H& i( r0 u1 K" Y2 ?
（4） 如果a^(p-1)/2=1或-1（mod p），那麽p不是素数的可能性值多是50%
. e. n* `# L1 l4 g' ]
* p. @! G' s9 h% b% ?
同样，重复t次，那麽p可能是素数所冒的错误风险不超过1/2^t。
5 w0 D) s3 k) D6 [# W' o* C- p7 G# {
J$ D! y% d# \ M; D K) ]
Rabin-Miller
# b% \4 A+ y! N+ b1 b$ x
这是个很容易且广泛使用的简单算法，它基于Gary Miller的部分象法，有Michael Rabin发展。事实上，这是在NIST的DSS建议中推荐的算法的一个简化版。
: X5 d& l4 l- }+ w% f( L/ T/ u
! X8 s- R. f% d0 s7 `1 \- C9 _5 w9 `
首先选择一个代测的随机数p，计算b，b是2整除p-1的次数。然后计算m，使得n=1+(2^b)m。
$ `/ A3 n8 ^3 x* H3 M8 c
4 |, @" o. b4 G5 R
（1） 选择一个小于p的随机数a。
* T: K3 R8 w$ a M4 R$ L' S# J W/ i6 l, E
（2） 设j=0且z=a^m mod p
2 n* }% Q6 A# F; x4 d- d
（3） 如果z=1或z=p-1，那麽p通过测试，可能使素数
7 g6 _. S+ H9 }0 H
（4） 如果j>0且z=1, 那麽p不是素数
) H1 T/ r \# _- D1 T# a
（5） 设j=j+1。如果j<b且z<>p-1,设z=z^2 mod p，然后回到(4)。如果z=p-1，那麽p通过测试，可能为素数。
' N9 X. t8 \! \. W% x( D' J0 i
（6） 如果j=b 且z<>p-1，不是素数
3 D8 E% l" @: X+ K
- M. Y1 f) B4 E' S N) o. Z& T
这个测试较前一个速度快。数a被当成证据的概率为75%。这意味着当迭代次数为t时，它产生一个假的素数所花费的时间不超过1/4^t。实际上，对大多数随机数，几乎99.99%肯定a是证据。
) g* L0 e e6 G, J" y: T- v! X
/ H4 o* b( T4 x
实际考虑：
7 {% E" D7 T) {6 M2 H$ l" e
在实际算法，产生素数是很快的。
1 j: Z- r6 F; [2 _4 n, w
7 l- O' |) I3 D& I$ M$ p4 P
（1） 产生一个n-位的随机数p
8 J& g$ D5 P' P
（2） 设高位和低位为1（设高位是为了保证位数，设低位是为了保证位奇数）
1 V( M4 V4 m4 W/ J" A! H- Q
（3） 检查以确保p不能被任何小素数整除：如3，5，7，11等等。有效的方法是测试小于2000的素数。使用字轮方法更快
6 L! M) z2 z' u' z0 Z- S; m
（4） 对某随机数a运行Rabin-Miller检测，如果p通过，则另外产生一个随机数a,在测试。选取较小的a值，以保证速度。做5次 Rabin-Miller测试如果p在其中失败，从新产生p，再测试。
* p" G) M2 ^/ D! f0 c+ H& x' I
: q# ^* M) [ g
2 R" ^% v, i i0 G( Q
在Sparc II上实现： 2 .8秒产生一个256位的素数
! @( U, Y8 r! Y5 K: L2 B$ w
24.0秒产生一个512位的素数
0 g4 v7 }+ {% T
2分钟产生一个768位的素数
( J; w5 \1 Z2 E& Q. C& {, b
5.1分钟产生一个1024位的素数
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5