Pseudoprime
Pseudoprime
Jump to navigation
Jump to search
A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.
Some sources use the term pseudoprime to describe all probable primes, both composite numbers and actual primes.
Pseudoprimes are of primary importance in public-key cryptography, which makes use of the difficulty of factoring large numbers into their prime factors. Carl Pomerance estimated in 1988 that it would cost $10 million to factor a number with 144 digits, and $100 billion to factor a 200-digit number (the cost today is dramatically cheaper but still prohibitively expensive).[1][2] However, finding and factoring the proper prime numbers for this use is correspondingly expensive, so various probabilistic primality tests are used to find primes among large numbers, some of which in rare cases incorrectly identify composite numbers as primes. On the other hand, deterministic primality tests, such as the AKS primality test, do not give false positives; there are no pseudoprimes with respect to them.
Fermat pseudoprimes[edit]
Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. For an integer a > 1, if a composite integer x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a. It follows that if x is a Fermat pseudoprime to base a, then x is coprime to a. Some sources use variations of this definition, for example to allow only odd numbers to be pseudoprimes.[3]
An integer x that is a Fermat pseudoprime to all values of a that are coprime to x is called a Carmichael number.
Classes[edit]
- Catalan pseudoprime
- Elliptic pseudoprime
- Euler pseudoprime
- Euler–Jacobi pseudoprime
- Fermat pseudoprime
- Frobenius pseudoprime
- Lucas pseudoprime
- Perrin pseudoprime
- Somer–Lucas pseudoprime
- Strong pseudoprime
References[edit]
^ Clawson, Calvin C. (1996). Mathematical Mysteries: The Beauty and Magic of Numbers. Cambridge: Perseus. p. 195. ISBN 0-7382-0259-2..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}
^ Cipra, Barry A. (December 23, 1988). "PCs Factor a 'Most Wanted' Number". Science. 242: 1634–1635. doi:10.1126/science.242.4886.1634. PMID 17730568.
^ Weisstein, Eric W. "Fermat Pseudoprime". MathWorld.
Prime number classes | |
|---|---|
| By formula |
|
| By integer sequence |
|
| By property |
|
Base-dependent |
|
| Patterns |
|
| By size |
|
| Complex numbers |
|
| Composite numbers |
|
| Related topics |
|
| First 60 primes |
|
List of prime numbers
| |
Classes of natural numbers | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Powers and related numbers |
| ||||||||||||||||||||
| Of the form a × 2b ± 1 |
| ||||||||||||||||||||
| Other polynomial numbers |
| ||||||||||||||||||||
Recursively defined numbers |
| ||||||||||||||||||||
| Possessing a specific set of other numbers |
| ||||||||||||||||||||
| Expressible via specific sums |
| ||||||||||||||||||||
| Generated via a sieve |
| ||||||||||||||||||||
Code related |
| ||||||||||||||||||||
| Figurate numbers |
| ||||||||||||||||||||
| Pseudoprimes |
| ||||||||||||||||||||
| Combinatorial numbers |
| ||||||||||||||||||||
| Arithmetic functions |
| ||||||||||||||||||||
| Dividing a quotient | |||||||||||||||||||||
| Other prime factor or divisor related numbers |
| ||||||||||||||||||||
| Recreational mathematics |
| ||||||||||||||||||||
 Mathematics portal | |||||||||||||||||||||
Categories:
- Pseudoprimes
(window.RLQ=window.RLQ||).push(function(){mw.config.set({"wgPageParseReport":{"limitreport":{"cputime":"0.276","walltime":"0.376","ppvisitednodes":{"value":1249,"limit":1000000},"ppgeneratednodes":{"value":0,"limit":1500000},"postexpandincludesize":{"value":124963,"limit":2097152},"templateargumentsize":{"value":2099,"limit":2097152},"expansiondepth":{"value":7,"limit":40},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":7722,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 248.668 1 -total"," 50.49% 125.551 1 Template:Reflist"," 36.58% 90.970 8 Template:Navbox"," 30.83% 76.654 1 Template:Cite_book"," 18.02% 44.811 1 Template:Prime_number_classes"," 13.64% 33.907 1 Template:Classes_of_natural_numbers"," 11.83% 29.410 1 Template:Cite_journal"," 11.46% 28.502 1 Template:Main"," 4.84% 12.042 33 Template:Math"," 4.43% 11.015 1 Template:Div_col"]},"scribunto":{"limitreport-timeusage":{"value":"0.120","limit":"10.000"},"limitreport-memusage":{"value":2980806,"limit":52428800}},"cachereport":{"origin":"mw1333","timestamp":"20181125223249","ttl":1900800,"transientcontent":false}}});mw.config.set({"wgBackendResponseTime":98,"wgHostname":"mw1240"});});
