Read More
Date: 1-12-2019
1020
Date: 12-7-2020
1350
Date: 20-2-2020
574
|
A strong pseudoprime to a base is an odd composite number with (for odd) for which either
(1) |
or
(2) |
for some , 1, ..., (Riesel 1994, p. 91). Note that Guy (1994, p. 27) restricts the definition of strong pseudoprimes to only those satisfying (1).
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) |
If is prime, it must divide at least one of the factors, but can't divide both because it 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 strong pseudoprime. A composite number is a strong pseudoprime to at most 1/4 of all bases less than itself (Monier 1980, Rabin 1980). The strong pseudoprimes provide the basis for Miller's primality test and Rabin-Miller strong pseudoprime test.
A strong pseudoprime to the base is also an Euler pseudoprime to the base (Pomerance et al. 1980). The strong pseudoprimes include some Euler pseudoprimes, Fermat pseudoprimes, and Carmichael numbers.
The following table lists the first few pseudoprimes to a number of small bases.
OEIS | -strong pseudoprimes | |
2 | A001262 | 2047, 3277, 4033, 4681, 8321, ... |
3 | A020229 | 121, 703, 1891, 3281, 8401, 8911, ... |
4 | A020230 | 341, 1387, 2047, 3277, 4033, 4371, ... |
5 | A020231 | 781, 1541, 5461, 5611, 7813, ... |
6 | A020232 | 217, 481, 1111, 1261, 2701, ... |
7 | A020233 | 25, 325, 703, 2101, 2353, 4525, ... |
8 | A020234 | 9, 65, 481, 511, 1417, 2047, ... |
9 | A020235 | 91, 121, 671, 703, 1541, 1729, ... |
The number of strong 2-pseudoprimes less than , , ... are 0, 5, 16, 46, 162, ... (OEIS A055552). Note that Guy's (1994, p. 27) definition gives only the subset 2047, 4681, 15841, 42799, 52633, 90751, ..., giving counts inconsistent with those in Guy's table.
The strong -pseudoprime test for , 3, 5 correctly identifies all primes below with only 13 exceptions, and if 7 is added, then the only exception less than is 3215031751. Jaeschke (1993) showed that there are only 101 strong pseudoprimes for the bases 2, 3, and 5 less than , nine if 7 is added, and none if 11 is 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 "strong Carmichael 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 on bases less than or equal to the th prime fails). Jaeschke (1993) computed from to 8 and gave upper bounds for to 11.
(8) |
|||
(9) |
|||
(10) |
|||
(11) |
|||
(12) |
|||
(13) |
|||
(14) |
|||
(15) |
|||
(16) |
|||
(17) |
|||
(18) |
(OEIS A014233), where the bounds for , , and were determined by Zhang and Tang (2003). A seven-step test utilizing older bounds on these results (Riesel 1994) allows all numbers less than to be tested.
Zhang (2001, 2002, 2005, 2006, 2007) conjectured that
(19) |
|||
(20) |
|||
(21) |
|||
(22) |
|||
(23) |
|||
(24) |
|||
(25) |
|||
(26) |
|||
(27) |
|||
(28) |
|||
(29) |
|||
(30) |
The Baillie-PSW primality test is a test based on a combination of strong pseudoprimes and Lucas pseudoprimes proposed by Pomerance et al. (Pomerance et al. 1980, Pomerance 1984).
REFERENCES:
Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; and Moll, V. H. Experimental Mathematics in Action. Wellesley, MA: A K Peters, p. 57, 2007.
Baillie, R. and Wagstaff, S. "Lucas Pseudoprimes." Math. Comput. 35, 1391-1417, 1980. https://mpqs.free.fr/LucasPseudoprimes.pdf.
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.
Pinch, R. G. E. "The Pseudoprimes Up to ." ftp://ftp.dpmms.cam.ac.uk/pub/PSP/.
Pomerance, C. "Are There Counterexamples to the Baillie-PSW Primality Test?" 1984. https://www.pseudoprime.com/dopo.pdf.
Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. "The Pseudoprimes to ." Math. Comput. 35, 1003-1026, 1980. https://mpqs.free.fr/ThePseudoprimesTo25e9.pdf.
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. Sequences A001262, A014233, A020229, A020230, A020231, A020232, A020233, A020234, A020235, A055552, and A102483 in "The On-Line Encyclopedia of Integer Sequences."
Zhang, Z. "Finding Strong Pseudoprimes to Several Bases." Math. Comput. 70, 863-872, 2001. https://www.ams.org/journal-getitem?pii=S0025-5718-00-01215-1.
Zhang, Z. "A One-Parameter Quadratic-Base Version of the Baillie-PSW Probable Prime Test." Math. Comput. 71, 1699-1734, 2002. https://www.ams.org/journal-getitem?pii=S0025-5718-02-01424-2.
Zhang, Z. "Finding -Strong Pseudoprimes." Math. Comput. 74, 1009-1024, 2005. https://www.ams.org/mcom/2005-74-250/S0025-5718-04-01693-X/home.html.
Zhang, Z. "Notes on Some New Kinds of Pseudoprimes." Math. Comput. 75, 451-460, 2006.
Zhang, Z. "Two Kinds of Strong Pseudoprimes up to ." Math. Comput. 76, 2095-2107, 2007.
Zhang, Z. and Tang, M. "Finding Strong Pseudoprimes to Several Bases, II." Math. Comput. 72, 2085-2097, 2003. https://www.ams.org/journal-getitem?pii=S0025-5718-03-01545-X.
|
|
علامات بسيطة في جسدك قد تنذر بمرض "قاتل"
|
|
|
|
|
أول صور ثلاثية الأبعاد للغدة الزعترية البشرية
|
|
|
|
|
وفد كلية الزراعة في جامعة كربلاء يشيد بمشروع الحزام الأخضر
|
|
|