Trial division
|
|
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> is 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.zh:试除法