Trial division

From Wikipedia, the free encyclopedia

Trial division is the hardest 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 \scriptstyle\sqrt{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 ith 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)2 > 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 {2\sqrt{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.

[edit] External links

v • d • e
Number-theoretic algorithms
Primality tests
Sieving algorithms
Integer factorization algorithms
Other algorithms
Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.