Skip to main content

Strong pseudoprime









Strong pseudoprime


From Wikipedia, the free encyclopedia

Jump to navigation
Jump to search


In number theory, a probable prime is a number that passes a primality test.
A strong probable prime is a number that passes a strong version of a primality test.
A strong pseudoprime is a composite number that passes a strong version of a primality test.
All primes pass these tests, but a small fraction of composites also pass, making them "false primes".


Unlike the Fermat pseudoprimes, for which there exist numbers that are pseudoprimes to all coprime bases (the Carmichael numbers), there are no composites that are strong pseudoprimes to all bases.




Contents






  • 1 Formal definition


  • 2 Properties of strong pseudoprimes


  • 3 Examples


  • 4 Smallest strong pseudoprime to base n


  • 5 References





Formal definition[edit]


An odd composite number n = d · 2s + 1 where d is odd is called a strong (Fermat) pseudoprime to base a when one of the following conditions holds:


ad≡1(modn){displaystyle a^{d}equiv 1{pmod {n}}}{displaystyle a^{d}equiv 1{pmod {n}}}

or


ad⋅2r≡−1(modn) for some 0≤r<s.{displaystyle a^{dcdot 2^{r}}equiv -1{pmod {n}}quad {mbox{ for some }}0leq r<s.}{displaystyle a^{dcdot 2^{r}}equiv -1{pmod {n}}quad {mbox{ for some }}0leq r<s.}

