Content deleted Content added
LMFRoelofs (talk | contribs) Tag: Reverted |
|||
Line 18:
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}}.
This is a process commonly used in passwords.
== Current state of the art ==
| |||