Namespaces
Variants
Actions

Difference between revisions of "Pseudo-prime"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(mention Fermat's little theorem)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Traditionally, a composite natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p1102701.png" /> is called a pseudo-prime if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p1102702.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p1102703.png" />, for it has long been known that primes have this property. (The term is apparently due to D.H. Lehmer.) There are infinitely many such <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p1102704.png" />, the first five being
+
{{TEX|done}}
 +
Traditionally, a composite natural number $n$ is called a pseudo-prime if $2^{n-1} \equiv 1$ modulo $n$, for it has long been known that primes have this property: this is [[Fermat's little theorem]]. (The term is apparently due to D.H. Lehmer.) There are infinitely many such $n$, the first five being
 +
$$
 +
341,\,561,\,645,\,1105,\,1387\ .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p1102705.png" /></td> </tr></table>
+
More recently, the concept has been extended to include any composite number that acts like a prime in some realization of a [[probabilistic primality test]]. That is, it satisfies some easily computable necessary, but not sufficient, condition for primality. Pseudo-primes in this larger sense include:
  
More recently, the concept has been extended to include any composite number that acts like a prime in some realization of a [[Probabilistic primality test|probabilistic primality test]]. That is, it satisfies some easily computable necessary, but not sufficient, condition for primality. Pseudo-primes in this larger sense include:
+
1) ordinary base-$b$ pseudo-primes, satisfying $b^{n-1}\equiv1$ modulo $n$;
  
1) ordinary base-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p1102707.png" /> pseudo-primes, satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p1102708.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p1102709.png" />;
+
2) Euler base-$b$ pseudo-primes, whose [[Jacobi symbol]] with $b$ satisfies
 +
$$
 +
b^{(n-1)/2} \equiv\left({\frac{b}{n}}\right) = \pm 1
 +
$$
  
2) Euler base-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027011.png" /> pseudo-primes, whose [[Jacobi symbol|Jacobi symbol]] with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027012.png" /> satisfies
+
3) strong base-$b$ pseudo-primes, for which the sequence $b^{s.2^i}$ modulo $n$ for $i=0,\ldots, r$ is either always $1$, or contains $-1$. (Here $n-1 = 2^r.s$ with $s$ odd.)
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027013.png" /></td> </tr></table>
+
For each $b$, the implications 3)$\Rightarrow$2)$\Rightarrow$1) hold. A number $n$ that is an ordinary base-$b$ pseudo-prime for all $b$ prime to $n$ is called a [[Carmichael number|Carmichael number]]. Analogous numbers for the other two categories do not exist.
 
 
3) strong base-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027015.png" /> pseudo-primes, for which the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027016.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027018.png" />, is either always <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027019.png" />, or contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027020.png" />. (Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027021.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027022.png" /> odd.)
 
 
 
For each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027023.png" />, the implications 3)<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027024.png" />2)<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027025.png" />1) hold. A number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027026.png" /> that is an ordinary base-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027027.png" /> pseudo-prime for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027028.png" /> prime to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027029.png" /> is called a [[Carmichael number|Carmichael number]]. Analogous numbers for the other two categories do not exist.
 
  
 
