% generated by GAPDoc2LaTeX from XML source (Frank Luebeck)
\documentclass[a4paper,11pt]{report}
\usepackage{a4wide}
\sloppy
\pagestyle{myheadings}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage{makeidx}
\makeindex
\usepackage{color}
\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
%% strange name because of pdflatex bug:
\definecolor{Chapter }{rgb}{0.0,0.0,1.0}

\usepackage{fancyvrb}

\usepackage{pslatex}

\usepackage{amsxtra}\usepackage[pdftex=true,
        a4paper=true,bookmarks=false,pdftitle={Written with GAPDoc},
        pdfcreator={LaTeX with hyperref package / GAPDoc},
        colorlinks=true,backref=page,breaklinks=true,linkcolor=RoyalBlue,
        citecolor=RoyalGreen,filecolor=RoyalRed,
        urlcolor=RoyalRed,pagecolor=RoyalBlue]{hyperref}

% write page numbers to a .pnr log file for online help
\newwrite\pagenrlog
\immediate\openout\pagenrlog =\jobname.pnr
\immediate\write\pagenrlog{PAGENRS := [}
\newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\F}{\mathbb{F}}

\newcommand{\GAP}{\textsf{GAP}}

\begin{document}

\logpage{[ 0, 0, 0 ]}
\begin{titlepage}
\begin{center}{\Huge \textbf{\textsf{FactInt}\mbox{}}}\\[1cm]
\hypersetup{pdftitle=\textsf{FactInt}}
\markright{\scriptsize \mbox{}\hfill \textsf{FactInt} \hfill\mbox{}}
{\Large \textbf{Advanced Methods for Factoring Integers\mbox{}}}\\[1cm]
{ Version 1.5.2 \mbox{}}\\[1cm]
{September 26, 2007\mbox{}}\\[1cm]
\mbox{}\\[2cm]
{\large \textbf{ Stefan Kohl    \mbox{}}}\\
\hypersetup{pdfauthor= Stefan Kohl    }
\end{center}\vfill

