primaliteetti

Primaliteetti, or primality, is a fundamental concept in number theory describing the property of a natural number being prime. A prime number is an integer greater than 1 that has exactly two distinct positive divisors: 1 and itself. By contrast, composite numbers have more than two divisors, and the number 1 is neither prime nor composite. In Finnish mathematical usage, primaliteetti denotes this same idea.

Examples of primes include 2, 3, 5, 7, 11, and 13. Examples of non-primes include 4, 6, 8, 9, and 15. The distribution of primes among the natural numbers is irregular but follows deep patterns studied in analytic number theory. The fundamental theorem of arithmetic states that every integer greater than 1 is either prime or can be factored uniquely into primes, up to the order of the factors.

Determining whether a given number is prime is called primality testing. The simplest method is trial division, checking divisibility up to the square root of the number. The Sieve of Eratosthenes is an efficient algorithm to enumerate all primes up to a given limit. For very large numbers, practical primality testing relies on probabilistic methods such as Miller-Rabin, often with multiple iterations, while deterministic variants exist for numbers below certain bounds. The AKS primality test established that primality can be decided in polynomial time in theory, though it is not used for routine computations.

Primaliteetti underpins many areas of mathematics and computer science, including cryptography, where large primes are used in public-key systems such as RSA, and in algorithms for random number generation and hashing.