Trial division

The trial division is an algorithm from the mathematical branch of number theory . The algorithm finds a nontrivial divisor of a positive integer , if one exists. If he does not find such a divisor, the given number is a prime number . The trial division is thus both a factorization procedure and a prime number test . If you continue the trial division after a nontrivial divisor has been found, you can ultimately determine the prime factorization of a natural number . As a rule, this procedure is only used as a factorization procedure to find prime factors up to a certain limit . One then speaks of an incomplete trial division .

functionality

In the sample, the division factors of a number to be searched by sequentially through every prime number beginning, at 2, divided and thereby checks whether a factor of is. If so, replace it with the number and divide it by again . If not, move on to the next largest prime number . This is done until it has become larger than the square root of n . The remaining number n is then either 1 or a prime number and thus the last factor of the given number, because on the one hand it cannot be divided by any number less than or equal (these have already been divided) and on the other hand the product of two numbers is greater than itself . ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle p}$ ${\ displaystyle p}$ ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle n / p}$ ${\ displaystyle p}$ ${\ displaystyle p}$ ${\ displaystyle p}$ ${\ displaystyle n}$ ${\ displaystyle {\ sqrt {n}}}$ ${\ displaystyle {\ sqrt {n}}}$ ${\ displaystyle n}$

In the case of an incomplete trial division, the procedure is the same, the only difference being that one stops at a given limit S. In this case, the remaining factor no longer necessarily has to be a prime factor.

example

To factor the number 1746, you first divide it by 2 and get 873. This number cannot be divided by 2 again. So you go over to the 3. By this you can divide again and get 291. This number can be divided by 3 again and you get 97, which is no longer divisible by 3. Then you try to divide by the numbers 5 and 7 without success. The next prime number 11, however, is already larger than the square root of 97, which is why you break off at this point and state the prime factorization: 1746 = 2 · 3 ² · 97.

variants

For the trial division one needs a list of small prime numbers, which one usually generates through the sieve of Eratosthenes . This is particularly useful if you want to factor several numbers of roughly the same size. Some variants of the trial division can do without this list.

One possibility is to do a trial division not only with the prime numbers, but with all numbers (except 1). The result is the same, but redundant divisions are made.

Some of these superfluous divisions can be avoided if one only conducts a trial division with the 2 and the odd numbers.

This idea can be further generalized by limiting yourself to all numbers that are congruent 1 or 5 modulo 6, or all numbers that are congruent 1, 7, 11, 13, 17, 19, 23 or 29 modulo 30. In the first case you also have to try the numbers 2 and 3, in the second case the numbers 2, 3 and 5.

If one generally takes the first n prime numbers (p _i ), one can use

{\ displaystyle \ prod _ {i = 1} ^ {n} (p_ {i} -1)}

an interval of

{\ displaystyle \ prod _ {i = 1} ^ {n} p_ {i}}

Browse numbers. For the first 4 prime numbers (2, 3, 5, 7) this means that (2-1) * (3-1) * (5-1) * (7-1) = 48 tests are sufficient to determine an interval with 2 3 5 7 = 210 divisors to be processed.

The advantage is that such a program does not require large tables of prime numbers. Since the distances between the necessary divisors are fixed in an interval of 210 numbers, a table of 48 small numbers is sufficient to calculate the increment for the next divisor.

Implementation details

If you want to sample the division in a computer program use, one is the list of primes save memory space, either as a bit - array store or alternatively always half the difference of the previous prime prime. In the latter case, only one byte of storage space is required for each prime number up to 1,872,851,947 (per prime number).

Instead of checking whether p is greater than the square root of n , testing whether p ^{2 is} greater than n , as this is faster.

In the case of the variant in which only numbers that are congruent 1 or 5 modulo 6 are tried, you can run through these numbers efficiently by alternately adding 2 and 4 to the previous number.

running time

In the worst case, the trial division needs about divisions. In the variants that get by without a prime number list, the number of divisions is in the worst case , the constant c depending on the method. ${\ displaystyle 2 {\ tfrac {\ sqrt {n}} {\ ln n}}}$ ${\ displaystyle c {\ sqrt {n}}}$

The mean runtime is in the same order of magnitude as in the worst case.

Areas of application

The incomplete trial division is often used to get an initial overview of the factorization of a number. Only when this is not able to fully factorize the number does one switch to more complex factorization methods.

In addition, the trial division is often required as a substep in more complex factoring processes.