1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
|
/*=============================================================================
This file is part of FLINT.
FLINT is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
FLINT is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with FLINT; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
=============================================================================*/
/******************************************************************************
Copyright (C) 2010 William Hart
Copyright (C) 2011 Fredrik Johansson
Copyright (C) 2011 Sebastian Pancratz
******************************************************************************/
*******************************************************************************
Factorisation
*******************************************************************************
void nmod_poly_factor_init(nmod_poly_factor_t fac)
Initialises \code{fac} for use. An \code{nmod_poly_factor_t}
represents a polynomial in factorised form as a product of
polynomials with associated exponents.
void nmod_poly_factor_clear(nmod_poly_factor_t fac)
Frees all memory associated with \code{fac}.
void nmod_poly_factor_realloc(nmod_poly_factor_t fac, slong alloc)
Reallocates the factor structure to provide space for
precisely \code{alloc} factors.
void nmod_poly_factor_fit_length(nmod_poly_factor_t fac, slong len)
Ensures that the factor structure has space for at
least \code{len} factors. This functions takes care
of the case of repeated calls by always at least
doubling the number of factors the structure can hold.
void nmod_poly_factor_set(nmod_poly_factor_t res, const nmod_poly_factor_t fac)
Sets \code{res} to the same factorisation as \code{fac}.
void nmod_poly_factor_print(const nmod_poly_factor_t fac)
Prints the entries of \code{fac} to standard output.
void nmod_poly_factor_insert(nmod_poly_factor_t fac,
const nmod_poly_t poly, slong exp)
Inserts the factor \code{poly} with multiplicity \code{exp} into
the factorisation \code{fac}.
If \code{fac} already contains \code{poly}, then \code{exp} simply
gets added to the exponent of the existing entry.
void nmod_poly_factor_concat(nmod_poly_factor_t res,
const nmod_poly_factor_t fac)
Concatenates two factorisations.
This is equivalent to calling \code{nmod_poly_factor_insert()}
repeatedly with the individual factors of \code{fac}.
Does not support aliasing between \code{res} and \code{fac}.
void nmod_poly_factor_pow(nmod_poly_factor_t fac, slong exp)
Raises \code{fac} to the power \code{exp}.
ulong nmod_poly_remove(nmod_poly_t f, const nmod_poly_t p)
Removes the highest possible power of \code{p} from \code{f} and
returns the exponent.
int nmod_poly_is_irreducible(const nmod_poly_t f)
Returns 1 if the polynomial \code{f} is irreducible, otherwise returns 0.
int nmod_poly_is_irreducible_ddf(const nmod_poly_t f)
Returns 1 if the polynomial \code{f} is irreducible, otherwise returns 0.
Uses fast distinct-degree factorisation.
int nmod_poly_is_irreducible_rabin(const nmod_poly_t f)
Returns 1 if the polynomial \code{f} is irreducible, otherwise returns 0.
Uses Rabin irreducibility test.
int _nmod_poly_is_squarefree(mp_srcptr f, slong len, nmod_t mod)
Returns 1 if \code{(f, len)} is squarefree, and 0 otherwise. As a
special case, the zero polynomial is not considered squarefree.
There are no restrictions on the length.
int nmod_poly_is_squarefree(const nmod_poly_t f)
Returns 1 if \code{f} is squarefree, and 0 otherwise. As a special
case, the zero polynomial is not considered squarefree.
void nmod_poly_factor_squarefree(nmod_poly_factor_t res, const nmod_poly_t f)
Sets \code{res} to a square-free factorization of \code{f}.
int nmod_poly_factor_equal_deg_prob(nmod_poly_t factor,
flint_rand_t state, const nmod_poly_t pol, slong d)
Probabilistic equal degree factorisation of \code{pol} into
irreducible factors of degree \code{d}. If it passes, a factor is
placed in factor and 1 is returned, otherwise 0 is returned and
the value of factor is undetermined.
Requires that \code{pol} be monic, non-constant and squarefree.
void nmod_poly_factor_equal_deg(nmod_poly_factor_t factors,
const nmod_poly_t pol, slong d)
Assuming \code{pol} is a product of irreducible factors all of
degree \code{d}, finds all those factors and places them in factors.
Requires that \code{pol} be monic, non-constant and squarefree.
void nmod_poly_factor_distinct_deg(nmod_poly_factor_t res,
const nmod_poly_t poly, slong * const *degs)
Factorises a monic non-constant squarefree polymnomial \code{poly}
of degree n into factors $f[d]$ such that for $1 \leq d \leq n$
$f[d]$ is the product of the monic irreducible factors of \code{poly}
of degree $d$. Factors $f[d]$ are stored in \code{res}, and the degree $d$
of the irreducible factors is stored in \code{degs} in the same order
as the factors.
Requires that \code{degs} has enough space for $(n/2)+1 * sizeof(slong)$.
void nmod_poly_factor_cantor_zassenhaus(nmod_poly_factor_t res,
const nmod_poly_t f)
Factorises a non-constant polynomial \code{f} into monic irreducible
factors using the Cantor-Zassenhaus algorithm.
void nmod_poly_factor_berlekamp(nmod_poly_factor_t res, const nmod_poly_t f)
Factorises a non-constant, squarefree polynomial \code{f} into monic
irreducible factors using the Berlekamp algorithm.
void nmod_poly_factor_kaltofen_shoup(nmod_poly_factor_t res,
const nmod_poly_t poly)
Factorises a non-constant polynomial \code{f} into monic irreducible
factors using the fast version of Cantor-Zassenhaus algorithm proposed by
Kaltofen and Shoup (1998). More precisely this algorithm uses a
“baby step/giant step” strategy for the distinct-degree factorization
step.
mp_limb_t nmod_poly_factor_with_berlekamp(nmod_poly_factor_t res,
const nmod_poly_t f)
Factorises a general polynomial \code{f} into monic irreducible factors
and returns the leading coefficient of \code{f}, or 0 if \code{f}
is the zero polynomial.
This function first checks for small special cases, deflates \code{f}
if it is of the form $p(x^m)$ for some $m > 1$, then performs a
square-free factorisation, and finally runs Berlekamp on all the
individual square-free factors.
mp_limb_t nmod_poly_factor_with_cantor_zassenhaus(nmod_poly_factor_t res,
const nmod_poly_t f)
Factorises a general polynomial \code{f} into monic irreducible factors
and returns the leading coefficient of \code{f}, or 0 if \code{f}
is the zero polynomial.
This function first checks for small special cases, deflates \code{f}
if it is of the form $p(x^m)$ for some $m > 1$, then performs a
square-free factorisation, and finally runs Cantor-Zassenhaus on all the
individual square-free factors.
mp_limb_t nmod_poly_factor_with_kaltofen_shoup(nmod_poly_factor_t res,
const nmod_poly_t f)
Factorises a general polynomial \code{f} into monic irreducible factors
and returns the leading coefficient of \code{f}, or 0 if \code{f}
is the zero polynomial.
This function first checks for small special cases, deflates \code{f}
if it is of the form $p(x^m)$ for some $m > 1$, then performs a
square-free factorisation, and finally runs Kaltofen-Shoup on all the
individual square-free factors.
mp_limb_t nmod_poly_factor(nmod_poly_factor_t res, const nmod_poly_t f)
Factorises a general polynomial \code{f} into monic irreducible factors
and returns the leading coefficient of \code{f}, or 0 if \code{f}
is the zero polynomial.
This function first checks for small special cases, deflates \code{f}
if it is of the form $p(x^m)$ for some $m > 1$, then performs a
square-free factorisation, and finally runs either Cantor-Zassenhaus
or Berlekamp on all the individual square-free factors.
Currently Cantor-Zassenhaus is used by default unless the modulus is 2, in
which case Berlekamp is used.
|
