| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Pseudoprime"
(restored) |
(spelling fixed) |
||
| Line 5: | Line 5: | ||
For example, a ''strong pseudoprime'' is a composite number that passes one iteration the [[Miller-Rabin pseudoprimality test]]. | For example, a ''strong pseudoprime'' is a composite number that passes one iteration the [[Miller-Rabin pseudoprimality test]]. | ||
| − | Pseudoprimes are useful in many areas of computing where primes need to be generated quickly. One example of such a field is in the RSA encryption system, where each party needs to generate two large primes, possibly with hundreds of decimal digits. Actually testing candidates for primality is | + | Pseudoprimes are useful in many areas of computing where primes need to be generated quickly. One example of such a field is in the RSA encryption system, where each party needs to generate two large primes, possibly with hundreds of decimal digits. Actually testing candidates for primality is impracticably slow; however probabilistic primality tests can rapidly generate numbers which are "[[Probable prime|probably prime]]". The term "probably" is not to be taken lightly; a number which passes only 100 iterations of the Miller-Rabin test, for example, has a probability of only <math>{1/4}^{100}</math> of being composite, which is less than <math>10^{-60}</math>. |
==External links== | ==External links== | ||
*[https://en.wikipedia.org/wiki/Pseudoprime Wikipedia] | *[https://en.wikipedia.org/wiki/Pseudoprime Wikipedia] | ||
[[Category:Math]] | [[Category:Math]] | ||
Latest revision as of 20:32, 25 July 2020
A pseudoprime is a composite number which passes some probabilistic primality tests.
Thus, when speaking about pseudoprimes, one has to specify the test performed.
For example, a strong pseudoprime is a composite number that passes one iteration the Miller-Rabin pseudoprimality test.
Pseudoprimes are useful in many areas of computing where primes need to be generated quickly. One example of such a field is in the RSA encryption system, where each party needs to generate two large primes, possibly with hundreds of decimal digits. Actually testing candidates for primality is impracticably slow; however probabilistic primality tests can rapidly generate numbers which are "probably prime". The term "probably" is not to be taken lightly; a number which passes only 100 iterations of the Miller-Rabin test, for example, has a probability of only [math]\displaystyle{ {1/4}^{100} }[/math] of being composite, which is less than [math]\displaystyle{ 10^{-60} }[/math].
