<p>Factoring large integers is a computationally very difficult problem, and there is no general factorization algorithm known which can be used for factoring products of two primes with more than about 100 decimal digits each on currently existing computers. But there are methods (not algorithms in the sense that it is guaranteed that they will give the desired result after a finite number of steps) for factoring integers with prime factors being far beyond the range where trial division is feasible.</p>
<p>One important class of such methods is based on exponentiation in suitably chosen groups acting on subsets of the <span class="SimpleMath">\(k\)</span>-fold cartesian product of the set of residue classes (mod <span class="SimpleMath">\(n\)</span>), where <span class="SimpleMath">\(n\)</span> denotes the number to be factored. Representatives of this class are the Elliptic Curves Method (ECM), Pollard's \(p-1\) and Williams' <span class="SimpleMath">\(p+1\)</span>. These methods have the important property that they find smaller factors usually considerably faster than larger ones. This however comes along with the drawback of suboptimal performance for large factors.</p>
<p>The other important class consists of the so-called factor base methods. Their run time depends only on the size of the number <span class="SimpleMath">\(n\)</span> to be factored, and not on the size of its factors. Factor base methods compute factorizations of perfect squares (mod <span class="SimpleMath">\(n\)</span>) over an appropriately chosen factor base. A factor base is a set of small prime numbers, or of prime ideals in the case of the Generalized Number Field Sieve. The factor base methods use these factorizations to determine a pair of integers <span class="SimpleMath">\((x,y)\)</span> such that <span class="SimpleMath">\(x^2\)</span> and <span class="SimpleMath">\(y^2\)</span> are congruent (mod <span class="SimpleMath">\(n\)</span>), but <span class="SimpleMath">\(\pm x\)</span> and <span class="SimpleMath">\(\pm y\)</span> are not. In this situation, taking <span class="SimpleMath">\(\gcd(n,x-y)\)</span> will yield a nontrivial divisor of <span class="SimpleMath">\(n\)</span>. Representatives of this class are the Continued Fraction Algorithm (CFRAC), the Multiple Polynomial Quadratic Sieve (MPQS) and the already mentioned Generalized Number Field Sieve (GNFS). The latter has the asymptotically lowest average-case complexity of all factoring methods known today. It has however the drawback of being more efficient than the MPQS only for numbers with more than about 100 decimal digits, which is probably not within the feasible range of such a function implemented in <strong class="pkg">GAP</strong>. The first two methods are implemented in this package.</p>
<p>Except of the "naive" methods like trial division and some "historical" methods, the only method which I am aware of that does not fit into one of the two classes mentioned above is Pollard's Rho, which is already implemented in the GAP Library.
<p>With respect to the current state-of-the-art in integer factorization, see the <span class="URL"><a href=" http://www.rsasecurity.com/rsalabs/node.asp?id=2093">Factoring Challenge</a></span> of the RSA Laboratories.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
