“Rabin-Miller Strong Pseudoprime Test”的概念、定义、习题解题方法及翻译-数学辞典

单词

Rabin-Miller Strong Pseudoprime Test

释义

Rabin-Miller Strong Pseudoprime Test

A Primality Test which provides an efficient probabilistic Algorithm for determining if a given number isPrime. It is based on the properties of Strong Pseudoprimes. Given an OddInteger , let with Odd. Then choose a random integer with . If or for some , then passes the test. A Prime will passthe test for all .

The test is very fast and requires no more than multiplications (mod ),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 possiblebases .

The Rabin-Miller test (combined with a Lucas Pseudoprime test) is the Primality Test used byMathematica versions 2.2 and later (Wolfram Research, Champaign, IL). As of 1991, the combined test had beenproven correct for all , but not beyond. The test potentially could therefore incorrectly identify a large Composite Number as Prime (but not vice versa). Strong Pseudoprime tests have been subsequentlyproved valid for every number up to .

See also Lucas-Lehmer Test, Miller's Primality Test, Pseudoprime, Strong Pseudoprime

References

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

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.

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

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

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。