1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%%  sf_bigint.tex       LiDIA documentation
4%%
5%%  This file contains the documentation of the specialisation
6%%  single_factor< bigint >, factorization< bigint >.
7%%
8%%  Copyright   (c)   1998  by  LiDIA-Group
9%%
10%%  Author: Volker Mueller
11%%
12
13\newcommand{\upperbound}{\mathit{upper\uscore bound}}
14\newcommand{\lowerbound}{\mathit{lower\uscore bound}}
15\newcommand{\size}{\mathit{size}}
16\newcommand{\step}{\mathit{step}}
17
18
19%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
20
21\NAME
22\CLASS{single_factor< bigint >} \dotfill a single factor of a bigint
23
24
25%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
26
27\ABSTRACT
28
29\code{single_factor< bigint >} is used for storing a single factor of a factorization of
30rational integers (see the general template class \code{factorization< T >}).  It is a
31specialization of \code{single_factor< T >} with some additional functionality, namely different
32factorization algorithms.
33
34
35%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
36
37\DESCRIPTION
38
39\code{single_factor< bigint >} is used for storing a single factor of a factorization of
40rational integers (see the general template class \code{factorization< T >}).  It is a
41specialization of \code{single_factor< T >} with some additional functionality, namely different
42factorization algorithms.  All functions for \code{single_factor< T >} can be applied to objects
43of class \code{single_factor< bigint >}, too.  These basic functions are not described here any
44further; you will find the description of the latter in \code{single_factor< T >}.
45
46At the moment we have implemented the following factorization algorithms: trial division (TD),
47Pollard Rho algorithm, Pollard $p-1$ algorithm, Williams $p+1$ algorithm, the elliptic curve
48method (\emph{ECM}) and the self initializing variant of the Quadratic sieve (\emph{MPQS}) with
49Block Lanczos algorithm as system solver.  The Pollard $p-1$ algorithm, Williams $p+1$
50algorithm, and \emph{ECM} use the so called Improved Standard Continuation.  A description of
51the theory of these algorithms can for example be found in \cite{Riesel:1994},
52\cite{Alford/Pomerance:1993}, and in several diploma theses (see \cite{Denny_Thesis:1993},
53\cite{Sosnowski_Thesis:1994}, \cite{Berger_Thesis:1993}, \cite{Mueller_Thesis:1995}).
54
55We do not describe the general template functions offered by \code{single_factor< T >}.  A
56description for these functions can be found in the manual for this template class.  Here we
57concentrate on the different factorization algorithms implemented for factorization of rational
58integers.  These factorization algorithm usually stop after a non trivial factor of the input
59number has been found.  Therefore note that the result of a factorization algorithm is not
60necessary a prime factorization.  Moreover it is possible that the returned factorization just
61has one member, namely the input number itself.  This can happen when the used factorization
62algorithm has not found a proper factor.
63
64
65%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
66
67\STITLE{Factorization Algorithms}
68
69Let $a$ be an instance of type \code{single_factor< bigint >}.
70
71It should be mentioned that all factorization implementations which have some integer $x$ as
72input return in any case a factorization which has the same value as $x$.  If a factor of $x$
73has been found, then the result is a non trivial factorization; otherwise the result is a
74trivial factorization holding only $x$ itself.
75
76\begin{fcode}{factorization< bigint >}{$a$.TrialDiv}{unsigned int $\upperbound$ = 1000000,
77    unsigned int $\lowerbound$ = 1}%
78  tries to factor the integer stored in $a$ by using \emph{TD} with all primes $p$ satisfying
79  $\lowerbound \leq p \leq \upperbound$.  For unreasonable parameters as negative values for
80  $\lowerbound$, the \LEH is invoked.  Found factors (with appropriate exponents) are returned
81  as factorization.  If the found factorization is a prime factorization, then the complete
82  prime factorization is returned and $a$ is set to one.  Otherwise found factors are returned
83  as factorization and $a$ is set to the remaining composite part.
84\end{fcode}
85
86\begin{fcode}{factorization< bigint >}{TrialDiv}{const bigint & $x$, unsigned int $\upperbound$ = 1000000,
87    unsigned int $\lowerbound$ = 1}%
88  tries to factor the integer $x$ by using \emph{TD} with all primes $p$ satisfying $\lowerbound
89  \leq p \leq \upperbound$.  The function returns the factorization found with this method.
90  Unreasonable input leads to a call to the \LEH.
91\end{fcode}
92
93\begin{fcode}{factorization< bigint >}{$a$.PollardPminus1}{int $\size$ = 9}
94  tries to factor the integer stored in $a$ by using Pollard's $(p-1)$ method.  Parameters are
95  chosen as in \emph{ECM} for finding factors of size $\size$ with some probability.  If a
96  factor is found, the factorization of $a$ is returned and $a$ is set to one; otherwise $a$
97  remains unchanged and an empty factorization is returned.  Unreasonable values for $\size$
98  lead to a call of the \LEH.
99\end{fcode}
100
101\begin{fcode}{factorization< bigint >}{PollardPminus1}{const bigint & $x$, int $\size$ = 9}
102  tries to factor the integer $x$ by using Pollard's $(p-1)$ method.  Parameters are chosen as in
103  \emph{ECM} to find factors of size $\size$ with some probability.  A factorization of $x$
104  is returned.
105\end{fcode}
106
107\begin{fcode}{factorization< bigint >}{$a$.PollardRho}{int $\size$ = 7}
108  tries to factor the integer stored in $a$ by using Pollard's rho method.  Parameters are
109  chosen for finding factors of size $\size$ with some probability.  If a factor is found, the
110  factorization is returned and $a$ is set to one; otherwise $a$ remains unchanged and an empty
111  factorization is returned.  Unreasonable values for $\size$ lead to a call of the \LEH.
112\end{fcode}
113
114\begin{fcode}{factorization< bigint >}{PollardRho}{const bigint & $x$, int $\size$ = 9}
115  tries to factor the integer $x$ by using Pollard's rho method.  Parameters are chosen for
116  finding factors of size $\size$.  A factorization of $x$ is returned.  Unreasonable values
117  for $\size$ lead to a call of the \LEH.
118\end{fcode}
119
120\begin{fcode}{factorization< bigint >}{$a$.WilliamsPplus1}{int $\size$ = 9}
121  tries to factor the integer stored in $a$ by using Williams $p+1$ method.  Parameters are
122  chosen as in \emph{ECM} to find factors of size $\size$ with some probability.  If a
123  factor is found, the factorization is returned and $a$ is set to one; otherwise $a$ is
124  unchanged and an empty factorization is returned.  Unreasonable values for $\size$ lead to
125  a call of the \LEH.
126\end{fcode}
127
128\begin{fcode}{factorization< bigint >}{WillaimsPplus1}{const bigint & $x$, int $\size$ = 9}
129  tries to factor the integer $x$ by using Williams $p+1$ method.  Parameters are chosen as in
130  \emph{ECM} to find factors of size $\size$ with some probability.  A factorization of $x$
131  is returned.  Unreasonable values for $\size$ lead to a call to the \LEH.
132\end{fcode}
133
134\begin{fcode}{factorization< bigint >}{$a$.Fermat}{}
135  tries to factor the integer stored in $a$ by using Fermat's method with a fixed number of
136  iterations.  If a factor is found, this factorization is returned and $a$ is set to one;
137  otherwise $a$ is unchanged and an empty factorization is returned.
138\end{fcode}
139
140\begin{fcode}{factorization< bigint >}{Fermat}{const bigint & $x$}
141  tries to factor the integer stored in $x$ by using Fermat's method with a fixed number of
142  iterations.  A factorization of $x$ is returned.
143\end{fcode}
144
145The following functions require some understanding of the underlying strategy of \emph{ECM}.  A
146detailed description of the implementation of \emph{TD} and \emph{ECM} can be found in
147\cite{Berger_Thesis:1993} and \cite{Mueller_Thesis:1995}.  \emph{ECM} uses the following
148strategy, which is parameterized by the int variables $\lowerbound$, $\upperbound$ and $\step$.
149These variables can be chosen by the user.  It starts to look for factors with $\lowerbound$
150decimal digits.  After having tried a ``few'' curves and not having found a factor the
151parameters of \emph{ECM} are changed and we try to find $(\lowerbound + \step)$-digit factors,
152$(\lowerbound + 2\,step)$-digit factors and so on, until the decimal size of the factors we are
153looking for exceeds $\upperbound$.  The number of curves which is used for finding a $d$-digit
154factor is chosen such that we find a $d$-digit factor with probability of at least $50 \%$ if it
155exists.  Note that found factors can be composite.  The built-in default values are $\lowerbound
156= 6, \step = 3$ and $\upperbound$ is set to half the decimal length of the number to be factored.
157The bounds $\lowerbound \geq 6$ and $\upperbound \leq 34$ are limited because we have only
158precomputed parameters for \emph{ECM} for factors of that size.
159
160\begin{fcode}{factorization< bigint >}{$a$.ECM}{int $\upperbound$ = 34,
161    int $\lowerbound$ = 6, int $\step$ = 3, bool jump_to_QS = false}%
162  tries to factor the integer stored in $a$ by using the ECM method with the strategy described
163  above.  If \code{jump_to_QS} is set to \TRUE, then the function uses some heuristic to check
164  whether \emph{MPQS} would be faster, if so, it starts the \emph{MPQS} algorithm to factor the
165  integer.  The function returns a factorization of the integer stored in $a$.  If a proper
166  factor was found, then $a$ is set to one.
167\end{fcode}
168
169\begin{fcode}{factorization< bigint >}{ECM}{const bigint & $x$,
170    int $\upperbound$ = 34, int $\lowerbound$ = 6, int $\step$ = 3}
171  tries to factor the integer stored in $x$ by using the \emph{ECM} method with the strategy
172  described above.  A factorization of $x$ is returned.
173\end{fcode}
174
175The version of \emph{MPQS} used in \LiDIA is called self initializing multiple polynomial large
176prime quadratic sieve.  A description of the algorithm can be found in
177\cite{Alford/Pomerance:1993}, \cite{Denny_Thesis:1993} or \cite{Sosnowski_Thesis:1994}.  The
178linear equation step uses an implementation of the Block Lanczos algorithm for $\bbfZ/2\bbfZ$.
179Note that the running time of \emph{MPQS} depends on the size of the number to be factored, not
180on the size of the factors.
181
182\begin{fcode}{factorization< bigint >}{$a$.MPQS}{}
183  returns a factorization of the integer stored in $a$ by using the \emph{MPQS} method.
184\end{fcode}
185
186\begin{fcode}{factorization< bigint >}{MPQS}{const bigint & $x$}
187  returns a factorization of the integer $x$ by using the \emph{MPQS} method.
188\end{fcode}
189
190
191%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
192
193\begin{cfcode}{factorization< bigint >}{$a$.factor}{int $\size$ = 34}
194  returns a factorization of $a$ using a strategy which tries to apply an ``optimal''
195  combination of the above algorithms.  Parameters are chosen such that the algorithms whose
196  running time depends on the size of the factor will find factors of size $\size$ with 50 \%
197  probability.  A factorization of $a$ is returned, $a$ is set to one.
198\end{cfcode}
199
200\begin{fcode}{factorization< bigint >}{sf_factor}{const bigint & $x$, int $\size$ = 34}
201  returns a factorization of $x$ using a strategy which tries to apply an ``optimal''
202  combination of the above algorithms.  Parameters are chosen such that the algorithms whose
203  running time depends on the size of the factor will find factors of size $\size$ with 50 \%
204  probability.
205\end{fcode}
206
207\begin{cfcode}{factorization< bigint >}{$a$.completely_factor}{}
208  returns a prime factorization of $a$ using a strategy which tries to apply always the fastest
209  of the above algorithms.  $a$ is set to one.
210\end{cfcode}
211
212\begin{fcode}{factorization< bigint >}{completely_factor}{const bigint & $x$}
213  returns a prime factorization of $x$ using a strategy which tries to apply an ``optimal''
214  combination of the above algorithms.
215\end{fcode}
216
217
218%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
219
220\SEEALSO
221
222\SEE{factorization< T >}, \SEE{bigint},
223\SEE{single_factor< T >},
224\SEE{rational_factorization}.
225
226
227%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
228
229\WARNINGS
230
231\emph{ECM} fails to factor integers that only consist of prime factors smaller than $1000$.
232Therefore it is strongly recommended to use the function \code{sf_factor} or to ensure with the
233function \code{TrialDiv}, that there are no such small prime factors left before calling
234functions which use \emph{ECM}.
235
236
237%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
238
239\EXAMPLES
240
241\begin{quote}
242\begin{verbatim}
243#include <LiDIA/bigint.h>
244#include <LiDIA/factorization.h>
245
246int main()
247{
248    bigint f;
249    factorization< bigint > u;
250
251    cout << "Please enter f : "; cin >> f ;
252
253    u = sf_factor(f);
254
255    cout << "\nFactorization of f : " << u << endl;
256
257    return 0;
258}
259\end{verbatim}
260\end{quote}
261
262For further examples please refer to
263\path{LiDIA/src/templates/factorization/bigint/fact_bi_appl.cc}.
264
265
266%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
267
268\AUTHOR
269
270Volker M\"uller, based on previous implementations of Oliver Braun and
271Emre Binisik.
272