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