1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%%  sf_Fp_polynomial.tex       LiDIA documentation
4%%
5%%  This file contains the documentation of the specialisation
6%%  single_factor< Fp_polynomial >, factorization< Fp_polynomial >.
7%%
8%%  Copyright   (c)   1996   by  LiDIA-Group
9%%
10%%  Authors: Thomas Pfahler
11%%
12
13
14%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
15
16\NAME
17
18\CLASS{single_factor< Fp_polynomial >} \dotfill a single factor of
19a polynomial over finite prime fields
20
21
22%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
23
24\ABSTRACT
25
26\code{single_factor< Fp_polynomial >} is used for storing factorizations of polynomials over
27finite prime fields (see \code{factorization}).  It is a specialization of \code{single_factor<
28  T >} with some additional functionality.  All functions for \code{single_factor< T >} can be
29applied to objects of class \code{single_factor< Fp_polynomial >}, too.  These basic functions
30are not described here any further; you will find the description of the latter in
31\code{single_factor< T >}.
32
33
34%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35
36\DESCRIPTION
37
38%\section{single_factor< Fp_polynomial >}
39
40%\STITLE{Constructor}
41
42
43\STITLE{Modifying Operations}
44
45Let $a$ be an instance of type \code{single_factor< Fp_polynomial >}.
46
47\begin{fcode}{bigint}{$a$.extract_unit}{}
48  returns the leading coefficient of \code{$a$.base()} and converts it to a monic polynomial (by
49  dividing it by its leading coefficient).
50\end{fcode}
51
52
53\STITLE{Factorization Algorithms}
54
55The implementation of the factorization algorithms is described in \cite{Pfahler_Thesis:1998}.
56
57Let $a$ be an instance of type \code{single_factor< Fp_polynomial >}.
58
59\begin{fcode}{factorization< Fp_polynomial >}{square_free_decomp}{const Fp_polynomial & $f$}
60  returns the factorization of $f$ into square-free factors.  $f$ must be monic, otherwise the
61  \LEH is invoked.
62\end{fcode}
63
64\begin{cfcode}{factorization< Fp_polynomial >}{$a$.square_free_decomp}{}
65  returns \code{square_free_decomp($a$.base())}.
66\end{cfcode}
67
68
69%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
70
71\begin{fcode}{factorization< Fp_polynomial >}{berlekamp}{const Fp_polynomial & $f$}
72  returns the complete factorization of $f$ using Berlekamp's factoring algorithm.  If $f$ is
73  the zero polynomial, the \LEH is invoked.
74\end{fcode}
75
76\begin{cfcode}{factorization< Fp_polynomial >}{$a$.berlekamp}{}
77  returns \code{berlekamp($a$.base())}.
78\end{cfcode}
79
80\begin{fcode}{factorization< Fp_polynomial >}{sf_berlekamp}{const Fp_polynomial & $f$}
81  returns the complete factorization of $f$ using Berlekamp's factoring algorithm.  $f$ must be
82  monic and square-free with a non-zero constant term; otherwise the behaviour of this function
83  is undefined.
84\end{fcode}
85
86\begin{cfcode}{factorization< Fp_polynomial >}{$a$.sf_berlekamp}{}
87  returns \code{sf_berlekamp($a$.base())}.
88\end{cfcode}
89
90
91%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92
93\begin{fcode}{factorization< Fp_polynomial >}{can_zass}{const Fp_polynomial & $f$}
94  returns the complete factorization of $f$ using \code{sf_can_zass}.  If $f$ is the zero
95  polynomial, the \LEH is invoked.  Note that as \code{ddf} creates temporary files, you need
96  write permission either in the \path{/tmp}-directory or in the directory from which it is
97  called.
98
99  This function uses less memory than \code{berlekamp} when factoring polynomials of large
100  degrees.
101\end{fcode}
102
103\begin{cfcode}{factorization< Fp_polynomial >}{$a$.can_zass}{}
104  returns \code{can_zass($a$.base())}.
105\end{cfcode}
106
107\begin{fcode}{factorization< Fp_polynomial >}{sf_can_zass}{const Fp_polynomial & $f$}
108  returns the complete factorization of $f$ using \code{ddf} and the von zur Gathen/Shoup
109  algorithm for factoring polynomials whose irreducible factors all have the same degree.
110
111  $f$ must be monic and square-free, otherwise the behaviour of this function is undefined.
112  Note that as \code{ddf} creates temporary files, you need write permission either in the
113  \path{/tmp} directory or in the directory from which it is called.
114
115  This function uses less memory than \code{sf_berlekamp} when factoring polynomials of large
116  degrees.
117\end{fcode}
118
119\begin{cfcode}{factorization< Fp_polynomial >}{$a$.sf_can_zass}{}
120returns \code{sf_can_zass($a$.base())}.
121\end{cfcode}
122
123\begin{fcode}{factorization< Fp_polynomial >}{ddf}{const Fp_polynomial & $f$}
124  performs a ``distinct degree factorization''.
125
126  Returns the factorization of $f$ into a product of factors, where each factor is the product
127  of distinct irreducibles all of the same degree, using Shoup's algorithm \cite{Shoup:1995}.
128  \emph{The exponents} of this factorization do not give the multipicities of these factors
129  (which would be 1) \emph{but the degrees} of the
130  irreducibles.
131
132  $f$ must be monic and square-free, otherwise the behaviour of this function is undefined.
133  Note that as \code{ddf} creates temporary files, you need write permission either in the
134  \path{/tmp} directory or in the directory from which it is called.
135\end{fcode}
136
137\begin{cfcode}{factorization< Fp_polynomial >}{$a$.ddf}{}
138  returns \code{ddf($a$.base())}.
139\end{cfcode}
140
141%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
142
143
144\begin{fcode}{factorization< Fp_polynomial >}{edf}{const Fp_polynomial & $f$, lidia_size_t $d$}
145  performs an ``equal degree factorization''.  Assumes that $f$ is a monic polynomial whose
146  irreducible factors all have degree $d$ (otherwise, the behaviour of this function is
147  undefined); returns the complete factorization of $f$ using an algorithm of von zur
148  Gathen/Shoup \cite{vzGathen/Shoup:1992}.
149\end{fcode}
150
151\begin{cfcode}{factorization< Fp_polynomial >}{$a$.edf}{lidia_size_t $d$}
152  returns \code{edf($a$.base(), $d$)}.
153\end{cfcode}
154
155
156%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
157
158\begin{fcode}{factorization< Fp_polynomial >}{factor}{const Fp_polynomial & $f$}
159  returns the complete factorization of $f$ using a strategy which tries to apply always the
160  fastest of the above algorithms.  It also includes special variants for factoring binomials.
161  The strategy is explained in detail in \cite{Pfahler_Thesis:1998}.  If $f$ is the zero
162  polynomial, the \LEH is invoked.
163\end{fcode}
164
165\begin{cfcode}{factorization< Fp_polynomial >}{$a$.factor}{}
166  returns \code{factor($a$.base())}.
167\end{cfcode}
168
169
170%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
171
172\SEEALSO
173
174\SEE{factorization< T >}, \SEE{Fp_polynomial}
175
176
177%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
178
179\WARNINGS
180
181Using \code{can_zass}, \code{sf_can_zass} or \code{ddf} requires write permission in the
182\path{/tmp} directory or in the directory from which they are called.  This is necessary because
183\code{ddf} creates temporary files.
184
185
186%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
187
188\EXAMPLES
189
190\begin{quote}
191\begin{verbatim}
192#include <LiDIA/Fp_polynomial.h>
193#include <LiDIA/factorization.h>
194
195int main()
196{
197    Fp_polynomial f;
198    factorization< Fp_polynomial > u;
199
200    cout << "Please enter f : "; cin >> f ;
201    u = factor(f);
202    cout << "\nFactorization of f :\n" << u << endl;
203
204    return 0;
205}
206\end{verbatim}
207\end{quote}
208
209%example:
210%
211%\code{Please enter f : X^3 - 2*X - 1 mod 5}
212%
213%\code{Factorization of f :}
214%\code{[ [[1 1] mod 5,1], [[2 1] mod 5,2] ]}
215%
216
217For further examples please refer to
218\path{LiDIA/src/templates/factorization/Fp_polynomial/Fp_pol_factor_appl.cc}.
219
220
221%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
222
223\AUTHOR
224
225Victor Shoup, Thomas Pfahler
226