1. Preface
  
  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.
  
  One  important  class of such methods is based on exponentiation in suitably
  chosen  groups  acting on subsets of the k-fold cartesian product of the set
  of  residue  classes  (mod  n),  where  n denotes the number to be factored.
  Representatives  of  this  class  are  the  Elliptic  Curves  Method  (ECM),
  Pollard's p-1  and  Williams' p+1. 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.
  
  The  other  important  class  consists of the so-called factor base methods.
  Their  runtime  depends only on the size of the number n to be factored, and
  not  on  the size of its factors. Factor base methods compute factorizations
  of  perfect  squares  (mod n)  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 (x,y) such that x^2 and y^2
  are  congruent (mod n), but pm x and pm y are not. In this situation, taking
  gcd(n,x-y)  will  yield  a  nontrivial divisor of n. 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 GAP. The first two methods are implemented in this
  package.
  
  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.
  
  With  respect  to the current state-of-the-art in integer factorization, see
  the                            Factoring                           Challenge
  (http://www.rsasecurity.com/rsalabs/node.asp?id=2093)     of     the     RSA
  Laboratories.