注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TOTO

Think and Be Different

 
 
 

日志

 
 

Rabin-Miller Strong Pseudoprime Test[zz]  

2006-12-24 14:08:32|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Rabin-Miller Strong Pseudoprime Test
COMMENT On this Page

A primality test that provides an efficient probabilistic algorithm for determining if a given number is prime. It is based on the properties of strong pseudoprimes.

The algorithm proceeds as follows. Given an odd integer n, let n==2^rs+1 with s odd. Then choose a random integer a with 1<=a<=n-1. If a^s=1 (mod n) or a^(2^js)=-1 (mod n) for some 0<=j<=r-1, then n passes the test. A prime will pass the test for all a.

The test is very fast and requires no more than (1+o(1))lgn multiplications (mod n), where lg is the logarithm base 2. Unfortunately, a number which passes the test is not necessarily prime. Monier (1980) and Rabin (1980) have shown that a composite number passes the test for at most 1/4 of the possible bases a. If N multiple independent tests are performed on a composite number, then the probability that it passes each test is 1/4^N or less.

However, if the smallest composite number that passes a particular set of tests is known ahead of time, then that set of tests constitutes a primality proof for all smaller numbers. The sequence of smallest odd numbers passing a multiple Rabin-Miller test using the first k primes for k==1, 2, ... is given by 2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383 341550071728321, 341550071728321, ... (Sloane's A014233; Jaeschke 1993). Therefore, multiple Rabin tests using the first 7 primes (using 8 gives no improvement) are valid for every number up to 3.4x10^(14).

Mathematica versions 2.2 and later have implemented the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test as the primality test used by the function PrimeQ[n]. As of 1997, this procedure is known to be correct only for all n<10^(16), but no counterexamples are known and if any exist, they are expected to occur with extremely small probability (i.e., much less than the probability of a hardware error on a computer performing the test).

SEE ALSO: Baillie-PSW Primality Test, Lucas-Lehmer Test, Miller's Primality Test, Primality Test, Pseudoprime, Strong Pseudoprime. [Pages Linking Here]

REFERENCES:

Arnault, F. "Rabin-Miller Primality Test: Composite Numbers Which Pass It." Math. Comput. 64, 355-361, 1995.

Crandall, R. and Pomerance, C. Prime Numbers. New York: Springer-Verlag, 2001.

Damg?rd, I.; Landrock, P.; and Pomerance, C. "Average Case Error Estimates for the Strong Probably Prime Test." Math. Comput. 61, 177-194, 1993.

Jaeschke, G. "On Strong Pseudoprimes to Several Bases." Math. Comput. 61, 915-926, 1993.

Miller, G. "Riemann's Hypothesis and Tests for Primality." J. Comp. Syst. Sci. 13, 300-317, 1976.

Monier, L. "Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms." Theor. Comput. Sci. 12, 97-108, 1980.

Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. "The Pseudoprimes to 25.10^9." Math. Comput. 35, 1003-1026, 1980. http://mpqs.free.fr/ThePseudoprimesTo25e9.pdf.

Rabin, M. O. "Probabilistic Algorithm for Testing Primality." J. Number Th. 12, 128-138, 1980.

Sloane, N. J. A. Sequence A014233 in "The On-Line Encyclopedia of Integer Sequences."

Wagon, S. "Primality Testing." Math. Intell. 8, No. 3, 58-61, 1986.

Wagon, S. Mathematica in Action. New York: W. H. Freeman, pp. 15-17, 1991.



LAST MODIFIED: May 5, 2006

CITE THIS AS:

Weisstein, Eric W. "Rabin-Miller Strong Pseudoprime Test." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

  评论这张
 
阅读(349)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017