Trial division

Trial division is the most laborious but 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 $scriptstylesqrt\{n\}$. If a number is found which divides evenly into "n", that number is a factor of "n".

A definite bound on the prime factors is possible. Suppose "P"("i") is the "i"th prime, so that "P"(1) = 2, "P"(2) = 3, etc. Then the last prime number worth testing as a possible factor of "n" is "P"("i") where "P"("i" + 1)² > "n"; equality here would mean that "P"("i" + 1) is a factor. This is all very well, but usually inconvenient to apply for the inspection of a single "n" since determining the correct value for "i" is more effort than simply trying the one unneeded candidate "P"("i" + 1) that would be involved in testing with all "P"("i") such that $scriptstyle\; P(i)\; le\; sqrt\{n\}$. Should the square root of "n" be integral, then it is a factor and "n" is a perfect square, not that this is a good way of finding them.

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

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

:$pi(sqrt\{n\})\; approx\; \{2sqrt\{n\}\; over\; ln\; n\}$

trial divisions, where $scriptstyle\; pi(x)$ denotes the prime-counting function, the number of primes less than "x". This does not take into account the overhead of primality testing to obtain the prime numbers as candidate factors. 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 can take up to about

:$\{sqrt\{n\}over\; 2\}$

trial divisions which for large "n" is worse.

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.

External links

* [http://www.btinternet.com/~se16/js/factor.htm Javascript Prime Factor Calculator using trial division] . Can handle numbers up to about 9×10¹⁵