Content deleted Content added
Line 23:
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 {{nowrap|1=''n'' = 171 × ''p'' × ''q''}} where {{nowrap|''p'' < ''q''}} are very large primes, [[trial division]] will quickly produce the factors 3 and 19 but will take ''p'' divisions to find the next factor. As a contrasting example, if ''n'' is the product of the primes 13729, 1372933, and 18848997161, where {{nowrap|1=13729 × 1372933 = 18848997157}}, Fermat's factorization method will begin with <math>\left\lceil\sqrt{n}\right\rceil = 18848997159 </math> which immediately yields <math display="inline">b = \sqrt{a^2 - n} = \sqrt{4} = 2 </math> and hence the factors {{nowrap|1=''a'' − ''b'' = 18848997157}} and {{nowrap|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 display="inline">\left\lceil\sqrt{18848997157}\,\right\rceil = 137292 </math> for ''a'' is
== Current state of the art ==
| |||