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