Trial division

Trial division is the most laborious but easiest to understand of the integer factorization algorithms. Its ease of implementation makes it a viable integer factorization option for devices with little available memory, such as graphing calculators.

Basic Idea

Trial division tests to see if an integer n, the integer to be factored, can be divided by any positive integer less than or equal to n.

Method

Given an integer n (throughout this article, n refers to "the integer to be factored"), trial division consists of testing whether n is divisible by any number. Clearly, it is only worthwhile to test candidate factors less than n, and in order from two upwards because an arbitrary n is more likely to be divisible by two than by three, and so on. With this ordering, there is no point in testing for divisibility by four if the number has already been determined not divisible by two, and so on for three and any multiple of three, etc. Therefore, effort can be reduced by selecting only prime numbers as candidate factors. Furthermore, the trial factors need go no further than $\scriptstyle {\sqrt {n}}$ because, if n is divisible by some number p, then n = p×q and if q were smaller than p, n would have earlier been detected as being divisible by q or a prime factor of q.

A definite bound on the prime factors is possible. Suppose P(i) is the ith prime, so that P(1) = 2, P(2) = 3, P(3) = 5, 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. Thus, testing with 2, 3, and 5 suffices up to n = 48 (not just 25) because the square of the next prime is 49. 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)\leq {\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.

An example of the trial division algorithm, without primality testing, is as follows (in Java):

import java.util.Scanner;
class TrialDivision {
    public static void main(String[] argv) {
        Scanner sc = new Scanner(System.in);
        int numToBeFactored = sc.nextInt();
 
        for (int i=2; i < 0.5 + Math.sqrt(numToBeFactored); i++) {
            double tmp=numToBeFactored/(double)i;
            if (tmp == (int)tmp) {
                System.out.println(i + ", " + (int)tmp);
            }
        }
    }
}

Trial division is guaranteed to find a factor of n if there is one, since it checks all possible prime factors of n. Thus, if the algorithm finds no factor, it is proof that n is a prime. If a factor is found, then n is a composite integer.

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. A useful table need not be large: P(3512) = 32749, the last prime that fits into a sixteen-bit signed integer and P(6542) = 65521 for unsigned sixteen-bit integers. That would suffice to test primality for numbers up to 65537² = 4,295,098,369. Preparing such a table (usually via the Sieve of Eratosthenes) would only be worthwhile if many numbers were to be tested. If instead 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 unfeasible.

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.