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