Prime Numbers

Overview

Prime numbers are the multiplicative building blocks of the positive integers. Every integer greater than one can be expressed as a product of primes, and that factorisation is unique apart from the order of the factors.

Technical foundations

The fundamental theorem of arithmetic states that every integer greater than one has a unique prime factorisation up to ordering. Euclid's argument proves there are infinitely many primes, while the prime number theorem shows that the counting function pi(x) is asymptotic to x divided by log x. More precise information is linked to zeros of the Riemann zeta function through explicit formulae. Arithmetic progressions contain infinitely many primes when the step and initial term are coprime, illustrating how algebraic constraints shape distribution.

How it works

Primes can be identified by testing divisibility up to a square-root bound, while large computations use more efficient primality tests and sieves. Their distribution becomes sparser on average as numbers grow, yet there are infinitely many primes and their local spacing remains highly irregular.

Measurement and research methods

Computational methods distinguish finding primes from proving that a candidate is prime. The sieve of Eratosthenes and segmented sieves enumerate ranges, Miller-Rabin provides an efficient probabilistic compositeness test, and algorithms such as ECPP can generate certificates that are independently verified. Integer factorisation instead seeks the unknown prime divisors of a composite and uses methods ranging from trial division to the number-field sieve. Complexity depends on bit length, not the numerical magnitude written in decimal notation, which is essential when comparing algorithms.

Key ideas

• One is not prime because including it would destroy uniqueness of factorisation.
• Primality and factorisation are related but computationally different tasks.
• Patterns in primes connect elementary arithmetic to deep analytic structures.

Current research frontier

Modern research studies gaps, additive representations, primes in polynomial sequences and connections with automorphic forms. The Riemann hypothesis would tightly bound fluctuations in prime distribution but remains unproved. In cryptography, RSA relies on difficulty of factoring selected composites, while Diffie-Hellman systems use group problems that may be built from prime moduli; primality alone does not confer security. Parameter generation must avoid weak randomness and special structure. Large quantum computers running Shor's algorithm would change these assumptions, motivating post-quantum schemes based on other hard problems.

Why it matters

Prime numbers are central to number theory and appear in algebra, geometry, pseudorandom constructions and public-key cryptography. Questions about their distribution have driven major mathematical methods.

Limits and open questions

Many simple statements about primes remain unproved, including famous conjectures about gaps and zeros of associated functions. Cryptographic use also depends on complete protocols, not merely on choosing large primes.