\mbox{}\\
{\mbox{}\\
\small \noindent \textbf{ Stefan Kohl    } --- Email: \href{mailto://kohl@mathematik.uni-stuttgart.de} {\texttt{kohl@mathematik.uni-stuttgart.de}}\\
 --- Homepage: \href{ http://www.cip.mathematik.uni-stuttgart.de/~kohlsn/ } {\texttt{ http://www.cip.mathematik.uni-stuttgart.de/\texttt{\symbol{126}}kohlsn/ }}\\
 --- Address: \begin{minipage}[t]{8cm}\noindent
 Institut f{\"u}r Geometrie und Topologie \\
 Pfaffenwaldring 57 \\
 Universit{\"a}t Stuttgart \\
 70550 Stuttgart \\
 Germany \end{minipage}
}\\
\end{titlepage}

\newpage\setcounter{page}{2}
{\small 
\section*{Abstract}
\logpage{[ 0, 0, 2 ]}
 This package for \textsf{GAP}{\nobreakspace}4 provides a general-purpose integer factorization routine,
which makes use of a combination of factoring methods. In particular it
contains implementations of the following algorithms: 
\begin{itemize}
\item Pollard's $p-1$
\item Williams' $p+1$
\item Elliptic Curves Method (ECM)
\item Continued Fraction Algorithm (CFRAC)
\item Multiple Polynomial Quadratic Sieve (MPQS)
\end{itemize}
 It also contains code by Frank L{\"u}beck for making use of Richard P. Brent's
tables of factors of integers of the form $b^k \pm 1$. \textsf{FactInt} is completely written in the \textsf{GAP} language and contains / requires no external binaries. It needs \textsf{GAPDoc}{\nobreakspace}1.0 \cite{GAPDoc} or higher. \textsf{FactInt} must be installed in the \texttt{pkg} subdirectory of the \textsf{GAP} distribution. \mbox{}}\\[1cm]
{\small 
\section*{Copyright}
\logpage{[ 0, 0, 1 ]}
 {\copyright} 1999 - 2007 by Stefan Kohl. This package is distributed under the
GNU General Public License. \vspace{-1cm} \mbox{}}\\[1cm]
{\small 
\section*{Acknowledgements}
\logpage{[ 0, 0, 3 ]}
 I would like to thank Bettina Eick and Steve Linton for their support and many
interesting discussions. \mbox{}}\\[1cm]
\newpage

\def\contentsname{Contents\logpage{[ 0, 0, 4 ]}}

\tableofcontents
\newpage

        
\chapter{\textcolor{Chapter }{Preface}}\label{ch:Preface}
\logpage{[ 1, 0, 0 ]}
\hyperdef{L}{X874E1D45845007FE}{}
{
  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{\nobreakspace}$p-1$ and Williams'{\nobreakspace}$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{\nobreakspace}$n$) over an appropriately chosen factor base. A factor base is a set of small
prime numbers, or of \index{prime ideal@prime ideal} prime ideals in the case of the \index{Generalized Number Field Sieve@Generalized Number Field Sieve} 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{\nobreakspace}$n$), but $\pm x$ and $\pm y$ are not. In this situation, taking $\gcd(n,x-y)$ will yield a nontrivial divisor of{\nobreakspace}$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{\nobreakspace}\textsf{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 \index{Pollard's Rho@Pollard's Rho} Pollard's Rho, which is already implemented in the \textsf{GAP} Library. 

 With respect to the current state-of-the-art in integer factorization, see the \index{RSA Factoring Challenge@RSA Factoring Challenge} \href{ http://www.rsasecurity.com/rsalabs/node.asp?id=2093} {Factoring Challenge} of the RSA Laboratories.  }

         
\chapter{\textcolor{Chapter }{The General Factorization Routine}}\label{ch:General}
\logpage{[ 2, 0, 0 ]}
\hyperdef{L}{X7B1A84BB788FC526}{}
{
   
\section{\textcolor{Chapter }{The method for \texttt{Factors}}}\label{sec:Factors}
\logpage{[ 2, 1, 0 ]}
\hyperdef{L}{X83BF2CD28017ABC5}{}
{
  The \textsf{FactInt} package provides a better method for the operation \texttt{Factors} for integer arguments, which supersedes the one included in the \textsf{GAP} Library: 

\subsection{\textcolor{Chapter }{Factors (FactInt's method, for integers)}}
\logpage{[ 2, 1, 1 ]}\nobreak
\hyperdef{L}{X833B087D7A83BC7A}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Factors({\slshape n})\index{Factors@\texttt{Factors}!FactInt's method, for integers}
\label{Factors:FactInt's method, for integers}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 A sorted list of the prime factors of \mbox{\texttt{\slshape n}}. 



 \index{primality of the factors@primality of the factors} The returned factors pass the built-in probabilistic primality test of \textsf{GAP} (\texttt{IsProbablyPrimeInt}, Baillie-PSW Primality Test; see the \textsf{GAP} Reference Manual). If the method fails to compute the prime factorization of \mbox{\texttt{\slshape n}}, an error is signalled. The same holds for all other factorization routines
provided by this package. It follows a rough description how the factorization
method works: 

 First of all, the method checks whether $n = b^k \pm 1$ for some $b$, $k$ and looks for factors corresponding to polynomial factors of $x^k \pm 1$. Provided that $b$ and $k$ are not too large, the factors that do not correspond to polynomial factors
are taken from Richard P. Brent's Factor Tables{\nobreakspace}\cite{Brent04}. The code for accessing these tables has been contributed by Frank
L{\"u}beck. 

 Then the method uses trial division and a number of cheap methods for various
common special cases. After the small and other ``easy'' factors have been found this way, \textsf{FactInt}'s method searches for ``medium-sized'' factors using Pollard's Rho (by the library function \texttt{FactorsRho}, see the \textsf{GAP} Reference Manual), Pollard's{\nobreakspace}$p-1$ (see{\nobreakspace}\texttt{FactorsPminus1} (\ref{FactorsPminus1:Pollard's p-1})), Williams'{\nobreakspace}$p+1$ (see{\nobreakspace}\texttt{FactorsPplus1} (\ref{FactorsPplus1:Williams' p+1})) and the Elliptic Curves Method (ECM, see{\nobreakspace}\texttt{FactorsECM} (\ref{FactorsECM:Elliptic Curves Method, ECM})) in this order. 

 If there is still an unfactored part remaining after that, it is factored
using the Multiple Polynomial Quadratic Sieve (MPQS, see{\nobreakspace}\texttt{FactorsMPQS} (\ref{FactorsMPQS:Multiple Polynomial Quadratic Sieve, MPQS})). 

 The following options are interpreted: 
\begin{description}
\item[{\mbox{\texttt{\slshape TDHints}}}]  A list of additional trial divisors. This is useful only if certain
primes{\nobreakspace}$p$ are expected to divide $n$ with probability significantly larger than $\frac{1}{p}$. 
\item[{\mbox{\texttt{\slshape RhoSteps}}}]  The number of steps for Pollard's Rho. 
\item[{\mbox{\texttt{\slshape RhoCluster}}}]  The number of steps between two gcd computations in Pollard's Rho. 
\item[{\mbox{\texttt{\slshape Pminus1Limit1}} / \mbox{\texttt{\slshape Pminus1Limit2}}}]  The first- / second stage limit for Pollard's{\nobreakspace}$p-1$ (see{\nobreakspace}\texttt{FactorsPminus1} (\ref{FactorsPminus1:Pollard's p-1})). 
\item[{\mbox{\texttt{\slshape Pplus1Residues}}}]  The number of residues to be tried by Williams'{\nobreakspace}$p+1$ (see{\nobreakspace}\texttt{FactorsPplus1} (\ref{FactorsPplus1:Williams' p+1})). 
\item[{\mbox{\texttt{\slshape Pplus1Limit1}} / \mbox{\texttt{\slshape Pplus1Limit2}}}]  The first- / second stage limit for Williams'{\nobreakspace}$p+1$ (see{\nobreakspace}\texttt{FactorsPplus1} (\ref{FactorsPplus1:Williams' p+1})). 
\item[{\mbox{\texttt{\slshape ECMCurves}}}]  The number of elliptic curves to be tried by the Elliptic Curves Method (ECM)
(see{\nobreakspace}\texttt{FactorsECM} (\ref{FactorsECM:Elliptic Curves Method, ECM})). Also admissible: a function that takes the number $n$ to be factored as an argument and returns the desired number of curves to be
tried. 
\item[{\mbox{\texttt{\slshape ECMLimit1}} / \mbox{\texttt{\slshape ECMLimit2}}}]  The initial first- / second stage limit for ECM (see{\nobreakspace}\texttt{FactorsECM} (\ref{FactorsECM:Elliptic Curves Method, ECM})). 
\item[{\mbox{\texttt{\slshape ECMDelta}}}]  The increment per curve for the first stage limit in ECM. The second stage
limit is adjusted appropriately (see{\nobreakspace}\texttt{FactorsECM} (\ref{FactorsECM:Elliptic Curves Method, ECM})). 
\item[{\mbox{\texttt{\slshape ECMDeterministic}}}]  If true, ECM chooses its curves deterministically, i.e. repeatable
(see{\nobreakspace}\texttt{FactorsECM} (\ref{FactorsECM:Elliptic Curves Method, ECM})). 
\item[{\mbox{\texttt{\slshape FBMethod}}}]  Specifies which of the factor base methods should be used to do the ``hard work''. Currently implemented: \texttt{"CFRAC"} and \texttt{"MPQS"} (see{\nobreakspace}\texttt{FactorsCFRAC} (\ref{FactorsCFRAC:Continued Fraction Algorithm, CFRAC}) and{\nobreakspace}\texttt{FactorsMPQS} (\ref{FactorsMPQS:Multiple Polynomial Quadratic Sieve, MPQS}), respectively). Default: \texttt{"MPQS"}. 
\end{description}
 For the use of the \textsf{GAP} Options Stack, see Chapter \emph{Options Stack} in the \textsf{GAP} Reference Manual. 

 Setting \mbox{\texttt{\slshape RhoSteps}}, \mbox{\texttt{\slshape Pminus1Limit1}}, \mbox{\texttt{\slshape Pplus1Residues}}, \mbox{\texttt{\slshape Pplus1Limit1}}, \mbox{\texttt{\slshape ECMCurves}} or \mbox{\texttt{\slshape ECMLimit1}} equal to zero switches the respective method off. The method chooses defaults
