-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathZZ_pEXFactoring.txt
189 lines (120 loc) · 6.48 KB
/
ZZ_pEXFactoring.txt
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
/**************************************************************************\
MODULE: ZZ_pEXFactoring
SUMMARY:
Routines are provided for factorization of polynomials over ZZ_pE, as
well as routines for related problems such as testing irreducibility
and constructing irreducible polynomials of given degree.
\**************************************************************************/
#include <NTL/ZZ_pEX.h>
#include <NTL/pair_ZZ_pEX_long.h>
void SquareFreeDecomp(vec_pair_ZZ_pEX_long& u, const ZZ_pEX& f);
vec_pair_ZZ_pEX_long SquareFreeDecomp(const ZZ_pEX& f);
// Performs square-free decomposition. f must be monic. If f =
// prod_i g_i^i, then u is set to a list of pairs (g_i, i). The list
// is is increasing order of i, with trivial terms (i.e., g_i = 1)
// deleted.
void FindRoots(vec_ZZ_pE& x, const ZZ_pEX& f);
vec_ZZ_pE FindRoots(const ZZ_pEX& f);
// f is monic, and has deg(f) distinct roots. returns the list of
// roots
void FindRoot(ZZ_pE& root, const ZZ_pEX& f);
ZZ_pE FindRoot(const ZZ_pEX& f);
// finds a single root of f. assumes that f is monic and splits into
// distinct linear factors
void NewDDF(vec_pair_ZZ_pEX_long& factors, const ZZ_pEX& f,
const ZZ_pEX& h, long verbose=0);
vec_pair_ZZ_pEX_long NewDDF(const ZZ_pEX& f, const ZZ_pEX& h,
long verbose=0);
// This computes a distinct-degree factorization. The input must be
// monic and square-free. factors is set to a list of pairs (g, d),
// where g is the product of all irreducible factors of f of degree d.
// Only nontrivial pairs (i.e., g != 1) are included. The polynomial
// h is assumed to be equal to X^{ZZ_pE::cardinality()} mod f.
// This routine implements the baby step/giant step algorithm
// of [Kaltofen and Shoup, STOC 1995].
// further described in [Shoup, J. Symbolic Comp. 20:363-397, 1995].
// NOTE: When factoring "large" polynomials,
// this routine uses external files to store some intermediate
// results, which are removed if the routine terminates normally.
// These files are stored in the current directory under names of the
// form tmp-*.
// The definition of "large" is controlled by the variable
extern double ZZ_pEXFileThresh
// which can be set by the user. If the sizes of the tables
// exceeds ZZ_pEXFileThresh KB, external files are used.
// Initial value is NTL_FILE_THRESH (defined in tools.h).
void EDF(vec_ZZ_pEX& factors, const ZZ_pEX& f, const ZZ_pEX& h,
long d, long verbose=0);
vec_ZZ_pEX EDF(const ZZ_pEX& f, const ZZ_pEX& h,
long d, long verbose=0);
// Performs equal-degree factorization. f is monic, square-free, and
// all irreducible factors have same degree. h = X^{ZZ_pE::cardinality()} mod
// f. d = degree of irreducible factors of f. This routine
// implements the algorithm of [von zur Gathen and Shoup,
// Computational Complexity 2:187-224, 1992]
void RootEDF(vec_ZZ_pEX& factors, const ZZ_pEX& f, long verbose=0);
vec_ZZ_pEX RootEDF(const ZZ_pEX& f, long verbose=0);
// EDF for d==1
void SFCanZass(vec_ZZ_pEX& factors, const ZZ_pEX& f, long verbose=0);
vec_ZZ_pEX SFCanZass(const ZZ_pEX& f, long verbose=0);
// Assumes f is monic and square-free. returns list of factors of f.
// Uses "Cantor/Zassenhaus" approach, using the routines NewDDF and
// EDF above.
void CanZass(vec_pair_ZZ_pEX_long& factors, const ZZ_pEX& f,
long verbose=0);
vec_pair_ZZ_pEX_long CanZass(const ZZ_pEX& f, long verbose=0);
// returns a list of factors, with multiplicities. f must be monic.
// Calls SquareFreeDecomp and SFCanZass.
// NOTE: these routines use modular composition. The space
// used for the required tables can be controlled by the variable
// ZZ_pEXArgBound (see ZZ_pEX.txt).
void mul(ZZ_pEX& f, const vec_pair_ZZ_pEX_long& v);
ZZ_pEX mul(const vec_pair_ZZ_pEX_long& v);
// multiplies polynomials, with multiplicities
/**************************************************************************\
Irreducible Polynomials
\**************************************************************************/
long ProbIrredTest(const ZZ_pEX& f, long iter=1);
// performs a fast, probabilistic irreduciblity test. The test can
// err only if f is reducible, and the error probability is bounded by
// ZZ_pE::cardinality()^{-iter}. This implements an algorithm from [Shoup,
// J. Symbolic Comp. 17:371-391, 1994].
long DetIrredTest(const ZZ_pEX& f);
// performs a recursive deterministic irreducibility test. Fast in
// the worst-case (when input is irreducible). This implements an
// algorithm from [Shoup, J. Symbolic Comp. 17:371-391, 1994].
long IterIrredTest(const ZZ_pEX& f);
// performs an iterative deterministic irreducibility test, based on
// DDF. Fast on average (when f has a small factor).
void BuildIrred(ZZ_pEX& f, long n);
ZZ_pEX BuildIrred_ZZ_pEX(long n);
// Build a monic irreducible poly of degree n.
void BuildRandomIrred(ZZ_pEX& f, const ZZ_pEX& g);
ZZ_pEX BuildRandomIrred(const ZZ_pEX& g);
// g is a monic irreducible polynomial. Constructs a random monic
// irreducible polynomial f of the same degree.
long IterComputeDegree(const ZZ_pEX& h, const ZZ_pEXModulus& F);
// f is assumed to be an "equal degree" polynomial, and h =
// X^{ZZ_pE::cardinality()} mod f. The common degree of the irreducible
// factors of f is computed. Uses a "baby step/giant step" algorithm, similar
// to NewDDF. Although asymptotocally slower than RecComputeDegree
// (below), it is faster for reasonably sized inputs.
long RecComputeDegree(const ZZ_pEX& h, const ZZ_pEXModulus& F);
// f is assumed to be an "equal degree" polynomial,
// h = X^{ZZ_pE::cardinality()} mod f.
// The common degree of the irreducible factors of f is
// computed Uses a recursive algorithm similar to DetIrredTest.
void TraceMap(ZZ_pEX& w, const ZZ_pEX& a, long d, const ZZ_pEXModulus& F,
const ZZ_pEX& h);
ZZ_pEX TraceMap(const ZZ_pEX& a, long d, const ZZ_pEXModulus& F,
const ZZ_pEX& h);
// Computes w = a+a^q+...+^{q^{d-1}} mod f; it is assumed that d >= 0,
// and h = X^q mod f, q a power of ZZ_pE::cardinality(). This routine
// implements an algorithm from [von zur Gathen and Shoup,
// Computational Complexity 2:187-224, 1992]
void PowerCompose(ZZ_pEX& w, const ZZ_pEX& h, long d, const ZZ_pEXModulus& F);
ZZ_pEX PowerCompose(const ZZ_pEX& h, long d, const ZZ_pEXModulus& F);
// Computes w = X^{q^d} mod f; it is assumed that d >= 0, and h = X^q
// mod f, q a power of ZZ_pE::cardinality(). This routine implements an
// algorithm from [von zur Gathen and Shoup, Computational Complexity
// 2:187-224, 1992]