Pollardféle

Pollardféle, also known as Pollard's rho algorithm, is a general-purpose integer factorization algorithm, which is used to find the prime factors of a composite number. It was developed by John Pollard in 1975. The algorithm is particularly useful for finding small factors of large numbers, and it is often used in cryptography to break certain types of encryption.

The Pollard's rho algorithm works by generating a sequence of numbers using a pseudo-random function, and then searching for a cycle in this sequence. The cycle is detected using Floyd's cycle-finding algorithm, which is also known as the "tortoise and hare" algorithm. Once a cycle is found, the greatest common divisor (GCD) of the numbers at the start and end of the cycle is calculated. If the GCD is greater than 1 and less than the original number, then it is a non-trivial factor of the number.

The Pollard's rho algorithm is a probabilistic algorithm, meaning that it does not always find a factor in a given number of steps. The probability of success depends on the size of the smallest prime factor of the number. The algorithm is most effective when the smallest prime factor is small.

The Pollard's rho algorithm is often used in conjunction with other factorization algorithms, such as the quadratic sieve, to factorize large numbers. It is also used in the generation of large prime numbers, which are used in cryptographic systems.