(If a number n satisfies one of the above conditions and we don't yet know whether it is prime, it is more precise to refer to it as a strong probable prime to base a. But if we know that n is not prime, then one may use the term strong pseudoprime.)


The definition is trivially met if a ≡ ±1 (mod n) so these trivial bases are often excluded.


Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes.[1]



Properties of strong pseudoprimes[edit]


A strong pseudoprime to base a is always an Euler–Jacobi pseudoprime, an Euler pseudoprime [2] and a Fermat pseudoprime to that base, but not all Euler and Fermat pseudoprimes are strong pseudoprimes. Carmichael numbers may be strong pseudoprimes to some bases—for example, 561 is a strong pseudoprime to base 50—but not to all bases.


A composite number n is a strong pseudoprime to at most one quarter of all bases below n;[3][4] thus, there are no "strong Carmichael numbers", numbers that are strong pseudoprimes to all bases. Thus given a random base, the probability that a number is a strong pseudoprime to that base is less than 1/4, forming the basis of the widely used Miller–Rabin primality test.
However, Arnault
[5]
gives a 397-digit composite number that is a strong pseudoprime to every base less than 307.
One way to prevent such a number from wrongfully being declared probably prime is to combine a strong probable prime test with a Lucas probable prime test, as in the Baillie–PSW primality test.


There are infinitely many strong pseudoprimes to any base.[2]



Examples[edit]


The first strong pseudoprimes to base 2 are


2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ... (sequence A001262 in the OEIS).

The first to base 3 are


121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, ... (sequence A020229 in the OEIS).

The first to base 5 are


781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... (sequence A020231 in the OEIS).

For base 4, see OEIS: A020230, and for base 6 to 100, see OEIS: A020232 to OEIS: A020326.
By testing the above conditions to several bases, one gets somewhat more powerful primality tests than by using one base alone.
For example, there are only 13 numbers less than 25·109 that are strong pseudoprimes to bases 2, 3, and 5 simultaneously.
They are listed in Table 7 of.[2] The smallest such number is 25326001.
This means that, if n is less than 25326001 and n is a strong probable prime to bases 2, 3, and 5, then n is prime.


Carrying this further, 3825123056546413051 is the smallest number that is a strong pseudoprime to the 9 bases 2, 3, 5, 7, 11, 13, 17, 19, and 23.[6][7]
So, if n is less than 3825123056546413051 and n is a strong probable prime to these 9 bases, then n is prime.


By judicious choice of bases that are not necessarily prime, even better tests can be constructed. For example, there is no composite <264{displaystyle <2^{64}}{displaystyle <2^{64}} that is a strong pseudoprime to all of the seven bases 2, 325, 9375, 28178, 450775, 9780504, and 1795265022.[8]



Smallest strong pseudoprime to base n[edit]














































































































































































































































































































































n
 Least SPSP
n
 Least SPSP
n
 Least SPSP
n
 Least SPSP
1
 9
 33
 545
 65
 33
 97
 49
2
 2047
 34
 33
 66
 65
 98
 9
3
 121
 35
 9
 67
 33
 99
 25
4
 341
 36
 35
 68
 25
 100
 9
5
 781
 37
 9
 69
 35
 101
 25
6
 217
 38
 39
 70
 69
 102
 133
7
 25
 39
 133
 71
 9
 103
 51
8
 9
 40
 39
 72
 85
 104
 15
9
 91
 41
 21
 73
 9
 105
 451
10
 9
 42
 451
 74
 15
 106
 15
11
 133
 43
 21
 75
 91
 107
 9
12
 91
 44
 9
 76
 15
 108
 91
13
 85
 45
 481
 77
 39
 109
 9
14
 15
 46
 9
 78
 77
 110
 111
15
 1687
 47
 65
 79
 39
 111
 55
16
 15
 48
 49
 80
 9
 112
 65
17
 9
 49
 25
 81
 91
 113
 57
18
 25
 50
 49
 82
 9
 114
 115
19
 9
 51
 25
 83
 21
 115
 57
20
 21
 52
 51
 84
 85
 116
 9
21
 221
 53
 9
 85
 21
 117
 49
22
 21
 54
 55
 86
 85
 118
 9
23
 169
 55
 9
 87
 247
 119
 15
24
 25
 56
 55
 88
 87
 120
 91
25
 217
 57
 25
 89
 9
 121
 15
26
 9
 58
 57
 90
 91
 122
 65
27
 121
 59
 15
 91
 9
 123
 85
28
 9
 60
 481
 92
 91
 124
 25
29
 15
 61
 15
 93
 25
 125
 9
30
 49
 62
 9
 94
 93
 126
 25
31
 15
 63
 529
 95
 1891
 127
 9
32
 25
 64
 9
 96
 95
 128
 49


References[edit]





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


  2. ^ abc Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·109" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}


  3. ^
    Louis Monier (1980). "Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms". Theoretical Computer Science. 12: 97–108. doi:10.1016/0304-3975(80)90007-9.


  4. ^ Rabin, Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 12 pp. 128-138, 1980.


  5. ^ F. Arnault (August 1995). "Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases". Journal of Symbolic Computation. 20 (2): 151–161. doi:10.1006/jsco.1995.1042.


  6. ^
    Zhenxiang Zhang; Min Tang (2003). "Finding Strong Pseudoprimes to Several Bases. II". Mathematics of Computation. 72 (244): 2085–2097. doi:10.1090/S0025-5718-03-01545-X.


  7. ^
    Jiang, Yupeng; Deng, Yingpu (2012). "Strong pseudoprimes to the first 9 prime bases". arXiv:1207.0063v1 [math.NT].


  8. ^ "SPRP Records". Retrieved 3 June 2015.












Retrieved from "https://en.wikipedia.org/w/index.php?title=Strong_pseudoprime&oldid=865771015"





Navigation menu

























(window.RLQ=window.RLQ||).push(function(){mw.config.set({"wgPageParseReport":{"limitreport":{"cputime":"0.316","walltime":"0.436","ppvisitednodes":{"value":776,"limit":1000000},"ppgeneratednodes":{"value":0,"limit":1500000},"postexpandincludesize":{"value":88916,"limit":2097152},"templateargumentsize":{"value":571,"limit":2097152},"expansiondepth":{"value":7,"limit":40},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":17338,"limit":5000000},"entityaccesscount":{"value":2,"limit":400},"timingprofile":["100.00% 262.209 1 -total"," 72.73% 190.706 1 Template:Reflist"," 55.08% 144.427 4 Template:Cite_journal"," 24.13% 63.279 7 Template:Navbox"," 17.78% 46.623 1 Template:Classes_of_natural_numbers"," 6.19% 16.242 1 Template:Cite_arXiv"," 3.57% 9.358 1 Template:Icon"," 2.70% 7.069 1 Template:Cite_web"," 2.46% 6.453 3 Template:OEIS"," 2.10% 5.501 3 Template:Oeis"]},"scribunto":{"limitreport-timeusage":{"value":"0.145","limit":"10.000"},"limitreport-memusage":{"value":3523083,"limit":52428800}},"cachereport":{"origin":"mw1319","timestamp":"20181125225922","ttl":1900800,"transientcontent":false}}});mw.config.set({"wgBackendResponseTime":84,"wgHostname":"mw1262"});});
-

Popular posts from this blog

Florida Star v. B. J. F.

Image
Florida Star v. B. J. F. From Wikipedia, the free encyclopedia Jump to navigation Jump to search United States Supreme Court case Florida Star v. B. J. F. Supreme Court of the United States Argued March 21, 1989 Decided June 21, 1989 Full case name The Florida Star v. B. J. F. Citations 491 U.S. 524 ( more ) 109 S. Ct. 2603; 105 L. Ed. 2d 443; 1989 U.S. LEXIS 3120; 57 U.S.L.W. 4816; 16 Media L. Rep. 1801 Prior history The Florida Star v. B.J.F., 530 So.2d 286 (1988) Supreme Court of Florida; Florida Star v. B.J.F., 499 So.2d 883 (1986) Fla. Dist. Court of Appeals Holding Florida Stat. § 794.03 is unconstitutional to the extent it makes the truthful reporting of information that was a matter of public record unlawful, as it violates the First Amendment. Court membership Chief Justice William Rehnquist Associate Justices William J. Brennan Jr.  · Byron White Thurgood Marshall  · Harry Blac...
Read more

Danny Elfman

Image
Danny Elfman From Wikipedia, the free encyclopedia Jump to navigation Jump to search Danny Elfman Elfman at the 2010 San Diego Comic-Con Born Daniel Robert Elfman ( 1953-05-29 ) May 29, 1953 (age 65) Los Angeles, California, U.S. Spouse(s) Bridget Fonda ( m.  2003) Children 1 Musical career Genres Rock [1] ska [2] new wave film music video game music Occupation(s) Composer, singer, songwriter, record producer Instruments Trombone guitar percussion vocals keyboards [3] Years active 1972–present Associated acts Oingo Boingo James Newton Howard Daniel Robert Elfman (born May 29, 1953) is an American composer, singer, songwriter, and record producer. Elfman first became known for being the lead singer and songwriter for the band Oingo Boingo from 1974 to 1995. He is well known for scoring films and television shows, particularly his frequent collabora...
Read more

Lugert, Oklahoma

Image
Unincorporated community in Oklahoma, United States Lugert, Oklahoma Unincorporated community Foundations from the town of Lugert at the bottom of Lake Altus-Lugert Lugert, Oklahoma Location within the state of Oklahoma Coordinates: 34°53′45″N 99°16′31″W  /  34.89583°N 99.27528°W  / 34.89583; -99.27528 Coordinates: 34°53′45″N 99°16′31″W  /  34.89583°N 99.27528°W  / 34.89583; -99.27528 Country United States State Oklahoma County Kiowa Time zone UTC-6 (Central (CST))  • Summer (DST) UTC-5 (CDT) GNIS feature ID 1100597 Lugert is an unincorporated community in Kiowa County, Oklahoma. [1] The town of Lugert was founded in 1901 on 80 acres (320,000 m 2 ). In the town, there was a general store that housed the Post office and sold dry goods, school supplies, groceries, harnesses, axes and much more. It was named for Frank Lugert, who had moved to the area in 1898. Lugert owned land where the town was sited and also owned the general st...
Read more