For a thorough empirical study of pseudo-primes, see [[#References|[a4]]]. Lists of pseudo-primes to various small bases can be found in [[#References|[a6]]].
 
For a thorough empirical study of pseudo-primes, see [[#References|[a4]]]. Lists of pseudo-primes to various small bases can be found in [[#References|[a6]]].
  
The concept of a pseudo-prime has been generalized to include primality tests based on finite fields and elliptic curves (cf. also [[Finite field|Finite field]]; [[Elliptic curve|Elliptic curve]]). For reviews of this work, see [[#References|[a3]]], [[#References|[a5]]].
+
The concept of a pseudo-prime has been generalized to include primality tests based on finite fields and elliptic curves (cf. also [[Finite field]]; [[Elliptic curve]]). For reviews of this work, see [[#References|[a3]]], [[#References|[a5]]].
  
The complementary concept is also of interest. The base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027030.png" /> is called a (Fermat) witness for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027031.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027032.png" /> is composite but not a base-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027033.png" /> pseudo-prime. Euler and strong witnesses are similarly defined. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027034.png" />, the smallest strong witness for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027035.png" />, grows sufficiently slowly, there is a polynomial-time algorithm for primality. It is known that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027036.png" /> is not bounded [[#References|[a2]]], but if an extended version of the Riemann hypothesis (cf. [[Riemann hypotheses|Riemann hypotheses]]) holds, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027037.png" /> [[#References|[a1]]].
+
The complementary concept is also of interest. The base $b$ is called a (Fermat) witness for $n$ if $n$ is composite and not a base-$b$ pseudo-prime. Euler and strong witnesses are similarly defined. If $W(n)$, the smallest strong witness for $n$, grows sufficiently slowly, there is a polynomial-time algorithm for primality. It is known that $W(n)$ is not bounded [[#References|[a2]]], but if an extended version of the Riemann hypothesis (cf. [[Riemann hypotheses|Riemann hypotheses]]) holds, then $W(n) \le 2(\log n)^2$ [[#References|[a1]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  E. Bach,  "Analytic methods in the analysis and design of number-theoretic algorithms" , MIT  (1985)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  W.R. Alford,  A. Granville,  C. Pomerance,  "On the difficulty of finding reliable witnesses" , ''Algorithmic Number Theory, First Internat. Symp., ANTS-I'' , ''Lecture Notes in Computer Science'' , '''877''' , Springer  (1994)  pp. 1–16</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  F. Morain,  "Pseudoprimes: a survey of recent results" , ''Proc. Eurocode '92'' , Springer  (1993)  pp. 207–215</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  C. Pomerance,  J.L. Selfridge,  S.S. Wagstaff, Jr.,  "The pseudoprimes to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110270/p11027038.png" />"  ''Math. Comp.'' , '''35'''  (1980)  pp. 1003–1026</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  P. Ribenboim,  "The book of prime number records" , Springer  (1989)  (Edition: Second)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  N.J.A. Sloane,  S. Plouffe,  "The encyclopedia of integer sequences" , Acad. Press  (1995)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  E. Bach,  "Analytic methods in the analysis and design of number-theoretic algorithms" , MIT  (1985)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  W.R. Alford,  A. Granville,  C. Pomerance,  "On the difficulty of finding reliable witnesses" , ''Algorithmic Number Theory, First Internat. Symp., ANTS-I'' , ''Lecture Notes in Computer Science'' , '''877''' , Springer  (1994)  pp. 1–16</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  F. Morain,  "Pseudoprimes: a survey of recent results" , ''Proc. Eurocode '92'' , Springer  (1993)  pp. 207–215</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  C. Pomerance,  J.L. Selfridge,  S.S. Wagstaff, Jr.,  "The pseudoprimes to $25\cdot10^9$"  ''Math. Comp.'' , '''35'''  (1980)  pp. 1003–1026.  Zbl 0444.10007.  DOI 10.2307/2006210</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  P. Ribenboim,  "The book of prime number records" , Springer  (1989)  (Edition: Second)</TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top">  N.J.A. Sloane,  S. Plouffe,  "The encyclopedia of integer sequences" , Acad. Press  (1995)</TD></TR>
 +
</table>
 +
 
 +
[[Category:Number theory]]

Latest revision as of 17:58, 8 November 2014

Traditionally, a composite natural number $n$ is called a pseudo-prime if $2^{n-1} \equiv 1$ modulo $n$, for it has long been known that primes have this property: this is Fermat's little theorem. (The term is apparently due to D.H. Lehmer.) There are infinitely many such $n$, the first five being $$ 341,\,561,\,645,\,1105,\,1387\ . $$

More recently, the concept has been extended to include any composite number that acts like a prime in some realization of a probabilistic primality test. That is, it satisfies some easily computable necessary, but not sufficient, condition for primality. Pseudo-primes in this larger sense include:

1) ordinary base-$b$ pseudo-primes, satisfying $b^{n-1}\equiv1$ modulo $n$;

2) Euler base-$b$ pseudo-primes, whose Jacobi symbol with $b$ satisfies $$ b^{(n-1)/2} \equiv\left({\frac{b}{n}}\right) = \pm 1 $$

3) strong base-$b$ pseudo-primes, for which the sequence $b^{s.2^i}$ modulo $n$ for $i=0,\ldots, r$ is either always $1$, or contains $-1$. (Here $n-1 = 2^r.s$ with $s$ odd.)

For each $b$, the implications 3)$\Rightarrow$2)$\Rightarrow$1) hold. A number $n$ that is an ordinary base-$b$ pseudo-prime for all $b$ prime to $n$ is called a Carmichael number. Analogous numbers for the other two categories do not exist.

For a thorough empirical study of pseudo-primes, see [a4]. Lists of pseudo-primes to various small bases can be found in [a6].

The concept of a pseudo-prime has been generalized to include primality tests based on finite fields and elliptic curves (cf. also Finite field; Elliptic curve). For reviews of this work, see [a3], [a5].

The complementary concept is also of interest. The base $b$ is called a (Fermat) witness for $n$ if $n$ is composite and not a base-$b$ pseudo-prime. Euler and strong witnesses are similarly defined. If $W(n)$, the smallest strong witness for $n$, grows sufficiently slowly, there is a polynomial-time algorithm for primality. It is known that $W(n)$ is not bounded [a2], but if an extended version of the Riemann hypothesis (cf. Riemann hypotheses) holds, then $W(n) \le 2(\log n)^2$ [a1].

References

[a1] E. Bach, "Analytic methods in the analysis and design of number-theoretic algorithms" , MIT (1985)
[a2] W.R. Alford, A. Granville, C. Pomerance, "On the difficulty of finding reliable witnesses" , Algorithmic Number Theory, First Internat. Symp., ANTS-I , Lecture Notes in Computer Science , 877 , Springer (1994) pp. 1–16
[a3] F. Morain, "Pseudoprimes: a survey of recent results" , Proc. Eurocode '92 , Springer (1993) pp. 207–215
[a4] C. Pomerance, J.L. Selfridge, S.S. Wagstaff, Jr., "The pseudoprimes to $25\cdot10^9$" Math. Comp. , 35 (1980) pp. 1003–1026. Zbl 0444.10007. DOI 10.2307/2006210
[a5] P. Ribenboim, "The book of prime number records" , Springer (1989) (Edition: Second)
[a6] N.J.A. Sloane, S. Plouffe, "The encyclopedia of integer sequences" , Acad. Press (1995)
How to Cite This Entry:
Pseudo-prime. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Pseudo-prime&oldid=16100
This article was adapted from an original article by E. Bach (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article