question: why are prime numbers so important? Why are we constantly calculating "new" ones?
comment: They're crucial to mathematical functions used to perform encryption. As computers get more powerful, bigger prime numbers may be required to keep encryption from being "forced" open by the sheer computing power we have available. The properties of these numbers make them usable in calculations that are easy to do in one direction, but hard to reverse. Bigger prime numbers in these calculations make them even harder to reverse.
passages: The property of being prime is called primality. A simple but slow method of checking the primality of a given number formula_1, called trial division, tests whether formula_1 is a multiple of any integer between 2 and formula_3. Faster algorithms include the Miller–Rabin primality test, which is fast but has a small chance of error, and the AKS primality test, which always produces the correct answer in polynomial time but is too slow to be practical. Particularly fast methods are available for numbers of special forms, such as Mersenne numbers. the largest known prime number has 24,862,048 decimal digits.
   Since 1951 all the largest known primes have been found using these tests on computers. The search for ever larger primes has generated interest outside mathematical circles, through the Great Internet Mersenne Prime Search and other distributed computing projects. The idea that prime numbers had few applications outside of pure mathematics was shattered in the 1970s when public-key cryptography and the RSA cryptosystem were invented, using prime numbers as their basis.
   This vision of the purity of number theory was shattered in the 1970s, when it was publicly announced that prime numbers could be used as the basis for the creation of public key cryptography algorithms.
  
  These applications have led to significant study of algorithms for computing with prime numbers, and in particular of primality testing, methods for determining whether a given number is prime.
   In November 2005 the largest known sexy prime quadruplet, found by Jens Kruse Andersen had 1002 digits:
  
  In September 2010 Ken Davis announced a 1004-digit quadruplet with "p" = 2 + 1582534968299.
  
  In May 2019 Marek Hubal announced a 1138-digit quadruplet with p = 1567237911*2677# + 3301 + 6*n.
  
  In June 2019 Peter Kaiser announced a 1534-digit quadruplet with p = 19299420002127 * 2 + 17233 + 6*n
  
  Section::::Types of groupings.:Sexy prime quintuplets.
   Generation of primes
  
  In computational number theory, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashing, public-key cryptography, and search of prime factors in large numbers.
  
  For relatively small numbers, it is possible to just apply trial division to each successive odd number. Prime sieves are almost always faster.
  
  Section::::Prime sieves.
   Prime numbers are frequently used for hash tables. For instance the original method of Carter and Wegman for universal hashing was based on computing hash functions by choosing random linear functions modulo large prime numbers. Carter and Wegman generalized this method to formula_64-independent hashing by using higher-degree polynomials, again modulo large primes. As well as in the hash function, prime numbers are used for the hash table size in quadratic probing based hash tables to ensure that the probe sequence covers the whole table.
   The following table gives the largest known primes of various types. Some of these primes have been found using distributed computing. In 2009, the Great Internet Mersenne Prime Search project was awarded a US$100,000 prize for first discovering a prime with at least 10 million digits. The Electronic Frontier Foundation also offers $150,000 and $250,000 for primes with at least 100 million digits and 1 billion digits, respectively.
  
  Section::::Computational methods.:Integer factorization.
   Section::::Judging the prime version.
   Shor's algorithm can factor any integer in a polynomial number of steps on a quantum computer. However, current technology can only run this algorithm for very small numbers. the largest number that has been factored by a quantum computer running Shor's algorithm is 21.
  
  Section::::Computational methods.:Other computational applications.
   However, prime gaps of "n" numbers can occur at numbers much smaller than "n"!. For instance, the first prime gap of size larger than 14 occurs between the primes 523 and 541, while 15! is the vastly larger number 1307674368000.
   Gigantic prime
  
  A gigantic prime is a prime number with at least 10,000 decimal digits. 
  
  The term appeared in "Journal of Recreational Mathematics" in the article "Collecting gigantic and titanic primes" (1992) by Samuel Yates. Chris Caldwell, who continued Yates' collection in The Prime Pages, reports that he changed the requirement from Yates' original 5,000 digits to 10,000 digits, when he was asked to revise the article after the death of Yates. Few primes of that size were known then, but a modern personal computer can find many in a day.
   The most basic primality testing routine, trial division, is too slow to be useful for large numbers. One group of modern primality tests is applicable to arbitrary numbers, while more efficient tests are available for numbers of special types. Most primality tests only tell whether their argument is prime or not. Routines that also provide a prime factor of composite arguments (or all of its prime factors) are called factorization algorithms.
  
  Prime numbers are also used in computing for checksums, hash tables, and pseudorandom number generators.
  
  Section::::Computational methods.:Trial division.
   Apart from their low density, they are easier to find than strong primes, in that the programs are much simpler. It is not necessary to attempt the factorization of "p" − 1. (If "p" − 1 is difficult to factor, then "p" is rejected, and "p" + 2 is tried. This is repeated until "p" − 1 factors easily. This will happen sooner than "p" would become a safe prime, on average, because primes "p" for which "p" − 1 factors easily are fairly dense.) All of this is made possible by the fact that there are extremely fast probabilistic tests for primality, such as the Miller–Rabin primality test.
   The increased practical importance of computerized primality testing and factorization led to the development of improved methods capable of handling large numbers of unrestricted form. The mathematical theory of prime numbers also moved forward with the Green–Tao theorem (2004) that there are arbitrarily long arithmetic progressions of prime numbers, and Yitang Zhang's 2013 proof that there exist infinitely many prime gaps of bounded size.
  
  Section::::History.:Primality of one.
   Section::::History.
   The following table lists the first 1000 primes, with 20 columns of consecutive primes in each of the 50 rows.
   Another type of problem concerns prime gaps, the differences between consecutive primes.
   A very important part of the computational number theory is to know if a number is prime. This can be difficult because it requires a large amount of computer power to prove primality in a large number.
   As of later 1989, Surrey University had the largest Prime Site in Europe, having multiple copies of virtually every 50 series machine (mostly running Primos 20.x, but some still running 19.x).
   Section::::Other applications.:Biology.
  
  The evolutionary strategy used by cicadas of the genus "Magicicada" makes use of prime numbers. These insects spend most of their lives as grubs underground. They only pupate and then emerge from their burrows after 7, 13 or 17 years, at which point they fly about, breed, and then die after a few weeks at most. Biologists theorize that these prime-numbered breeding cycle lengths have evolved in order to prevent predators from synchronizing with these cycles.
   although their ordering may differ. So, although there are many different ways of finding a factorization using an integer factorization algorithm, they all must produce the same result. Primes can thus be considered the "basic building blocks" of the natural numbers.
   Section::::Searching for Mersenne primes.
  
  Fast algorithms for finding Mersenne primes are available, and the seven largest known prime numbers are Mersenne primes.
   Section::::See also.
  
  BULLET::::- Repunit
  
  BULLET::::- Fermat prime
  
  BULLET::::- Power of two
  
  BULLET::::- Erdős–Borwein constant
  
  BULLET::::- Mersenne conjectures
  
  BULLET::::- Mersenne twister
  
  BULLET::::- Double Mersenne number
  
  BULLET::::- Prime95 / MPrime
  
  BULLET::::- Great Internet Mersenne Prime Search (GIMPS)
  
  BULLET::::- Largest known prime number
  
  BULLET::::- Titanic prime
  
  BULLET::::- Gigantic prime
  
  BULLET::::- Megaprime
  
  BULLET::::- Wieferich prime
  
  BULLET::::- Wagstaff prime
  
  BULLET::::- Cullen prime
  
  BULLET::::- Woodall prime
  
  BULLET::::- Proth prime
  
  BULLET::::- Solinas prime
  
  BULLET::::- Gillies' conjecture
  
  Section::::External links.
  
  BULLET::::- GIMPS home page
  
  BULLET::::- GIMPS status — status page gives various statistics on search progress, typically updated every week, including progress towards proving the ordering of primes 42–47
   Further advances in the study of repunits did not occur until the 1960s, when computers allowed many new factors of repunits to be found and the gaps in earlier tables of prime periods corrected. "R" was found to be a probable prime circa 1966 and was proved prime eleven years later, when "R" was shown to be the only further possible prime repunit with fewer than ten thousand digits. It was proven prime in 1986, but searches for further prime repunits in the following decade consistently failed. However, there was a major side-development in the field of generalized repunits, which produced a large number of new primes and probable primes.
   Section::::Computational methods.:Special-purpose algorithms and the largest known prime.
  
  In addition to the aforementioned tests that apply to any natural number, some numbers of a special form can be tested for primality more quickly.
  
  For example, the Lucas–Lehmer primality test can determine whether a Mersenne number (one less than a power of two) is prime, deterministically,
  
  in the same time as a single iteration of the Miller–Rabin test. This is why since 1992 () the largest "known" prime has always been a Mersenne prime.
  
  It is conjectured that there are infinitely many Mersenne primes.
  