HOME

TheInfoList



OR:

Trial division is the most laborious but easiest to understand of the
integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are ...
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 ''n''. For example, for the integer , the only numbers that divide it are 1, 2, 3, 4, 6, 12. Selecting only the largest powers of primes in this list gives that . Trial division was first described by
Fibonacci Fibonacci (; also , ; – ), also known as Leonardo Bonacci, Leonardo of Pisa, or Leonardo Bigollo Pisano ('Leonardo the Traveller from Pisa'), was an Italian mathematician from the Republic of Pisa, considered to be "the most talented Western ...
in his book ''
Liber Abaci ''Liber Abaci'' (also spelled as ''Liber Abbaci''; "The Book of Calculation") is a historic 1202 Latin manuscript on arithmetic by Leonardo of Pisa, posthumously known as Fibonacci. ''Liber Abaci'' was among the first Western books to describ ...
'' (1202).


Method

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. Clearly, it is only worthwhile to test candidate factors less than ''n'', and in order from two upwards because an arbitrary ''n'' is more likely to be divisible by two than by three, and so on. With this ordering, there is no point in testing for divisibility by four if the number has already been determined not divisible by two, and so on for three and any multiple of three, etc. Therefore, the effort can be reduced by selecting only
prime numbers A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
as candidate factors. Furthermore, the trial factors need go no further than \scriptstyle\sqrt because, if ''n'' is divisible by some number ''p'', then ''n = p × q'' and if ''q'' were smaller than ''p'', ''n'' would have been detected earlier as being divisible by ''q'' or by a prime factor of ''q''. A definite bound on the prime factors is possible. Suppose is the 'th prime, so that ''P''1 = 2, ''P''2 = 3, ''P''3 = 5, etc. Then the last prime number worth testing as a possible factor of ''n'' is where ; equality here would mean that is a factor. Thus, testing with 2, 3, and 5 suffices up to ''n'' = 48 not just 25 because the square of the next prime is 49, and below ''n'' = 25 just 2 and 3 are sufficient. Should the square root of ''n'' be an integer, then it is a factor and ''n'' is a perfect square. An example of the trial division algorithm, using successive integers as trial factors, is as follows (in Python): def trial_division(n: int) -> list nt """Return a list of the prime factors for a natural number.""" a = [] # Prepare an empty list. f = 2 # The first possible factor. while n > 1: # While n still has remaining factors... if n % f

0: # The remainder of n divided by f might be zero. a.append(f) # If so, it divides n. Add f to the list. n //= f # Divide that factor out of n. else: # But if f is not a factor of n, f += 1 # Add one to f and try again. return a # Prime factors may be repeated: 12 factors to 2,2,3.
Or 2x more efficient: def trial_division(n: int) -> list nt a = [] while n % 2

0: a.append(2) n //= 2 f = 3 while f * f <= n: if n % f

0: a.append(f) n //= f else: f += 2 if n != 1: a.append(n) # Only odd number is possible return a
These versions of trial division are guaranteed to find a factor of ''n'' if there is one since they check ''all possible factors'' of ''n'' and if ''n'' is a prime number, this means trial factors all the way up to ''n''. Thus, if the algorithm finds one factor only, n, it is proof that ''n'' is a
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. If more than one factor is found, then ''n'' is a composite integer. A more computationally advantageous way of saying this is, if any prime whose square does not exceed ''n'' divides it without a remainder, then ''n'' is not prime. Below is a version in C++ (without squaring f) template vector TrialDivision(U n)


Speed

In the
worst case In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
, trial division is a laborious algorithm. For a base-2 ''n'' digit number ''a'', if it starts from two and works up only to the square root of ''a'', the algorithm requires :\pi(2^) \approx trial divisions, where \scriptstyle \pi(x) denotes the
prime-counting function In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number ''x''. It is denoted by (''x'') (unrelated to the number ). History Of great interest in number theory i ...
, the number of primes less than ''x''. This does not take into account the overhead of
primality testing A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating wheth ...
to obtain the prime numbers as candidate factors. 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 In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime ...
) would only be worthwhile if many numbers were to be tested. If instead a variant is used without primality testing, but simply dividing by every odd number less than the square root the base-2 ''n'' digit number ''a'', prime or not, it can take up to about: :2^ In both cases, the required time grows exponentially with the digits of the number. Even so, this is a quite satisfactory method, considering that even the best-known algorithms have exponential time growth. For ''a'' chosen uniformly at random from integers of a given length, there is a 50% chance that 2 is a factor of ''a'' and a 33% chance that 3 is a factor of ''a'', 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 ''a'', it is worthwhile to check for divisibility by the small primes, since for a = 1000, in base-2 n=10. However, many-digit numbers that do not have factors in the small primes can require days or months to factor with the trial division. In such cases other methods are used such as the
quadratic sieve The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considera ...
and the
general number field sieve In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\left( ...
(GNFS). Because these methods also have superpolynomial time growth a practical limit of ''n'' digits is reached very quickly. For this reason, in public key cryptography, values for ''a'' 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
supercomputer A supercomputer is a computer with a high level of performance as compared to a general-purpose computer. The performance of a supercomputer is commonly measured in floating-point operations per second ( FLOPS) instead of million instructions ...
s and computer grids. The largest cryptography-grade number that has been factored is
RSA-250 In mathematics, the RSA numbers are a set of large semiprimes (numbers with exactly two prime factors) that were part of the RSA Factoring Challenge. The challenge was to find the prime factors of each number. It was created by RSA Laboratories ...
, a 250 digits number, using the GNFS and resources of several supercomputers. The running time was 2700 core years.


References

* *


External links

16x16px 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

{{number theoretic algorithms Integer factorization algorithms Division (mathematics) Articles with example Python (programming language) code