-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathZZ_pXFactoring.txt
198 lines (126 loc) · 6.67 KB
/
ZZ_pXFactoring.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
189
190
191
192
193
194
195
196
197
/**************************************************************************\
MODULE: ZZ_pXFactoring
SUMMARY:
Routines are provided for factorization of polynomials over ZZ_p, as
well as routines for related problems such as testing irreducibility
and constructing irreducible polynomials of given degree.
\**************************************************************************/
#include <NTL/ZZ_pX.h>
#include <NTL/pair_ZZ_pX_long.h>
void SquareFreeDecomp(vec_pair_ZZ_pX_long& u, const ZZ_pX& f);
vec_pair_ZZ_pX_long SquareFreeDecomp(const ZZ_pX& f);
// Performs square-free decomposition. f must be monic. If f =
// prod_i g_i^i, then u is set to a lest 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_p& x, const ZZ_pX& f);
vec_ZZ_p FindRoots(const ZZ_pX& f);
// f is monic, and has deg(f) distinct roots. returns the list of
// roots
void FindRoot(ZZ_p& root, const ZZ_pX& f);
ZZ_p FindRoot(const ZZ_pX& f);
// finds a single root of f. assumes that f is monic and splits into
// distinct linear factors
void SFBerlekamp(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0);
vec_ZZ_pX SFBerlekamp(const ZZ_pX& f, long verbose=0);
// Assumes f is square-free and monic. returns list of factors of f.
// Uses "Berlekamp" approach, as described in detail in [Shoup,
// J. Symbolic Comp. 20:363-397, 1995].
void berlekamp(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f,
long verbose=0);
vec_pair_ZZ_pX_long berlekamp(const ZZ_pX& f, long verbose=0);
// returns a list of factors, with multiplicities. f must be monic.
// Calls SFBerlekamp.
void NewDDF(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f, const ZZ_pX& h,
long verbose=0);
vec_pair_ZZ_pX_long NewDDF(const ZZ_pX& f, const ZZ_pX& 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^p 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_pXFileThresh
// which can be set by the user. If the sizes of the tables
// exceeds ZZ_pXFileThresh KB, external files are used.
// Initial value is NTL_FILE_THRESH (defined in tools.h).
void EDF(vec_ZZ_pX& factors, const ZZ_pX& f, const ZZ_pX& h,
long d, long verbose=0);
vec_ZZ_pX EDF(const ZZ_pX& f, const ZZ_pX& h,
long d, long verbose=0);
// Performs equal-degree factorization. f is monic, square-free, and
// all irreducible factors have same degree. h = X^p 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_pX& factors, const ZZ_pX& f, long verbose=0);
vec_ZZ_pX RootEDF(const ZZ_pX& f, long verbose=0);
// EDF for d==1
void SFCanZass(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0);
vec_ZZ_pX SFCanZass(const ZZ_pX& 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_pX_long& factors, const ZZ_pX& f,
long verbose=0);
vec_pair_ZZ_pX_long CanZass(const ZZ_pX& 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_pXArgBound (see ZZ_pX.txt).
void mul(ZZ_pX& f, const vec_pair_ZZ_pX_long& v);
ZZ_pX mul(const vec_pair_ZZ_pX_long& v);
// multiplies polynomials, with multiplicities
/**************************************************************************\
Irreducible Polynomials
\**************************************************************************/
long ProbIrredTest(const ZZ_pX& 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
// p^{-iter}. This implements an algorithm from [Shoup, J. Symbolic
// Comp. 17:371-391, 1994].
long DetIrredTest(const ZZ_pX& 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_pX& f);
// performs an iterative deterministic irreducibility test, based on
// DDF. Fast on average (when f has a small factor).
void BuildIrred(ZZ_pX& f, long n);
ZZ_pX BuildIrred_ZZ_pX(long n);
// Build a monic irreducible poly of degree n.
void BuildRandomIrred(ZZ_pX& f, const ZZ_pX& g);
ZZ_pX BuildRandomIrred(const ZZ_pX& g);
// g is a monic irreducible polynomial. Constructs a random monic
// irreducible polynomial f of the same degree.
long ComputeDegree(const ZZ_pX& h, const ZZ_pXModulus& F);
// f is assumed to be an "equal degree" polynomial; h = X^p mod f.
// The common degree of the irreducible factors of f is computed This
// routine is useful in counting points on elliptic curves
long ProbComputeDegree(const ZZ_pX& h, const ZZ_pXModulus& F);
// Same as above, but uses a slightly faster probabilistic algorithm.
// The return value may be 0 or may be too big, but for large p
// (relative to n), this happens with very low probability.
void TraceMap(ZZ_pX& w, const ZZ_pX& a, long d, const ZZ_pXModulus& F,
const ZZ_pX& h);
ZZ_pX TraceMap(const ZZ_pX& a, long d, const ZZ_pXModulus& F,
const ZZ_pX& h);
// 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 p. This routine implements an algorithm
// from [von zur Gathen and Shoup, Computational Complexity 2:187-224,
// 1992].
void PowerCompose(ZZ_pX& w, const ZZ_pX& h, long d, const ZZ_pXModulus& F);
ZZ_pX PowerCompose(const ZZ_pX& h, long d, const ZZ_pXModulus& F);
// w = X^{q^d} mod f; it is assumed that d >= 0, and h = X^q mod f, q
// a power of p. This routine implements an algorithm from [von zur
// Gathen and Shoup, Computational Complexity 2:187-224, 1992]