Trial division

From Free net encyclopedia

Trial division is the simplest and easiest to understand of the integer factorization algorithms.

Given a composite integer n (throughout this article, n means "the integer to be factored"), trial division consists of trial-dividing n by every prime number less than or equal to <math>\sqrt{n}</math>. If a number is found which divides evenly into n, a factor of n has been found.

Trial division is guaranteed to find a factor of n, since it checks all possible prime factors of n. Thus, if the algorithm fails, it is proof that n is prime.

In the worst case, trial division is a very inefficient algorithm. If it starts from 2 and works up to the square root of n, the algorithm requires

<math>\pi(\sqrt{n})</math>

trial divisions, where <math>\pi(x)</math> denotes the prime counting function, the number of primes less than x. This does not take into account the overhead of primality testing. If a variant is used without primality testing, but simply dividing by every odd number less than the square root of n, prime or not, it takes

<math>{\sqrt{n}\over 2}</math>

trial divisions.

This means that for n with large prime factors of similar size (like those used in public key cryptography), trial division is computationally infeasible.

However, for n with at least one small factor, trial division can be a quick way to find that small factor. It is worthwhile to note that for random n, there is a 50% chance that 2 is a factor of n, and a 33% chance that 3 is a factor, and so on. It can be shown that 88% of all positive integers have a factor under 100, and that 91% have a factor under 1000.

For most significant factoring concerns, however, other algorithms are more efficient and therefore feasible.de:Probedivision fr:Divisions successives ru:Перебор zh:试除法