TRIAL DIVISION TO TWELVE DIGITS
What is Trial Division?
Trial division is the name of an algorithm which attempts at finding a prime factor of a given positive integer N. The trial is done by repeatedly dividing N by the prime numbers 2, 3, 5, 7, 11, etc., until a factor is found; otherwise N itself is prime.
Note that given a composite N which factors into two or more primes, at most one of the prime factors can be larger than √N while the rest is each bounded by this square root. Therefore, it is not necessary to continue the algorithm once we reach the last prime number p ≤ √N.
Furthermore, once we find a prime factor p, we iterate the trial division with the integer N/p in place of N. In this way, we end up with the complete factorization of N into prime numbers. As already mentioned, if not one factor is found, then the number N proves to be a prime.
Feel free to save or modify a copy of this file for your own use.
Other Factoring Algorithms
Despite its simple implementation, trial divison is super slow when dealing with large numbers. To tackle a 53-bit integer, for instance, our prime database would swell 70 to 80 times larger than its current size.
For a more advanced and more clever factoring algorithms, try to google the so-called Pollard rho method and p−1 method, or the quadratic sieve method. None of these guarantees a quick result, if successful at all, but with some theoretical help, one can learn the best factoring approach with respect to a given integer range.
There are situations in which one must know simply whether N is prime or composite, without needing the factors of N if composite. This calls for a primality testing algorithm. Generally speaking, testing primes is not as hard as factoring composites, nor as slow. See our testing primes page for an example.
Copyright © 20112021 Amin Witno
This page belongs to the personal folder of Amin Witno and does not necessarily represent the philosophy and values of Philadelphia University or the Department of Basic Sciences in particular.