Trial division
Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer n, the integer to be factored, can be divided by each number in turn that is less than or equal to the square root of n.
For example, to find the prime factors of n = 70, one can try to divide 70 by successive primes: first, 70 / 2 = 35; next, neither 2 nor 3 evenly divides 35; finally, 35 / 5 = 7, and 7 is itself prime. So 70 = 2 × 5 × 7.
Trial division was first described by Fibonacci in his book Liber Abaci (1202).[1]
Method
[edit]Given an integer n (n refers to "the integer to be factored"), the trial division consists of systematically testing whether n is divisible by any smaller number. Since the goal is to find a prime factorization, once a prime factor p is found, one can repeat the process with n/p to find another prime factor, and so on. The process terminates when all of the prime factors are found.
If n is composite, then its smallest prime factor must be at most , because it is not possible for two prime factors of n both to be greater than this. Thus, to find the first prime factor, one can proceed by testing each number from 2 up to whether it evenly divides n. If such a factor is found, we proceed as above with n/p. If every prime factor of n exceeds , it means that n is prime, and so the process terminates.
During the trial divisions, it is only necessary to test against primes, and only those primes less than or equal to . As a practical matter, it may not be feasible to keep track of all primes less than this bound, but sieving can still reduce the number of non-primes one must test (for example, not testing any even number greater than two, or multiple of three greater than three).[2] It is not strictly necessary to keep track of a table of primes however: if an integer p is found that divides the current integer n to be factored, then it is guaranteed to be prime, because the smaller primes have been excluded as potential factors of n, provided the implementation scans the integers in order starting at .
Moreover, an additional optimization of the method is as follows. When a prime factor of n is found, instead of immediately repeating the full scan with the new integer n/p all over again beginning at 2, the scan can instead proceed beginning at the prime p. This will then recursively remove from n all powers of the prime p that divide it, and then proceed to the next prime.
A simple pseudocode implementation is:[3]
Input: integer n ≥ 2 Output: list of prime factors, including repetitions factors ← empty list (m is the integer we are working with) m ← n (Remove factors of two) while 2 divides m: append 2 to factors m ← m / 2 (Beginning at p = 3, remove each prime power that divides m) p ← 3 while p² ≤ m: while p divides m: append p to factors m ← m / p (only need to consider odd p; an optimized version would use a wheel here; cf. Crandall and Pomerance, p. 126) p ← p + 2 if m > 1: (all primes ≤ √m have been removed, so m is prime) append m to factors return factors
Speed
[edit]In the worst case, trial division is a laborious algorithm. For a number n having bits, if it starts from two and works up only to the square root of n, the algorithm requires[4]
trial divisions, where denotes the prime-counting function, the number of primes less than x. This does not take into account the overhead of maintaining a table of primes or sieving for them. 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 655372 = 4,295,098,369. Preparing such a table (usually via the Sieve of Eratosthenes) may be especially worthwhile if many numbers are 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:
In both cases, the required time grows exponentially with the digits of the number.
For many integers, this can be a satisfactory method of factorization because it can detect small factors early, but for integers containing only large prime factors its worst-case exponential growth makes it far inferior to subexponential algorithms. Early-terminating optimized trial division may be used in conjunction with other methods for pulling off small factors.[5][6] For n chosen uniformly at random from integers of a given length, there is a 50% chance that 2 is a factor of n and a 33% chance that 3 is a factor of n, and so on. It can be shown that 88% of all positive integers have a factor under 100 and that 92% have a factor under 1000. Thus, when confronted by an arbitrary large n, it is worthwhile to check for divisibility by the small primes, since for , in base-2 .
However, many-digit numbers that do not have factors in the small primes can require days or months to factor with trial division. In such cases other methods are used such as the quadratic sieve and the general number field sieve (GNFS). Because these methods also have superpolynomial time growth a practical limit of bits is reached very quickly. For this reason, in public key cryptography, values for n are chosen to have large prime factors of similar size so that they cannot be factored by any publicly known method in a useful time period on any available computer system or computer cluster such as supercomputers and computer grids. The largest cryptography-grade number that has been factored is RSA-260, a 260-digit number, factored in September 2026 using a GPU-accelerated implementation of the general number field sieve.[7]
References
[edit]- ↑ Mollin, Richard A. (2002). "A brief history of factoring and primality testing B. C. (before computers)". Mathematics Magazine. 75 (1): 18–29. doi:10.2307/3219180. JSTOR 3219180. MR 2107288.
- ↑ Crandall & Pomerance 2005, Section 3.2.
- ↑ Crandall & Pomerance 2005, pp. 118–119.
- ↑ Crandall & Pomerance 2005, p. 120.
- ↑ Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (1996). "Number-Theoretic Reference Problems" (PDF). Handbook of Applied Cryptography. CRC Press. p. 90. ISBN 978-0-8493-8523-0.
- ↑ "Some notes on internal implementation". Wolfram Research. Retrieved 2026-11-11.
FactorInteger switches between trial division, Pollard p−1, Pollard rho, elliptic curve, and quadratic sieve algorithms.
- ↑ Lu, Eric (September 9, 2026). "Factoring RSA-260". Cognition. Retrieved September 9, 2026.
- Childs, Lindsay N. (2009). A concrete introduction to higher algebra. Undergraduate Texts in Mathematics (3rd ed.). New York, NY: Springer-Verlag. ISBN 978-0-387-74527-5. Zbl 1165.00002.
- Crandall, Richard; Pomerance, Carl (2005). Prime numbers. A computational perspective (2nd ed.). New York, NY: Springer-Verlag. ISBN 0-387-25282-7. Zbl 1088.11001.
External links
[edit]- Wikiversity offers a lesson on prime factorization using trial division with Python.
- Fast JavaScript Prime Factor Calculator using trial division. Can handle numbers up to about 253
- Trial Division in Java, C and JavaScript (in Portuguese)