Editing Factorization (section)

==Integers==
{{Main|Integer factorization}}

By the [[fundamental theorem of arithmetic]], every [[integer]] greater than 1 has a unique (up to the order of the factors) factorization into [[prime number]]s, which are those integers which cannot be further factorized into the product of integers greater than one.

For computing the factorization of an integer {{mvar|n}}, one needs an [[algorithm]] for finding a [[divisor]] {{mvar|q}} of {{mvar|n}} or deciding that {{mvar|n}} is prime. When such a divisor is found, the repeated application of this algorithm to the factors {{mvar|q}} and {{math|''n'' / ''q''}} gives eventually the complete factorization of {{mvar|n}}.<ref>{{Cite book |last1=Hardy|last2=Wright |title=An Introduction to the Theory of Numbers |isbn=978-0198531715 |edition=5th |year=1980 |publisher=Oxford Science Publications |url-access=registration |url=https://archive.org/details/introductiontoth00hard|mode=cs2}}</ref>

For finding a divisor {{mvar|q}} of {{mvar|n}}, if any, it suffices to test all values of {{mvar|q}} such that {{math|1 < ''q''}} and {{math|''q''<sup>2</sup> ≤ ''n''}}. In fact, if {{math|''r''}} is a divisor of {{mvar|n}} such that {{math|''r''<sup>2</sup> > ''n''}}, then {{math|1=''q'' = ''n'' / ''r''}} is a divisor of {{mvar|n}} such that {{math|''q''<sup>2</sup> ≤ ''n''}}.

If one tests the values of {{mvar|q}} in increasing order, the first divisor that is found is necessarily a prime number, and the ''cofactor'' {{math|1=''r'' = ''n'' / ''q''}} cannot have any divisor smaller than {{mvar|q}}. For getting the complete factorization, it suffices thus to continue the algorithm by searching a divisor of {{mvar|r}} that is not smaller than {{mvar|q}} and not greater than {{math|{{sqrt|''r''}}}}.

There is no need to test all values of {{mvar|q}} for applying the method. In principle, it suffices to test only prime divisors. This needs to have a table of prime numbers that may be generated for example with the [[sieve of Eratosthenes]]. As the method of factorization does essentially the same work as the sieve of Eratosthenes, it is generally more efficient to test for a divisor only those numbers for which it is not immediately clear whether they are prime or not. Typically, one may proceed by testing 2, 3, 5, and the numbers >&nbsp;5, whose last digit is 1, 3, 7, 9 and the sum of digits is not a multiple of 3.

This method works well for factoring small integers, but is inefficient for larger integers. For example, [[Pierre de Fermat]] was unable to discover that the 6th [[Fermat number]] 
: <math>1 + 2^{2^5} = 1 + 2^{32} = 4\,294\,967\,297</math>
is not a prime number. In fact, applying the above method would require more than {{val|10,000|u=divisions}}, for a number that has 10&nbsp;[[decimal digit]]s.

There are more efficient factoring algorithms. However they remain relatively inefficient, as, with the present state of the art, one cannot factorize, even with the more powerful computers, a number of 500 decimal digits that is the product of two randomly chosen prime numbers. This ensures the security of the [[RSA cryptosystem]], which is widely used for secure [[internet]] communication.

===Example===
For factoring {{math|1=''n'' = 1386}} into primes:
* Start with division by 2: the number is even, and {{math|1=''n'' = 2 · 693}}. Continue with 693, and 2 as a first divisor candidate. 
* 693 is odd (2 is not a divisor), but is a multiple of 3: one has {{math|1= 693 = 3 · 231}} and {{math|1=''n'' = 2 · 3 · 231}}. Continue with 231, and 3 as a first divisor candidate.
* 231 is also a multiple of 3: one has {{math|1= 231 = 3 · 77}}, and thus {{math|1=''n'' = 2 · 3<sup>2</sup> · 77}}. Continue with 77, and 3 as a first divisor candidate.
* 77 is not a multiple of 3, since the sum of its digits is 14, not a multiple of 3. It is also not a multiple of 5 because its last digit is 7. The next odd divisor to be tested is 7. One has {{math|1= 77 = 7 · 11}}, and thus {{math|1=''n'' = 2 · 3<sup>2</sup> · 7 · 11}}. This shows that 7 is prime (easy to test directly). Continue with 11, and 7 as a first divisor candidate. 
* As {{math|7<sup>2</sup> > 11}}, one has finished. Thus 11 is prime, and the prime factorization is 
: {{math|1=1386 = 2 · 3<sup>2</sup> · 7 · 11}}.