1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2%% 3%% sf_alg_ideal.tex LiDIA documentation 4%% 5%% This file contains the documentation of the specialisation 6%% single_factor< alg_ideal >. 7%% 8%% Copyright (c) 1997 by LiDIA-Group 9%% 10%% Author: Stefan Neis 11%% 12 13\newcommand{\upperbound}{\mathit{upper\uscore bound}} 14\newcommand{\lowerbound}{\mathit{lower\uscore bound}} 15\newcommand{\fact}{\mathit{fact}} 16\newcommand{\step}{\mathit{step}} 17 18 19%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 20 21\NAME 22 23\CLASS{single_factor< alg_ideal >} \dotfill a factor of an ideal in an 24algebraic number field 25 26 27%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 28 29\ABSTRACT 30 31\code{single_factor< alg_ideal >} is used for storing factorizations of ideals of algebraic 32number fields (see \code{factorization}). It is a specialization of \code{single_factor< T >} 33with some additional functionality. All functions for \code{single_factor< T >} can be applied 34to objects of class \code{single_factor< alg_ideal >}, too. These basic functions are not 35described here any further; you will find the description of the latter in \code{single_factor< 36 T >}. 37 38 39%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 40 41\DESCRIPTION 42 43%\section{single_factor< alg_ideal >} 44 45%\STITLE{Constructor} 46 47 48%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 49 50\ACCS 51 52Let $a$ be an instance of type \code{single_factor< alg_ideal >}. 53 54\begin{cfcode}{prime_ideal}{$a$.prime_base}{} 55 If \code{$a$.is_prime_factor()} returns \TRUE, then $a$ represents a \code{prime_ideal} which 56 is returned by this function. If \code{$a$.is_prime_factor()} returns \FALSE, calling this 57 function will result in unpredictable behaviour. 58\end{cfcode} 59 60 61%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 62 63\HIGH 64 65Let $a$ be an instance of type \code{single_factor< alg_ideal >}. 66 67\STITLE{Queries} 68 69\begin{fcode}{bool}{$a$.is_prime_factor}{int $\mathit{test}$ = 0} 70 Note that contrary to the general description, calling this routine with $\mathit{test} \neq 71 0$ will not perform an explicit test if we do not yet know, whether or not $a$ is prime, since 72 no efficient test is implemented. Instead, this will result in an error message. If you need 73 to know, whether or not a \code{single_factor< alg_ideal >} is prime, call this function 74 without parameter and if the result is not ``prime'', call the function \code{factor} and 75 check the factorization. 76\end{fcode} 77 78\STITLE{Factorization Algorithms} 79 80If one tries to factor an integral ideal of an algebraic number field, the hard part is to find 81a factorization of the smallest strictly positive integer in this ideal. If this factorization 82has been succesfully computed, the remaining computations can be done in (probabilistic) 83polynomial time as described e.g.~in \cite{Cohen:1995}, chapter 4.8.2 (for numbers not dividing 84the index) and \cite{Buchmann/LenstraHW} or \cite{Weber_Thesis:1993} (for index divisors). 85 86For fractional ideals, one needs to factor the denominator in addition, however, this can be 87handled separately. 88 89Therefore the generic factorization functions are 90 91\begin{fcode}{factorization< alg_ideal >}{finish}{const alg_ideal & $a$, 92 rational_factorization & $f$}% 93 returns the factorization of the numerator of $a$. $f$ must contain a factorization of the 94 smallest strictly positive integer in this ideal. 95\end{fcode} 96 97\begin{cfcode}{factorization< alg_ideal >}{$a$.finish}{rational_factorization & $f$} 98 returns \code{finish($a$.base(), $f$)}. 99\end{cfcode} 100 101To avoid copying objects, there are also the following variations of these calls: 102 103\begin{fcode}{void}{finish}{factorization< alg_ideal > & $\fact$, 104 const alg_ideal & $a$, rational_factorization & $f$}% 105 stores the factorization of the numerator of $a$ to $\fact$. $f$ must contain a factorization 106 of the smallest strictly positive integer in this ideal. 107\end{fcode} 108 109\begin{cfcode}{void}{$a$.finish}{factorization< alg_ideal > & $\fact$, 110 rational_factorization & $f$}% 111 stores the factorization of the numerator of \code{$a$.base()} to $\fact$. $f$ must contain a 112 factorization of the smallest strictly positive integer in this ideal. 113\end{cfcode} 114 115 116%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 117 118In general, our factorization routines use the following strategy: First, we compute the 119smallest strictly positive integer in an ideal. Then some function of the class 120\code{rational_factorization} is called to factor this integer. Finally, we call \code{finish} 121to obtain the factorization of the ideal. 122 123To enable the user to use the full power of the factorization routines of class 124\code{rational_factorization}, we reuse the interface of this class. Thus we obtain the 125following functions: 126 127\begin{cfcode}{factorization< alg_ideal >}{$a$.factor}{int $\upperbound$ = 34} 128 returns the factorization of \code{$a$.base()} using the function \code{factor} of class 129 \code{rational_factorization} with the given parameter to compute the factorization of the 130 smallest strictly positive integer in the ideal. 131\end{cfcode} 132 133\begin{fcode}{factorization< alg_ideal >}{factor}{const alg_ideal & $a$, 134 int $\upperbound$ = 34}% 135 returns the factorization of $a$ using the function \code{factor} of class 136 \code{rational_factorization} with the given parameter to compute the factorization of the 137 smallest strictly positive integer in the ideal. 138\end{fcode} 139 140\begin{cfcode}{void}{$a$.factor}{factorization< alg_ideal > & $\fact$, 141 int $\upperbound$ = 34}% 142 stores the factorization of \code{$a$.base()} to $\fact$ using the function \code{factor} of 143 class \code{rational_factorization} with the given parameter to compute the factorization of 144 the smallest strictly positive integer in the ideal. 145\end{cfcode} 146 147\begin{fcode}{void}{factor}{factorization< alg_ideal > & $\fact$, 148 const alg_ideal & $a$, int $\upperbound$ = 34}% 149 stores the factorization of $a$ to $\fact$ using the function \code{factor} of class 150 \code{rational_factorization} with the given parameter to compute the factorization of the 151 smallest strictly positive integer in the ideal. 152\end{fcode} 153 154 155%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 156 157\begin{cfcode}{factorization< alg_ideal >}{$a$.trialdiv}{unsigned int $\upperbound$ = 1000000, 158 unsigned int $\lowerbound$ = 1}% 159 returns the factorization of \code{$a$.base()} using the function \code{trialdiv} of class 160 \code{rational_factorization} with the given parameters to compute the factorization of the 161 smallest strictly positive integer in the ideal. 162\end{cfcode} 163 164\begin{fcode}{factorization< alg_ideal >}{trialdiv}{const alg_ideal & $a$, 165 unsigned int $\upperbound$ = 1000000, unsigned int $\lowerbound$ = 1}% 166 returns the factorization of $a$ using the function \code{trialdiv} of class 167 \code{rational_factorization} with the given parameters to compute the factorization of the 168 smallest strictly positive integer in the ideal. 169\end{fcode} 170 171\begin{cfcode}{void}{$a$.trialdiv}{factorization< alg_ideal > & $\fact$, 172 unsigned int $\upperbound$ = 1000000, unsigned int $\lowerbound$ = 1}% 173 stores the factorization of \code{$a$.base()} to $\fact$ using the function \code{trialdiv} of 174 class \code{rational_factorization} with the given parameters to compute the factorization of 175 the smallest strictly positive integer in the ideal. 176\end{cfcode} 177 178\begin{fcode}{void}{trialdiv}{factorization< alg_ideal > & $\fact$, const alg_ideal & $a$, 179 unsigned int $\upperbound$ = 1000000, unsigned int $\lowerbound$ = 1}% 180 stores the factorization of $a$ to $\fact$ using the function \code{trialdiv} of class 181 \code{rational_factorization} with the given parameters to compute the factorization of the 182 smallest strictly positive integer in the ideal. 183\end{fcode} 184 185 186%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 187 188\begin{cfcode}{factorization< alg_ideal >}{$a$.ecm}{int $\upperbound$ = 34, 189 int $\lowerbound$ = 6, int $\step$ = 3}% 190 returns the factorization of \code{$a$.base()} using the function \code{ecm} of class 191 \code{rational_factorization} with the given parameters to compute the factorization of the 192 smallest strictly positive integer in the ideal. 193\end{cfcode} 194 195\begin{fcode}{factorization< alg_ideal >}{ecm}{const alg_ideal & $a$, 196 int $\upperbound$ = 34, int $\lowerbound$ = 6, int $\step$ = 3}% 197 returns the factorization of $a$ using the function \code{ecm} of class 198 \code{rational_factorization} with the given parameters to compute the factorization of the 199 smallest strictly positive integer in the ideal. 200\end{fcode} 201 202\begin{cfcode}{void}{$a$.ecm}{factorization< alg_ideal > & $\fact$, 203 int $\upperbound$ = 34, int $\lowerbound$ = 6, int $\step$ = 3}% 204 stores the factorization of \code{$a$.base()} to $\fact$ using the function \code{ecm} of 205 class \code{rational_factorization} with the given parameters to compute the factorization of 206 the smallest strictly positive integer in the ideal. 207\end{cfcode} 208 209\begin{fcode}{void}{ecm}{factorization< alg_ideal > & $\fact$, 210 const alg_ideal & $a$, int $\upperbound$ = 34, int $\lowerbound$ = 6, int $\step$ = 3}% 211 stores the factorization of $a$ to $\fact$ using the function \code{ecm} of class 212 \code{rational_factorization} with the given parameters to compute the factorization of the 213 smallest strictly positive integer in the ideal. 214\end{fcode} 215 216 217%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 218 219\begin{cfcode}{factorization< alg_ideal >}{$a$.mpqs}{} 220 returns the factorization of \code{$a$.base()} using the function \code{mpqs} of class 221 \code{rational_factorization} to compute the factorization of the smallest strictly positive 222 integer in the ideal. 223\end{cfcode} 224 225\begin{fcode}{factorization< alg_ideal >}{mpqs}{const alg_ideal & $a$} 226 returns the factorization of $a$ using the function \code{mpqs} of class 227 \code{rational_factorization} to compute the factorization of the smallest strictly positive 228 integer in the ideal. 229\end{fcode} 230 231\begin{cfcode}{void}{$a$.mpqs}{factorization< alg_ideal > & $\fact$} 232 stores the factorization of \code{$a$.base()} to $\fact$ using the function \code{mpqs} of 233 class \code{rational_factorization} to compute the factorization of the smallest strictly 234 positive integer in the ideal. 235\end{cfcode} 236 237\begin{fcode}{void}{mpqs}{factorization< alg_ideal > & $\fact$, 238 const alg_ideal & $a$} stores the factorization of $a$ to $\fact$ using the function 239 \code{mpqs} of class \code{rational_factorization} to compute the factorization of the 240 smallest strictly positive integer in the ideal. 241\end{fcode} 242 243 244%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 245 246\SEEALSO 247 248\SEE{factorization< T >}, \SEE{alg_ideal}, 249\SEE{prime_ideal}, 250\SEE{rational_factorization} 251 252 253%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 254% WARNINGS 255%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 256 257\WARNINGS 258 259Using \code{factor} or \code{mpqs} requires write permission in the \path{/tmp} directory or in 260the directory from which they are called. This is necessary because \code{mpqs} creates 261temporary files. 262 263 264%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 265 266\EXAMPLES 267 268\begin{quote} 269\begin{verbatim} 270#include <LiDIA/alg_ideal.h> 271#include <LiDIA/prime_ideal.h> 272#include <LiDIA/factorization.h> 273 274int main() 275{ 276 277 alg_ideal f; 278 279 factorization< alg_ideal > u; 280 281 cout << "Please enter f : "; cin >> f ; 282 283 u = factor(f); 284 285 cout << "\nFactorization of f :\n" << u << endl; 286 287} 288\end{verbatim} 289\end{quote} 290 291 292%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 293 294\AUTHOR 295 296Stefan Neis, Anja Steih, Damian Weber 297