Primaliteitsproef

Primaliteitsproef, often translated as primality test, refers to an algorithm used to determine whether a given integer is a prime number. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Primality tests are fundamental in number theory and have significant applications in cryptography.

There are two main categories of primality tests: deterministic and probabilistic. Deterministic tests guarantee a correct answer, while probabilistic tests offer a high probability of correctness but can sometimes err.

One of the simplest deterministic primality tests is trial division. This method involves checking if the number in question, say 'n', is divisible by any integer from 2 up to the square root of 'n'. If a divisor is found, 'n' is composite; otherwise, it is prime. While straightforward, trial division becomes computationally expensive for very large numbers.

More sophisticated deterministic tests exist, such as the AKS primality test, which provides polynomial-time complexity. However, it is often slower in practice than probabilistic methods for numbers of typical cryptographic size.

Probabilistic tests, like the Miller-Rabin test, are widely used due to their efficiency. They work by checking certain properties that prime numbers must satisfy. If a number fails these checks, it is definitely composite. If it passes, it is likely prime, with the probability of error decreasing significantly with repeated testing. For practical applications, especially in cryptography, a sufficiently high certainty level is achieved.