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

单词

Strong Pseudoprime

释义

Strong Pseudoprime

A strong pseudoprime to a base is an Odd Composite Number with (for Odd) forwhich either

(1)

(2)

for some

The definition is motivated by the fact that a Fermat Pseudoprime to the base satisfies

(3)

But since

is Odd, it can be written

, and

(4)

is Prime, it must Divide at least one of the Factors, but can't Divide both becauseit would then Divide their difference

(5)

Therefore,

(6)

so write

to obtain

(7)

If Divides exactly one of these Factors but is Composite, it is a strongpseudoprime. A Composite number is a strong pseudoprime to at most 1/4 of all bases less than itself (Monier 1980, Rabin1980). The strong pseudoprimes provide the basis for Miller's Primality Test and Rabin-Miller Strong PseudoprimeTest.

A strong pseudoprime to the base is also an Euler Pseudoprime to the base (Pomerance et al. 1980). The strongpseudoprimes include some Euler Pseudoprimes, Fermat Pseudoprimes,and Carmichael Numbers.

There are 4842 strong psp(2) less than , where a psp(2) is also known as a Poulet Number. Thestrong -pseudoprime test for , 3, 5 correctly identifies all Primes below with only 13exceptions, and if 7 is added, then the only exception less than is 315031751. Jaeschke (1993) showedthat there are only 101 strong pseudoprimes for the bases 2, 3, and 5 less than , nine if 7 is added, and none if 11is added. Also, the bases 2, 13, 23, and 1662803 have no exceptions up to .

If is Composite, then there is a base for which is not a strong pseudoprime. There are therefore no ``strongCarmichael Numbers.'' Let denote the smallest strong pseudoprime to all of the first Primes taken as bases (i.e, the smallest Odd Number for which the Rabin-Miller Strong Pseudoprime Test onbases less than or equal to fails). Jaeschke (1993) computed from to 8 and gave upper bounds for to11.

(Sloane's A014233). A seven-step test utilizing these results (Riesel 1994) allows all numbers less than

to betested.

Pomerance et al. (1980) have proposed a test based on a combination of Strong Pseudoprimes andLucas Pseudoprimes. They offer a $620 reward for discovery of a Composite Number whichpasses their test (Guy 1994, p. 28).

See also Carmichael Number, Miller's Primality Test, Poulet Number, Rabin-Miller Strong PseudoprimeTest, Rotkiewicz Theorem, Strong Elliptic Pseudoprime, Strong Lucas Pseudoprime

References

Baillie, R. and Wagstaff, S. ``Lucas Pseudoprimes.'' Math. Comput. 35, 1391-1417, 1980.

Guy, R. K. ``Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes.'' §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.

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

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 .'' Math. Comput. 35, 1003-1026, 1980. Available electronically from ftp://sable.ox.ac.uk/pub/math/primes/ps2.Z.

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

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Basel: Birkhäuser, p. 92, 1994.

Sloane, N. J. A. Sequence A014233in ``The On-Line Version of the Encyclopedia of Integer Sequences.''http://www.research.att.com/~njas/sequences/eisonline.html.

随便看

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