Trial division

The trial division is an algorithm from the mathematical branch of number theory. The algorithm determines a non-trivial divisor of a positive integer, if one exists. He does not find such a divider, the predetermined number is a prime number. The trial division is thus both a factorization and a primality test. Performs to the trial division continues after a nichttrivaler divider was found, so you can eventually determine the prime factorization of a natural number. Typically, you use this method only as a factorization to find the prime factors up to a certain limit. This is called incomplete trial division.

Operation

The sample division, the factors of a number to be searched by starting the sequence divided by a prime number in each of Figures 2 and is checked by whether this is a factor of. If so, you had to find a factor p, is replaced by the number / p and tried this prime again. If not, you will pass to the next larger prime number. This is done until one has arrived at the square root of n. The remaining number is a prime number and then the last factor, since it is on the one hand by any of the numbers smaller than the other and divided the product of two numbers is larger and larger than itself.

In the case of incomplete trial division, the procedure as well, with the only difference that you stop already with a prescribed bound S. The remaining factor no longer needs to be a prime factor in this case.

Example

In order to factorize the number in 1746, dividing them first by 2 and receives 873 One more time can not divide this number by 2. Thus you will pass to 3 Through this you can share again and gets 291 This number can again be divided by 3 and you get 97, which is not divisible by 3. After trying unsuccessfully not to divide by the numbers 5 and 7. The next prime is 11 but already larger than the square root of 97, which is why it breaks off at this point and the prime factorization may specify: 1746 = 2.32.97.

Variants

For the trial division one needs a list of small primes, which is usually generated by the sieve of Eratosthenes. This is especially handy if you want to factorize a number of approximately equal numbers. Some variants of the trial division can do without this list.

One possibility is to carry out not only with the prime a sample division, but with all numbers (except 1). The result is the same, but it can be performed unnecessary divisions.

Some of these divisions can avoid unnecessary, if one carries out trial division, only with the 2 and odd numbers.

This idea can be generalized even further by focusing limited to all numbers that are congruent to 1 or 5 modulo 6, or all the numbers congruent to 1, 7, 11, 13, 17, 19, 23 or 29 modulo 30. In the first case it is necessary additionally to Figures 2 and 3 sample, in the second case, the numbers 2, 3 and 5

Referring generally to the first n primes (pi), it can be with

An interval of

Browse numbers. 4 for the first prime numbers ( 2, 3, 5, 7), this means that (2-1 ) * ( 3-1 ) * ( 5-1 ) * ( 7-1) = 48 Test sufficient to give an interval of 2.3.5.7 = 210 dividers work off.

The advantage is that such a program does not require large prime number tables. Since the distances of the required splitter are set at an interval of 210 numbers, a table of small numbers 48 to calculate the increment for the next divider suffices.

Implementation details

If you want to use the trial division in a computer program, it will save space reasons, the list of primes either as a bit array or alternatively always half the difference between the prime to the previous prime. In the latter case one needs for every prime number up to 1,872,851,947 bytes of memory only (per prime).

Instead of checking whether P is greater than the square root of n, one tests whether P2 is greater than N, as this is faster.

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

Term

Dividing the sample required about divisions in the worst case. In the variants that do not require a prime number list, the number of divisions in the worst case, where the constant c depends on the method.

The average operating time is of the same order of magnitude as in the worst case.

Areas of application

The incomplete trial division is often used to gain an initial overview of the factorization of a number. Only if this is not able to completely factoring, the number, the user returns to complex factorization.

In addition, the trial division is often required as part of step in more complex factorization.

• Factorization