Editing Integer factorization (section)

== Prime decomposition ==
[[Image:PrimeDecompositionExample.svg|right|thumb|Prime decomposition of {{math|''n'' {{=}} 864}} as {{math|2<sup>5</sup> × 3<sup>3</sup>}}]]
By the [[fundamental theorem of arithmetic]], every positive integer has a unique [[prime factor]]ization. (By convention, 1 is the [[empty product]].) [[Primality test|Testing]] whether the integer is prime can be done in [[polynomial time]], for example, by the [[AKS primality test]]. If composite, however, the polynomial time tests give no insight into how to obtain the factors.

Given a general algorithm for integer factorization, any integer can be factored into its constituent [[prime factor]]s by repeated application of this algorithm. The situation is more complicated with special-purpose factorization algorithms, whose benefits may not be realized as well or even at all with the factors produced during decomposition. For example, if {{math|1=''n'' = 171 × ''p'' × ''q''}} where {{math|''p'' < ''q''}} are very large primes, [[trial division]] will quickly produce the factors 3 and 19 but will take {{math|''p''}} divisions to find the next factor. As a contrasting example, if {{math|''n''}} is the product of the primes {{math|13729}}, {{math|1372933}}, and {{math|18848997161}}, where {{math|1=13729 × 1372933 = 18848997157}}, Fermat's factorization method will begin with {{math|⌈{{sqrt|''n''}}⌉ {{=}} 18848997159}} which immediately yields {{math|''b'' {{=}} {{sqrt|''a''<sup>2</sup> − ''n''}} {{=}} {{sqrt|4}} {{=}} 2}} and hence the factors {{math|1=''a'' − ''b'' = 18848997157}} and {{math|1=''a'' + ''b'' = 18848997161}}. While these are easily recognized as composite and prime respectively, Fermat's method will take much longer to factor the composite number because the starting value of {{math|⌈{{sqrt|18848997157}}⌉ {{=}} 137292}} for {{math|''a''}} is a factor of 10 from {{math|1372933}}.