QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4085|回复: 0
打印 上一主题 下一主题

[转帖]产生素数的算法

[复制链接]
字体大小: 正常 放大
lckboy        

26

主题

1

听众

218

积分

升级  59%

  • TA的每日心情

    2014-2-22 20:49
  • 签到天数: 13 天

    [LV.3]偶尔看看II

    群组2014美赛MCMA题备战群

    群组2014美赛MCMB题备战群

    跳转到指定楼层
    1#
    发表于 2004-6-7 11:54 |只看该作者 |正序浏览
    |招呼Ta 关注Ta
    Solovag-Strasson # b0 d! j$ A7 A4 w" Z
    Robert Solovag和Volker Strasson开发了一种概率的基本测试算法。这个算法使用了雅可比函数来测试p是否为素数: / R! S4 @! r2 ]1 U$ \5 T+ g

    6 v7 o3 t% O- t! E(1) 选择一个小于p的随机数a。
    " a, ^7 M: S! C  @; b(2) 如果GCD(a,p)<>1,那么p通不过测试,它是合数。 / N4 B) v0 x0 S5 a
    (3) 计算j=a^(p-1)/2 mod p。 % W, Z" l% I! p7 ?* C* S
    (4) 计算雅可比符号J(a,p)。
    % i/ [$ ?' B& J/ F- ]4 G$ E(5) 如果j<>J(a,p),那么p肯定不是素数。 + V9 Y) b, z0 b. L% x
    (6) 如果j=J(a,p),那麽p不是素数的可能性值多是50%
    1 d. t9 H. x1 f+ ~: [5 X6 ~$ _: O% w- G
    数a被称为一个证据,如果a不能确定p,p肯定不是素数。如果p是合数。随机数a是证据的概率不小于50%。对a选择t个不同的随机值,重复t次这种测试。p通过所有t次测试后,它是合数的可能性不超过1/2^t。 ; n% A4 [9 |) f0 J8 S

    + r/ W: t0 Q5 xLehmann
    5 C# K' X9 a3 E3 M0 }7 y9 K" x另一种更简单的测试是由Lehmann独自研究的。下面是它的测试算法:
    3 p# a- `4 q9 y% ]3 d3 F, s( J. b& {. C
    ' `* P' {) n2 v/ W( x( `(1) 选择一个小于p的随机数a。 % r8 L& N. x1 z& v+ w. L
    (2) 计算a^(p-1)/2 mod p - X- |, l$ u4 Z4 D1 K  F
    (3) 如果a^(p-1)/2<>1或-1(mod p),那么p肯定不是素数。
    ' \* U. p0 v& t/ O(4) 如果a^(p-1)/2=1或-1(mod p),那麽p不是素数的可能性值多是50% 4 N3 ]' |4 ^# Z2 `5 t

    0 ~$ ]- [: }- ~6 D同样,重复t次,那麽p可能是素数所冒的错误风险不超过1/2^t。 ! Q' L7 Z' c) D# j" m

    0 [3 j6 E4 ^' ~# ]  _$ s3 ~4 d1 D/ eRabin-Miller , c, w0 F1 A4 P4 O7 }' l
    这是个很容易且广泛使用的简单算法,它基于Gary Miller的部分象法,有Michael Rabin发展。事实上,这是在NIST的DSS建议中推荐的算法的一个简化版。 7 ~4 [, @. W$ N. @/ S/ Z

    2 h0 C+ {  q: |( [' B1 T3 _* ^首先选择一个代测的随机数p,计算b,b是2整除p-1的次数。然后计算m,使得n=1+(2^b)m。
    + m# y" a2 ^& ?! \! J0 M% d' w, w: k4 G3 j$ Z! |$ ^5 I6 E% ?
    (1) 选择一个小于p的随机数a。
    ; U& t; @( I0 m% H; ^4 ]" B(2) 设j=0且z=a^m mod p * v/ p2 T5 v# x+ w
    (3) 如果z=1或z=p-1,那麽p通过测试,可能使素数 ( X. ~: P7 V* J5 i5 B5 @1 j0 C0 H
    (4) 如果j>0且z=1, 那麽p不是素数 ! `0 @- O/ ]/ v0 E6 w) ]  V4 l; R- p
    (5) 设j=j+1。如果j<b且z<>p-1,设z=z^2 mod p,然后回到(4)。如果z=p-1,那麽p通过测试,可能为素数。
    1 M4 }- h% s; R, z(6) 如果j=b 且z<>p-1,不是素数
    ; v5 L8 G5 t0 L" S8 \* v
    / w3 X6 C* J. C+ q+ D/ g' e这个测试较前一个速度快。数a被当成证据的概率为75%。这意味着当迭代次数为t时,它产生一个假的素数所花费的时间不超过1/4^t。实际上,对大多数随机数,几乎99.99%肯定a是证据。 # t2 W& Z5 r! W& l7 g' L' e

    : f/ `; Q+ |/ c; ~1 t* F实际考虑:
      o- ^2 g7 I: [9 H5 X5 {* u在实际算法,产生素数是很快的。
    , i9 P, g6 s" y6 @. n; `8 A3 L
    0 }% u2 i5 W, H  Q(1) 产生一个n-位的随机数p
    4 X' x9 E% x: k# ]2 _(2) 设高位和低位为1(设高位是为了保证位数,设低位是为了保证位奇数)
    $ {: i4 J! ?, {4 V" U6 a! W$ ~(3) 检查以确保p不能被任何小素数整除:如3,5,7,11等等。有效的方法是测试小于2000的素数。使用字轮方法更快
    9 J% G' L# j+ {9 {2 a* N' I(4) 对某随机数a运行Rabin-Miller检测,如果p通过,则另外产生一个随机数a,在测试。选取较小的a值,以保证速度。做5次 Rabin-Miller测试如果p在其中失败,从新产生p,再测试。 , r; R2 M2 o5 {( w
    1 x; D  Z, h  Q9 N& X; l" i- Y
    ) z6 b9 U  W  y4 A( k  _. H% v( {% ]
    在Sparc II上实现: 2 .8秒产生一个256位的素数 ' W) F. v+ J* n
    24.0秒产生一个512位的素数
      j' b& y' x0 h  T$ @% ?, A2分钟产生一个768位的素数 , P; R  K, X) s& g0 s' b2 p
    5.1分钟产生一个1024位的素数
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-20 21:11 , Processed in 0.408122 second(s), 51 queries .

    回顶部