for all option values that are not explicitly set by the user. The option
values are also interpreted by the routines for the particular factorization
methods described in the next chapter. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> Factors( Factorial(44) + 1 );
  [ 694763, 9245226412016162109253, 413852053257739876455072359 ]
  gap> Factors( 2^997 - 1 );
  [ 167560816514084819488737767976263150405095191554732902607, 
    79934306053602222928609369601238840619880168466272137576868879760059\
  3002563860297371289151859287894468775962208410650878341385577817736702\
  2158878920741413700868182301410439178049533828082651513160945607018874\
  830040978453228378816647358334681553 ]
  
\end{Verbatim}
 }

 The above method for \texttt{Factors} calls the following function, which is the actual ``working horse'' of this package: 

\subsection{\textcolor{Chapter }{FactInt (factorization of an integer)}}
\logpage{[ 2, 1, 2 ]}\nobreak
\hyperdef{L}{X866CD23D78460060}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FactInt({\slshape n})\index{FactInt@\texttt{FactInt}!factorization of an integer}
\label{FactInt:factorization of an integer}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 A list of two lists, where the first list contains the determined prime
factors of{\nobreakspace}\mbox{\texttt{\slshape n}} and the second list contains the remaining unfactored parts of{\nobreakspace}\mbox{\texttt{\slshape n}}, if there are any. 



 This function interprets all options which are interpreted by the method for \texttt{Factors} described above. In addition, it interprets the options \mbox{\texttt{\slshape cheap}} and \mbox{\texttt{\slshape FactIntPartial}}. If the option \mbox{\texttt{\slshape cheap}} is set, only usually cheap factorization attempts are made. If the option \mbox{\texttt{\slshape FactIntPartial}} is set, the factorization process is stopped before invoking the (usually
time-consuming) MPQS or CFRAC, if the number of digits of the remaining
unfactored part exceeds the bound passed as option value \mbox{\texttt{\slshape MPQSLimit}} or \mbox{\texttt{\slshape CFRACLimit}}, respectively. 

 \texttt{Factors(\mbox{\texttt{\slshape n}})} is equivalent to \texttt{FactInt(\mbox{\texttt{\slshape n}}:\mbox{\texttt{\slshape cheap}}:=false, \mbox{\texttt{\slshape FactIntPartial}}:=false)[1]}. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> FactInt( Factorial(300) + 1 : cheap );
  [ [ 461, 259856122109, 995121825812791, 3909669044842609, 
        4220826953750952739, 14841043839896940772689086214475144339 ], 
    [ 104831288231765723173983836560438594053336296629073932563520618687\
  9287645058010688827246061541065631119345674081834085960064144597037243\
  9235869682208979384309498719255615067943353399357029226058930732298505\
  5816977495398426741656633461747046623641451042655247093315505417820370\
  9451745871701742000546384614472756584182478531880962594857275869690727\
  9733563594352516014206081210368516157890709802912711149521530885498556\
  1244667790208245620301404499928532222524585946881528337257061789593197\
  99211283640357942345263781351 ] ]
  
\end{Verbatim}
 }

 }

  
