Content deleted Content added
m Fixing wrongly titled links |
m Fixing wrongly titled links |
||
Line 56:
At the start of the 19th century, Legendre and Gauss independently conjectured that as ''x'' tends to infinity, the number of primes up to ''x'' is asymptotic to ''x''/ln(''x''), where ln(''x'') is the [[natural logarithm]] of ''x''. Ideas of Riemann in his [[On the Number of Primes Less Than a Given Magnitude|1859 paper on the zeta-function]] sketched a program which would lead to a proof of the prime number theorem. This outline was completed by [[Jacques Hadamard|Hadamard]] and [[Charles de la Vallée-Poussin|de la Vallée Poussin]], who independently proved the prime number theorem in 1896.
Proving a number is prime is not done (for large numbers) by trial division. Many mathematicians have worked on [[primality test]]s for large numbers, often restricted to specific number forms. This includes [[Pépin's test]] for Fermat numbers (1877), [[Proth's theorem]] (around 1878), the [[Lucas–Lehmer primality test
For a long time, prime numbers were thought to have extremely limited application outside of [[pure mathematics]];{{Fact|date=August 2008}} this changed in the 1970s when the concepts of [[public-key cryptography]] were invented, in which prime numbers formed the basis of the first algorithms such as the [[RSA]] cryptosystem algorithm.
Line 149:
===Location of the largest known prime===
{{main|Largest known prime|Mersenne prime}}
Historically, the largest known prime has almost always been a Mersenne prime since the dawn of electronic computers, because there exists a particularly fast primality test for numbers of this form, the [[Lucas–Lehmer primality test
{| class="wikitable" border="1"
| |||