Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Difference between revisions of "Pseudoprime"

From Prime-Wiki
Jump to: navigation, search
(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 impractibly 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>.
+
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].

External links