\section{\textcolor{Chapter }{Getting information about the factoring process}}\label{sec:Info}
\logpage{[ 2, 2, 0 ]}
\hyperdef{L}{X83A95F837BB78098}{}
{
  \index{information about factoring process@information about factoring process} Optionally, the \textsf{FactInt} package prints information on the progress of the factorization process: 

\subsection{\textcolor{Chapter }{InfoFactInt (FactInt's Info class)}}
\logpage{[ 2, 2, 1 ]}\nobreak
\hyperdef{L}{X8093BB787C2E764B}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InfoFactInt\index{InfoFactInt@\texttt{InfoFactInt}!FactInt's Info class}
\label{InfoFactInt:FactInt's Info class}
}\hfill{\scriptsize (info class)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FactIntInfo({\slshape level})\index{FactIntInfo@\texttt{FactIntInfo}!setting the InfoLevel of InfoFactInt}
\label{FactIntInfo:setting the InfoLevel of InfoFactInt}
}\hfill{\scriptsize (function)}}\\


 This Info class allows to monitor what happens during the factoring process. 

 If \texttt{InfoLevel(InfoFactInt) = 1}, then basic information about the factoring techniques used is displayed. If
this InfoLevel has value{\nobreakspace}2, then additionally all ``relevant'' steps in the factoring algorithms are mentioned. If it is set equal
to{\nobreakspace}3, then large amounts of details of the progress of the
factoring process are shown. 

 Enter \texttt{FactIntInfo(\mbox{\texttt{\slshape level}})} to set the \texttt{InfoLevel} of \texttt{InfoFactInt} to the positive integer \mbox{\texttt{\slshape level}}. The call \texttt{FactIntInfo(\mbox{\texttt{\slshape level}});} is equivalent to \texttt{SetInfoLevel(InfoFactInt,\mbox{\texttt{\slshape level}});}. 

 The informational output is usually not literally the same in each
factorization attempt to a given integer with given parameters. For a
description of the Info mechanism, see Section \emph{Info Functions} in the \textsf{GAP} Reference Manual. }

 }

  }

         
\chapter{\textcolor{Chapter }{The Routines for Specific Factorization Methods}}\label{ch:Methods}
\logpage{[ 3, 0, 0 ]}
\hyperdef{L}{X7E7EE1A1785A8009}{}
{
  Descriptions of the factoring methods implemented in this package can be found
in{\nobreakspace}\cite{Bressoud89} and \cite{Cohen93}. Cohen's book contains also descriptions of the other methods mentioned in
the preface.  
\section{\textcolor{Chapter }{Trial division}}\label{sec:TrialDivision}
\logpage{[ 3, 1, 0 ]}
\hyperdef{L}{X7A0392177E697956}{}
{
  \index{trial division@trial division} 

\subsection{\textcolor{Chapter }{FactorsTD (trial division)}}
\logpage{[ 3, 1, 1 ]}\nobreak
\hyperdef{L}{X7C4D255A789F54B4}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FactorsTD({\slshape n[, Divisors]})\index{FactorsTD@\texttt{FactorsTD}!trial division}
\label{FactorsTD:trial division}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 A list of two lists: The first list contains the prime factors found, and the
second list contains remaining unfactored parts of \mbox{\texttt{\slshape n}}, if there are any. 



 This function tries to factor \mbox{\texttt{\slshape n}} by trial division. The optional argument \mbox{\texttt{\slshape Divisors}} is the list of trial divisors. If not given, it defaults to the list of primes $p < 1000$. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> FactorsTD(12^25+25^12);
  [ [ 13, 19, 727 ], [ 5312510324723614735153 ] ]
  
\end{Verbatim}
 }

 }

  
\section{\textcolor{Chapter }{Pollard's $p-1$}}\label{sec:PollardsPminus1}
\logpage{[ 3, 2, 0 ]}
\hyperdef{L}{X8081FF657DA9C674}{}
{
  \index{Pollard's p-1@Pollard's $p-1$} 

\subsection{\textcolor{Chapter }{FactorsPminus1 (Pollard's p-1)}}
\logpage{[ 3, 2, 1 ]}\nobreak
\hyperdef{L}{X7AF95E2E87F58200}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FactorsPminus1({\slshape n[[, a], Limit1[, Limit2]]})\index{FactorsPminus1@\texttt{FactorsPminus1}!Pollard's p-1}
\label{FactorsPminus1:Pollard's p-1}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 A list of two lists: The first list contains the prime factors found, and the
second list contains remaining unfactored parts of \mbox{\texttt{\slshape n}}, if there are any. 



 This function tries to factor \mbox{\texttt{\slshape n}} using Pollard's{\nobreakspace}$p-1$. It uses \mbox{\texttt{\slshape a}} as base for exponentiation, \mbox{\texttt{\slshape Limit1}} as first stage limit and \mbox{\texttt{\slshape Limit2}} as second stage limit. If the function is called with three arguments, these
arguments are interpreted as \mbox{\texttt{\slshape n}}, \mbox{\texttt{\slshape Limit1}} and \mbox{\texttt{\slshape Limit2}}. Defaults are chosen for all arguments which are omitted. 

 Pollard's $p-1$ is based on the fact that exponentiation (mod{\nobreakspace}$n$) can be done efficiently enough to compute $a^{k!}$ mod{\nobreakspace}$n$ for sufficiently large{\nobreakspace}$k$ in a reasonable amount of time. Assume that $p$ is a prime factor of $n$ which does not divide{\nobreakspace}$a$, and that $k!$ is a multiple of{\nobreakspace}$p-1$. Then \index{Lagrange's Theorem@Lagrange's Theorem} Lagrange's Theorem states that $a^{k!} \equiv 1$ (mod{\nobreakspace}$p$). If $k!$ is not a multiple of $q-1$ for another prime factor $q$ of{\nobreakspace}$n$, it is likely that the factor{\nobreakspace}$p$ can be determined by computing $\gcd(a^{k!}-1,n)$. A prime factor $p$ is usually found if the largest prime factor of $p-1$ is not larger than \mbox{\texttt{\slshape Limit2}}, and the second-largest one is not larger than \mbox{\texttt{\slshape Limit1}}. (Compare with \texttt{FactorsPplus1} (\ref{FactorsPplus1:Williams' p+1}) and{\nobreakspace}\texttt{FactorsECM} (\ref{FactorsECM:Elliptic Curves Method, ECM}).) 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> FactorsPminus1( Factorial(158) + 1, 100000, 1000000 );
  [ [ 2879, 5227, 1452486383317, 9561906969931, 18331561438319, 
        4837142997094837608115811103417329505064932181226548534006749213\
  4508231090637045229565481657130504121732305287984292482612133314325471\
  3674832962773107806789945715570386038565256719614524924705165110048148\
  7161609649806290811760570095669 ], [  ] ]
  gap> List( last[ 1 ]{[ 3, 4, 5 ]}, p -> Factors( p - 1 ) );
  [ [ 2, 2, 3, 3, 81937, 492413 ], [ 2, 3, 3, 3, 5, 7, 7, 1481, 488011 ]
      , [ 2, 3001, 7643, 399613 ] ]
  
\end{Verbatim}
 }

 }

  
\section{\textcolor{Chapter }{Williams' $p+1$}}\label{sec:WilliamsPplus1}
\logpage{[ 3, 3, 0 ]}
\hyperdef{L}{X860B4BE37DABDE10}{}
{
  \index{Williams' p+1@Williams' $p+1$} 

\subsection{\textcolor{Chapter }{FactorsPplus1 (Williams' p+1)}}
\logpage{[ 3, 3, 1 ]}\nobreak
\hyperdef{L}{X8079A0367DE4FC35}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FactorsPplus1({\slshape n[[, Residues], Limit1[, Limit2]]})\index{FactorsPplus1@\texttt{FactorsPplus1}!Williams' p+1}
\label{FactorsPplus1:Williams' p+1}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 A list of two lists: The first list contains the prime factors found, and the
second list contains remaining unfactored parts of \mbox{\texttt{\slshape n}}, if there are any. 



 This function tries to factor \mbox{\texttt{\slshape n}} using Williams'{\nobreakspace}$p+1$. It tries \mbox{\texttt{\slshape Residues}} different residues, and uses \mbox{\texttt{\slshape Limit1}} as first stage limit and \mbox{\texttt{\slshape Limit2}} as second stage limit. If the function is called with three arguments, these
arguments are interpreted as \mbox{\texttt{\slshape n}}, \mbox{\texttt{\slshape Limit1}} and \mbox{\texttt{\slshape Limit2}}. Defaults are chosen for all arguments which are omitted. 

 Williams' $p+1$ is very similar to Pollard's{\nobreakspace}$p-1$ (see \texttt{FactorsPminus1} (\ref{FactorsPminus1:Pollard's p-1})). The difference is that the underlying group here can either have order $p+1$ or $p-1$, and that the group operation takes more time. A prime factor $p$ is usually found if the largest prime factor of the group order is at most \mbox{\texttt{\slshape Limit2}} and the second-largest one is not larger than \mbox{\texttt{\slshape Limit1}}. (Compare also with \texttt{FactorsECM} (\ref{FactorsECM:Elliptic Curves Method, ECM}).) 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> FactorsPplus1( Factorial(55) - 1, 10, 10000, 100000 );
  [ [ 73, 39619, 277914269, 148257413069 ], 
    [ 106543529120049954955085076634537262459718863957 ] ]
  gap> List( last[ 1 ], p -> [ Factors( p - 1 ), Factors( p + 1 ) ] );
  [ [ [ 2, 2, 2, 3, 3 ], [ 2, 37 ] ], 
    [ [ 2, 3, 3, 31, 71 ], [ 2, 2, 5, 7, 283 ] ], 
    [ [ 2, 2, 2207, 31481 ], [ 2, 3, 5, 9263809 ] ], 
    [ [ 2, 2, 47, 788603261 ], [ 2, 3, 5, 13, 37, 67, 89, 1723 ] ] ]
  
\end{Verbatim}
 }

 }

  
\section{\textcolor{Chapter }{The Elliptic Curves Method (ECM)}}\label{sec:ECM}
\logpage{[ 3, 4, 0 ]}
\hyperdef{L}{X855CB8B07A0141C4}{}
{
  \index{Elliptic Curves Method (ECM)@Elliptic Curves Method (ECM)} 

\subsection{\textcolor{Chapter }{FactorsECM (Elliptic Curves Method, ECM)}}
\logpage{[ 3, 4, 1 ]}\nobreak
\hyperdef{L}{X87B162F878AD031C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FactorsECM({\slshape n[, Curves[, Limit1[, Limit2[, Delta]]]]})\index{FactorsECM@\texttt{FactorsECM}!Elliptic Curves Method, ECM}
\label{FactorsECM:Elliptic Curves Method, ECM}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ECM({\slshape n[, Curves[, Limit1[, Limit2[, Delta]]]]})\index{ECM@\texttt{ECM}!shorthand for FactorsECM}
\label{ECM:shorthand for FactorsECM}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 A list of two lists: The first list contains the prime factors found, and the
second list contains remaining unfactored parts of \mbox{\texttt{\slshape n}}, if there are any. 



 This function tries to factor \mbox{\texttt{\slshape n}} using the Elliptic Curves Method (ECM). The argument \mbox{\texttt{\slshape Curves}} is the number of curves to be tried. The argument \mbox{\texttt{\slshape Limit1}} is the initial \index{first stage limit@first stage limit} first stage limit, and \mbox{\texttt{\slshape Limit2}} is the initial \index{second stage limit@second stage limit} second stage limit. The argument \mbox{\texttt{\slshape Delta}} is the increment per curve for the first stage limit. The second stage limit
is adjusted appropriately. Defaults are chosen for all arguments which are
omitted. 

 \texttt{FactorsECM} recognizes the option \mbox{\texttt{\slshape ECMDeterministic}}. If set, the choice of the curves is deterministic. This means that in
repeated runs of \texttt{FactorsECM} the same curves are used, and hence for the same{\nobreakspace}$n$ the same factors are found after the same number of trials. 

 The Elliptic Curves Method is based on the fact that exponentiation in the \index{elliptic curve groups@elliptic curve groups} elliptic curve groups $E(a,b)/n$ can be performed fast enough to compute for example $g^{k!}$ for $k$ large enough (e.g. 100000 or so) in a reasonable amount of time and without
using much memory, and on Lagrange's Theorem. Assume that $p$ is a prime divisor of{\nobreakspace}$n$. Then Lagrange's Theorem states that if $k!$ is a multiple of $|E(a,b)/p|$, then for any \index{elliptic curve point@elliptic curve point} elliptic curve point{\nobreakspace}$g$, the power $g^{k!}$ is the identity element of $E(a,b)/p$. In this situation -- under reasonable circumstances -- the
factor{\nobreakspace}$p$ can be determined by taking an appropriate gcd. 

 In practice, the algorithm chooses in some sense ``better'' products $P_k$ of small primes rather than $k!$ as exponents. After reaching the first stage limit with $P_{Limit1}$, it considers further products $P_{Limit1}q$ for primes{\nobreakspace}$q$ up to the second stage limit \mbox{\texttt{\slshape Limit2}}, which is usually set equal to something like 100 times the first stage
limit. The prime{\nobreakspace}$q$ corresponds to the largest prime factor of the order of the group $E(a,b)/p$. 

 A prime divisor $p$ is usually found if the largest prime factor of the order of one of the
examined elliptic curve groups $E(a,b)/p$ is at most \mbox{\texttt{\slshape Limit2}} and the second-largest one is at most \mbox{\texttt{\slshape Limit1}}. Thus trying a larger number of curves increases the chance of factoring \mbox{\texttt{\slshape n}} as well as choosing a larger value for \mbox{\texttt{\slshape Limit1}} and/or \mbox{\texttt{\slshape Limit2}}. It turns out to be not optimal either to try a large number of curves with
very small \mbox{\texttt{\slshape Limit1}} and \mbox{\texttt{\slshape Limit2}} or to try only a few curves with very large limits. (Compare
with{\nobreakspace}\texttt{FactorsPminus1} (\ref{FactorsPminus1:Pollard's p-1}).) 

 The elements of the group $E(a,b)/n$ are the points $(x,y)$ given by the solutions of $y^2 = x^3 + ax + by$ in the residue class ring (mod{\nobreakspace}$n$), and an additional point $\infty$ at infinity, which serves as identity element. To turn this set into a group,
define the product (although elliptic curve groups are usually written
additively, I prefer using the multiplicative notation here to retain the
analogy to \texttt{FactorsPminus1} (\ref{FactorsPminus1:Pollard's p-1}) and \texttt{FactorsPplus1} (\ref{FactorsPplus1:Williams' p+1})) of two points $p_1$ and{\nobreakspace}$p_2$ as follows: If $p_1 \neq p_2$, let $l$ be the line through $p_1$ and{\nobreakspace}$p_2$, otherwise let $l$ be the tangent to the curve{\nobreakspace}$C$ given by the above equation in the point $p_1 = p_2$. The line $l$ intersects $C$ in a third point, say{\nobreakspace}$p_3$. If $l$ does not intersect the curve in a third affine point, then set $p_3 := \infty$. Define $p_1 \cdot p_2$ by the image of{\nobreakspace}$p_3$ under the reflection across the $x$-axis. Define the product of any curve point $p$ and $\infty$ by $p$ itself. This -- more or less obviously, checking associativity requires some
calculation -- turns the set of points on the given curve into an abelian
group $E(a,b)/n$. 

 However, the calculations are done in \index{projective coordinates@projective coordinates} projective coordinates to have an explicit representation of the identity
element and to avoid calculating inverses (mod{\nobreakspace}$n$) for the group operation. Otherwise this would require using an $O((log \ n)^3)$-algorithm, while multiplication (mod{\nobreakspace}$n$) is only $O((log \ n)^2)$. The corresponding equation is given by $bY^2Z = X^3 + aX^2Z + XZ^2$. This form allows even more efficient computations than the \index{Weierstrass model@Weierstrass model} Weierstrass model $Y^2Z = X^3 + aXZ^2 + bZ^3$, which is the projective equivalent of the affine representation $y^2 = x^3 + ax + by$ mentioned above. The algorithm only keeps track of two of the three
coordinates, namely $X$ and{\nobreakspace}$Z$. The curves are chosen in a way that ensures the order of the corresponding
group to be divisible by{\nobreakspace}12. This increases the chance that it
is smooth enough to find a factor of{\nobreakspace}$n$. The implementation follows the description of R. P. Brent given in \cite{Brent96}, pp. 5 -- 8. In terms of this paper, for the second stage the ``improved standard continuation'' is used. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> FactorsECM(2^256+1,100,10000,1000000,100);
  [ [ 1238926361552897, 
        93461639715357977769163558199606896584051237541638188580280321 ]
      , [  ] ]
  
\end{Verbatim}
 }

 }

  
\section{\textcolor{Chapter }{The Continued Fraction Algorithm (CFRAC)}}\label{sec:CFRAC}
\logpage{[ 3, 5, 0 ]}
\hyperdef{L}{X78466BB97BEE5495}{}
{
  \index{Continued Fraction Algorithm (CFRAC)@Continued Fraction Algorithm (CFRAC)} 

\subsection{\textcolor{Chapter }{FactorsCFRAC (Continued Fraction Algorithm, CFRAC)}}
\logpage{[ 3, 5, 1 ]}\nobreak
\hyperdef{L}{X7A5C8BC5861CFC8C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FactorsCFRAC({\slshape n})\index{FactorsCFRAC@\texttt{FactorsCFRAC}!Continued Fraction Algorithm, CFRAC}
\label{FactorsCFRAC:Continued Fraction Algorithm, CFRAC}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{CFRAC({\slshape n})\index{CFRAC@\texttt{CFRAC}!shorthand for FactorsCFRAC}
\label{CFRAC:shorthand for FactorsCFRAC}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 A list of the prime factors of{\nobreakspace}\mbox{\texttt{\slshape n}}. 



 This function tries to factor \mbox{\texttt{\slshape n}} using the Continued Fraction Algorithm (CFRAC), also known as
Brillhart-Morrison Algorithm. In case of failure an error is signalled. 

 Caution: The runtime of this function depends only on the size
of{\nobreakspace}\mbox{\texttt{\slshape n}}, and not on the size of the factors. Thus if a small factor is not found
during the preprocessing which is done before invoking the sieving process,
the runtime is as long as if \mbox{\texttt{\slshape n}} would have two prime factors of roughly equal size. 

 The Continued Fraction Algorithm tries to find integers $x$ and{\nobreakspace}$y$ such that $x^2 \equiv y^2$ (mod{\nobreakspace}$n$), but not $\pm x \equiv \pm y$ (mod{\nobreakspace}$n$). In this situation, taking $\gcd(x - y,n)$ yields a nontrivial divisor of{\nobreakspace}$n$. For determining such a pair $(x,y)$, the algorithm uses the continued fraction expansion of the square root
of{\nobreakspace}$n$. If $x_i/y_i$ is a \index{continued fraction approximation@continued fraction approximation} continued fraction approximation of the square root of{\nobreakspace}$n$, then $c_i := x_i^2 - ny_i^2$ is bounded by a small constant times the square root of{\nobreakspace}$n$. The algorithm tries to find as many $c_i$ as possible which factor completely over a chosen \index{factor base@factor base} factor base (a list of small primes) or with only one factor not in the factor
base. The latter ones can be used if and only if a second $c_i$ with the same ``large'' factor is found. \index{factor base@factor base!large factors} Once enough values $c_i$ have been factored, as a final stage \index{Gaussian Elimination@Gaussian Elimination} Gaussian Elimination over GF(2) is used to determine which of the congruences $x_i^2 \equiv c_i$ (mod{\nobreakspace}$n$) have to be multiplied together to obtain a congruence of the desired form $x^2 \equiv y^2$ (mod{\nobreakspace}$n$). Let $M$ be the corresponding matrix. Then the entries of{\nobreakspace}$M$ are given by $M_{ij} = 1$ if an odd power of the $j$-th element of the factor base divides the $i$-th usable factored value, and $M_{ij} = 0$ otherwise. To obtain the desired congruence, it is necessary that the rows
of{\nobreakspace}$M$ are linearly dependent. In other words, this means that the number of factored $c_i$ needs to be larger than the rank of{\nobreakspace}$M$, which is approximately given by the size of the factor base. (Compare
with{\nobreakspace}\texttt{FactorsMPQS} (\ref{FactorsMPQS:Multiple Polynomial Quadratic Sieve, MPQS}).) 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> FactorsCFRAC( Factorial(34) - 1 );
  [ 10398560889846739639, 28391697867333973241 ]
  
\end{Verbatim}
 }

 }

  
\section{\textcolor{Chapter }{The Multiple Polynomial Quadratic Sieve (MPQS)}}\label{sec:MPQS}
\logpage{[ 3, 6, 0 ]}
\hyperdef{L}{X81A47111807C58B1}{}
{
  \index{Multiple Polynomial Quadratic Sieve (MPQS)@Multiple Polynomial Quadratic Sieve (MPQS)} 

\subsection{\textcolor{Chapter }{FactorsMPQS (Multiple Polynomial Quadratic Sieve, MPQS)}}
\logpage{[ 3, 6, 1 ]}\nobreak
\hyperdef{L}{X86F8DFB681442E05}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FactorsMPQS({\slshape n})\index{FactorsMPQS@\texttt{FactorsMPQS}!Multiple Polynomial Quadratic Sieve, MPQS}
\label{FactorsMPQS:Multiple Polynomial Quadratic Sieve, MPQS}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MPQS({\slshape n})\index{MPQS@\texttt{MPQS}!shorthand for FactorsMPQS}
\label{MPQS:shorthand for FactorsMPQS}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 A list of the prime factors of{\nobreakspace}\mbox{\texttt{\slshape n}}. 



 This function tries to factor \mbox{\texttt{\slshape n}} using the Single Large Prime Variation of the Multiple Polynomial Quadratic
Sieve (MPQS). In case of failure an error is signalled. 

 Caution: The runtime of this function depends only on the size
of{\nobreakspace}\mbox{\texttt{\slshape n}}, and not on the size of the factors. Thus if a small factor is not found
during the preprocessing which is done before invoking the sieving process,
the runtime is as long as if \mbox{\texttt{\slshape n}} would have two prime factors of roughly equal size. 

 The intermediate results of a computation can be saved by interrupting it with \texttt{[Ctrl][C]} and calling \texttt{Pause();} from the break loop. This causes all data needed for resuming the computation
again to be pushed as a record \mbox{\texttt{\slshape MPQSTmp}} on the options stack. When called again with the same argument \mbox{\texttt{\slshape n}}, \texttt{FactorsMPQS} takes the record from the options stack and continues with the previously
computed factorization data. For continuing the factorization process in
another session, one needs to write this record to a file. This can be done by
the function \texttt{SaveMPQSTmp(\mbox{\texttt{\slshape filename}})}. The file written by this function can be read by the standard \texttt{Read}-function of{\nobreakspace}\textsf{GAP}. 

 The Multiple Polynomial Quadratic Sieve tries to find integers $x$ and{\nobreakspace}$y$ such that $x^2 \equiv y^2$ (mod{\nobreakspace}$n$), but not $\pm x \equiv \pm y$ (mod{\nobreakspace}$n$). In this situation, taking $\gcd(x - y,n)$ yields a nontrivial divisor of{\nobreakspace}$n$. For determining such a pair $(x,y)$, the algorithm chooses polynomials $f_a$ of the form $f_a(r) = ar^2 + 2br + c$ with suitably chosen coefficients $a$, $b$ and{\nobreakspace}$c$ which satisfy $b^2 \equiv n$ (mod{\nobreakspace}$a$) and $c = (b^2 - n)/a$. The identity $a \cdot f_a(r) = (ar + b)^2 - n$ yields a congruence (mod{\nobreakspace}$n$) with a perfect square on one side and $a \cdot f_a(r)$ on the other. The algorithm uses a sieving technique similar to the Sieve of
Eratosthenes over an appropriately chosen \index{sieving interval@sieving interval} sieving interval to search for factorizations of values $f_a(r)$ over a chosen factor base. Any two factorizations with the same single ``large'' factor which does not belong to the factor base can also be used. Taking more
polynomials and hence shorter sieving intervals has the advantage of having to
factor smaller values $f_a(r)$ over the factor base. 

 Once enough values $f_a(r)$ have been factored, as a final stage Gaussian Elimination over GF(2) is used
to determine which congruences have to be multiplied together to obtain a
congruence of the desired form $x^2 \equiv y^2$ (mod{\nobreakspace}$n$). Let $M$ be the corresponding matrix. Then the entries of{\nobreakspace}$M$ are given by $M_{ij} = 1$ if an odd power of the $j$-th element of the factor base divides the $i$-th usable factored value, and $M_{ij} = 0$ otherwise. To obtain the desired congruence, it is necessary that the rows
of{\nobreakspace}$M$ are linearly dependent. In other words, this means that the number of usable
factorizations of values $f_a(r)$ needs to be larger than the rank of{\nobreakspace}$M$. The latter is approximately equal to the size of the factor base. (Compare
with{\nobreakspace}\texttt{FactorsCFRAC} (\ref{FactorsCFRAC:Continued Fraction Algorithm, CFRAC}).) 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> FactorsMPQS( Factorial(38) + 1 );
  [ 14029308060317546154181, 37280713718589679646221 ]
  
\end{Verbatim}
 }

  }

  }

         
\chapter{\textcolor{Chapter }{How much Time does a Factorization take?}}\label{ch:Timings}
\logpage{[ 4, 0, 0 ]}
\hyperdef{L}{X85B6B6E4796B99EE}{}
{
   
\section{\textcolor{Chapter }{Timings for the general factorization routine}}\label{sec:TimingsForTheGeneralFactorizationRoutine}
\logpage{[ 4, 1, 0 ]}
\hyperdef{L}{X825FC33479FE2B1D}{}
{
  A few words in advance: In general, it is not possible to give a precise
prediction for the CPU time needed for factoring a given integer. This time
depends heavily on the sizes of the factors of the given number and on some
other properties which cannot be tested before actually doing the
factorization. But nevertheless, rough runtime estimates can be given for
numbers with factors of given orders of magnitude. 

 After casting out the small and other ``easy'' factors -- which should not take more than at most a few minutes for numbers
of ``reasonable'' size -- the general factorization routine uses first ECM (see{\nobreakspace}\texttt{FactorsECM} (\ref{FactorsECM:Elliptic Curves Method, ECM})) for finding factors very roughly up to the third root of the remaining
composite and then the MPQS (see{\nobreakspace}\texttt{FactorsMPQS} (\ref{FactorsMPQS:Multiple Polynomial Quadratic Sieve, MPQS})) for doing the ``rest'' of the work. The latter is often the most time-consuming part. 

 In the sequel, some timings for the ECM and for the MPQS are given. These
methods are by far the most important ones with respect to runtime statistics
(the $p \pm 1$-methods (see{\nobreakspace}\texttt{FactorsPminus1} (\ref{FactorsPminus1:Pollard's p-1}) and \texttt{FactorsPplus1} (\ref{FactorsPplus1:Williams' p+1})) are only suitable for finding factors with certain properties and CFRAC
(see{\nobreakspace}\texttt{FactorsCFRAC} (\ref{FactorsCFRAC:Continued Fraction Algorithm, CFRAC})) is just a slower predecessor of the MPQS). All absolute timings are given
for a Pentium{\nobreakspace}200 under Windows as a reference machine (this was
a fast machine at the time the first version of this package has been
written). }

  
\section{\textcolor{Chapter }{Timings for the ECM}}\label{sec:TimingsForTheECM}
\logpage{[ 4, 2, 0 ]}
\hyperdef{L}{X8131C8BD7F637545}{}
{
  The runtime of \texttt{FactorsECM} depends mainly on the size of the factors of the input number. On average,
finding a 12-digit factor of a 100-digit number takes about
1{\nobreakspace}min{\nobreakspace}40{\nobreakspace}s, finding a 15-digit
factor of a 100-digit number takes about 10{\nobreakspace}min and finding an
18-digit factor of a 100-digit number takes about 50{\nobreakspace}min.
A{\nobreakspace}general rule of thumb is the following: one digit more
increases the runtime by a bit less than a factor of two. These timings are
very rough, and they may vary by a factor of 10 or more. You can compare
trying an elliptic curve with throwing a couple of dice, where a success
corresponds to the case where all of them show the same side -- it is possible
to be successful with the first trial, but it is also possible that this takes
much longer. In particular, all trials are independent of one another. In
general, ECM is superior to Pollard's Rho for finding factors with at least 10
decimal digits. In the same time needed by Pollard's Rho for finding a
13-digit factor one can reasonably expect to find a 17-digit factor when using
ECM, for which Pollard's Rho in turn would need about 100 times as long
as{\nobreakspace}ECM. For larger factors this difference grows rapidly. From
theory it can be said that finding a 20-digit factor requires about 500 times
as much work as finding a 10-digit factor, finding a 30-digit factor requires
about 160 times as much work as finding a 20-digit factor and finding a
40-digit factor requires about 80 times as much work as finding a 30-digit
factor. 

 The default parameters are optimized for finding factors with about 15 -- 35
digits. This seems to be a sensible choice, since this is the most important
range for the application of ECM. The function \texttt{FactorsECM} usually gives up when the input number{\nobreakspace}$n$ has two factors which are both larger than its third root. This is of course
only a ``probabilistic'' statement. Sometimes -- but seldom -- the remaining composite has
3{\nobreakspace}factors, 4{\nobreakspace}factors should occur (almost) never. 

 The user can of course specify other parameters than the default ones, but
giving timings for all possible choices is obviously impossible. The
interested reader should follow the references given in the bibliography at
the end of this manual for getting information on how many curves with which
parameters are usually needed for finding factors of a given size. This
depends mainly on the distribution of primes, respectively of numbers with
prime factors not exceeding a certain bound. 

 For benchmarking purposes, the amount of time needed for trying a single curve
with given smoothness bounds for a number of given size is suited best. A
typical example is the following: one curve with (\mbox{\texttt{\slshape Limit1}},\mbox{\texttt{\slshape Limit2}}) = (100000,10000000) applied to a 100-digit integer requires a total of
10{\nobreakspace}min{\nobreakspace}20{\nobreakspace}s, where
6{\nobreakspace}min{\nobreakspace}45{\nobreakspace}s are spent for the first
stage and 3{\nobreakspace}min{\nobreakspace}35{\nobreakspace}s are spent for
the second stage. The time needed for the first stage is approximately linear
in \mbox{\texttt{\slshape Limit1}} and the time needed for the second stage is a bit less than linear in \mbox{\texttt{\slshape Limit2}}. }

  
\section{\textcolor{Chapter }{Timings for the MPQS}}\label{sec:TimingsForTheMPQS}
\logpage{[ 4, 3, 0 ]}
\hyperdef{L}{X7E2D09BD7AD0D77F}{}
{
  The runtime of \texttt{FactorsMPQS} depends only on the size of the input number, and not on the size of its
factors. Rough timings are as follows: 90{\nobreakspace}s for a 40-digit
number, 10{\nobreakspace}min for a 50-digit number, 2{\nobreakspace}h for a
60-digit number, 20{\nobreakspace}h for a 70-digit number and
100{\nobreakspace}h for a 75-digit number. These timings are much more precise
than those given for ECM, but they may also vary by a factor of 2
or{\nobreakspace}3 depending on whether a good factor base can be found
without using a large multiplier or not. A general rule of thumb is the
following: 10{\nobreakspace}digits more cause 10{\nobreakspace}times as much
work. For benchmarking purposes, precise timings for some integers are given: $38!+1$ (45{\nobreakspace}digits, good factor base with multiplier{\nobreakspace}1):
2{\nobreakspace}min{\nobreakspace}22{\nobreakspace}s, $40!-1$ (48{\nobreakspace}digits, not so good factor base even with
multiplier{\nobreakspace}7):
8{\nobreakspace}min{\nobreakspace}58{\nobreakspace}s, cofactor of $1093^{33}+1$ (61{\nobreakspace}digits, good factor base with multiplier{\nobreakspace}1):
1{\nobreakspace}h{\nobreakspace}12{\nobreakspace}min. }

  }

  \def\bibname{References\logpage{[ "Bib", 0, 0 ]}
\hyperdef{L}{X7A6F98FD85F02BFE}{}
}

\bibliographystyle{alpha}
\bibliography{factintbib.xml}

\def\indexname{Index\logpage{[ "Ind", 0, 0 ]}
\hyperdef{L}{X83A0356F839C696F}{}
}


\printindex

\newpage
\immediate\write\pagenrlog{["End"], \arabic{page}];}
\immediate\closeout\pagenrlog
\end{document}