trial division

Factoring by trial divisionMathworldPlanetmath is an algorithmMathworldPlanetmath where a given integer n is tested for divisibility by each prime pi in order until all its factors are discovered. It is the easiest algorithm to understand and the simplest to implement, but not always the most efficient.

Depending on the implementation, the algorithm can be provided with a list of primes. If, for example, the implementation is to be limited to 16-bit unsigned integers, it might make sense to provide a list of the primes up to 257. Otherwise, the list of primes could be gathered on the fly, or a performance penalty could be accepted by allowing certain “could-be primes”.

Call the trial division algorithm with an integer n.

  1. 1.

    Initialize i=1, length of factor list to 0, (if used) all exponents to 1, prime flag to true, test cap to n, test remainder m to equal n.

  2. 2.

    Test if mpi is an integer. If it is, reset m=mpi, set prime flag to false and test if pi will divide again. As many times as indicated, add pi to the list of factors, or add it once to the list of factors and increment the appropriate exponent accordingly. Increment once the length of the factor list.

  3. 3.

    Increment i and see if pi<n. Also check that m>1. If both of these conditions are true, repeat the previous step.

  4. 4.

    If prime flag is true, place n in the first spot of the factor list and set factor list length to 1.

  5. 5.

    Return the factor list (and if applicable, the exponent list). It might or might not be a good idea to expose the prime flag to the calling functionMathworldPlanetmath.

For example, n=32851. Clearly 2 doesn’t divide evenly, a human can tell on sight. Since it’s a small number, the digit sum test for 3 is applied quickly enough, and it returns false. We don’t need to try 5, though a computer does. Then, dividing by 7, we get the integer 4693, but 7 doesn’t divide again. Neither does 11. 4693 divided by 13 gives us 361. If this was a recursive implementation, it would recognize that 361 is 19 squared. Ergo, the factorization is 32851=713192.

To give another example: given n=1411041, trial division would take 196 divisions. The second division would find 3 is a factor, the third would confirm 3’s exponent is 1, and it would take almost a couple hundred more divisions to get to 1187 and the certainty that 470347 must be a prime and the factors are hence 3 and 470347. Of course, with numbers of this size, a computer can perform hundreds of divisions in the blink of an eye.

Let’s try 522611488293. This number is almost “unfair” to an implementation lacking a list of primes provided beforehand, or even an implementation that remembers the primes it has tried. The second factor, 370373, ends a prime gapMathworldPlanetmath of 110 consecutive composites. It’s enough to slow down a computer implementation of trial division, even one that actually wastes time trying on such composites as 370263, 370267, 370269, etc. but not by much.

This last example, 4393547637856664251490043044051018234292171475232959, is an example of what not to even try to factor with trial division. Its square rootMathworldPlanetmath is more than 61025, and the logarithmic integralDlmfDlmfMathworldPlanetmathPlanetmath tells us there might be about 1024 primes to test divide in trying to factor this number.

The speed of the algorithm depends perhaps more in the size of the smallest prime factorMathworldPlanetmath than it does on the size of n. For example, PrimeFan’s Integer Factorer (a Javascript implementation) takes 2 to 3 seconds to factor 2432902008176640000 (which is 20!), but fails to give an answer for 2432902008176639999 before Internet Explorer asks the user if they want to abort the script. Henry Bottomley’s Javascript implementation handles factorials better than PrimeFan’s (responding to 20! instantaneously), but still freezes on 20!-1.

0.1 External links se16/js/factor.htmHenry Bottomley’s Prime Factors Calculator’s Number Factorer

Title trial division
Canonical name TrialDivision
Date of creation 2013-03-22 16:39:00
Last modified on 2013-03-22 16:39:00
Owner CompositeFan (12809)
Last modified by CompositeFan (12809)
Numerical id 7
Author CompositeFan (12809)
Entry type Algorithm
Classification msc 11A41