Factorisatietechnieken

Factorisatietechnieken are methods used to break down a composite number into its prime factors. This process is fundamental in number theory and has various applications in cryptography and computer science. The simplest technique is trial division, where one systematically checks for divisibility by prime numbers starting from 2. If a number is divisible by a prime, that prime is a factor, and the process is repeated with the resulting quotient. This continues until all factors are prime.

More advanced techniques exist for larger numbers. The Fermat factorization method relies on the difference of squares. It attempts to express the number n as a difference of two squares, n = x^2 - y^2. This can then be factored as n = (x - y)(x + y). The Pollard's rho algorithm is a probabilistic method that uses a pseudorandom sequence to find a non-trivial factor. Another probabilistic algorithm is the quadratic sieve, which is generally more efficient than Pollard's rho for numbers up to a certain size. For very large numbers, the general number field sieve is the most efficient known algorithm. The choice of factorization technique often depends on the size of the number being factored and the computational resources available.