1 | |
---|
2 | /**************************************************************************\ |
---|
3 | |
---|
4 | MODULE: zz_pXFactoring |
---|
5 | |
---|
6 | SUMMARY: |
---|
7 | |
---|
8 | Routines are provided for factorization of polynomials over zz_p, as |
---|
9 | well as routines for related problems such as testing irreducibility |
---|
10 | and constructing irreducible polynomials of given degree. |
---|
11 | |
---|
12 | \**************************************************************************/ |
---|
13 | |
---|
14 | #include "zz_pX.h" |
---|
15 | #include "pair_zz_pX_long.h" |
---|
16 | |
---|
17 | |
---|
18 | void SquareFreeDecomp(vec_pair_zz_pX_long& u, const zz_pX& f); |
---|
19 | vec_pair_zz_pX_long SquareFreeDecomp(const zz_pX& f); |
---|
20 | |
---|
21 | // Performs square-free decomposition. f must be monic. If f = |
---|
22 | // prod_i g_i^i, then u is set to a lest of pairs (g_i, i). The list |
---|
23 | // is is increasing order of i, with trivial terms (i.e., g_i = 1) |
---|
24 | // deleted. |
---|
25 | |
---|
26 | |
---|
27 | void FindRoots(vec_zz_p& x, const zz_pX& f); |
---|
28 | vec_zz_p FindRoots(const zz_pX& f); |
---|
29 | |
---|
30 | // f is monic, and has deg(f) distinct roots. returns the list of |
---|
31 | // roots |
---|
32 | |
---|
33 | void FindRoot(zz_p& root, const zz_pX& f); |
---|
34 | zz_p FindRoot(const zz_pX& f); |
---|
35 | |
---|
36 | // finds a single root of f. assumes that f is monic and splits into |
---|
37 | // distinct linear factors |
---|
38 | |
---|
39 | |
---|
40 | void SFBerlekamp(vec_zz_pX& factors, const zz_pX& f, long verbose=0); |
---|
41 | vec_zz_pX SFBerlekamp(const zz_pX& f, long verbose=0); |
---|
42 | |
---|
43 | // Assumes f is square-free and monic. returns list of factors of f. |
---|
44 | // Uses "Berlekamp" approach, as described in detail in [Shoup, |
---|
45 | // J. Symbolic Comp. 20:363-397, 1995]. |
---|
46 | |
---|
47 | void berlekamp(vec_pair_zz_pX_long& factors, const zz_pX& f, |
---|
48 | long verbose=0); |
---|
49 | vec_pair_zz_pX_long berlekamp(const zz_pX& f, long verbose=0); |
---|
50 | |
---|
51 | // returns a list of factors, with multiplicities. f must be monic. |
---|
52 | // Calls SFBerlekamp. |
---|
53 | |
---|
54 | |
---|
55 | |
---|
56 | void NewDDF(vec_pair_zz_pX_long& factors, const zz_pX& f, const zz_pX& h, |
---|
57 | long verbose=0); |
---|
58 | |
---|
59 | vec_pair_zz_pX_long NewDDF(const zz_pX& f, const zz_pX& h, |
---|
60 | long verbose=0); |
---|
61 | |
---|
62 | // This computes a distinct-degree factorization. The input must be |
---|
63 | // monic and square-free. factors is set to a list of pairs (g, d), |
---|
64 | // where g is the product of all irreducible factors of f of degree d. |
---|
65 | // Only nontrivial pairs (i.e., g != 1) are included. The polynomial |
---|
66 | // h is assumed to be equal to X^p mod f. This routine implements the |
---|
67 | // baby step/giant step algorithm of [Kaltofen and Shoup, STOC 1995], |
---|
68 | // further described in [Shoup, J. Symbolic Comp. 20:363-397, 1995]. |
---|
69 | |
---|
70 | void EDF(vec_zz_pX& factors, const zz_pX& f, const zz_pX& h, |
---|
71 | long d, long verbose=0); |
---|
72 | |
---|
73 | vec_zz_pX EDF(const zz_pX& f, const zz_pX& h, |
---|
74 | long d, long verbose=0); |
---|
75 | |
---|
76 | // Performs equal-degree factorization. f is monic, square-free, and |
---|
77 | // all irreducible factors have same degree. h = X^p mod f. d = |
---|
78 | // degree of irreducible factors of f. This routine implements the |
---|
79 | // algorithm of [von zur Gathen and Shoup, Computational Complexity |
---|
80 | // 2:187-224, 1992] |
---|
81 | |
---|
82 | |
---|
83 | void RootEDF(vec_zz_pX& factors, const zz_pX& f, long verbose=0); |
---|
84 | vec_zz_pX RootEDF(const zz_pX& f, long verbose=0); |
---|
85 | |
---|
86 | // EDF for d==1 |
---|
87 | |
---|
88 | void SFCanZass(vec_zz_pX& factors, const zz_pX& f, long verbose=0); |
---|
89 | vec_zz_pX SFCanZass(const zz_pX& f, long verbose=0); |
---|
90 | |
---|
91 | // Assumes f is monic and square-free. returns list of factors of f. |
---|
92 | // Uses "Cantor/Zassenhaus" approach, using the routines NewDDF and |
---|
93 | // EDF above. |
---|
94 | |
---|
95 | |
---|
96 | void CanZass(vec_pair_zz_pX_long& factors, const zz_pX& f, |
---|
97 | long verbose=0); |
---|
98 | vec_pair_zz_pX_long CanZass(const zz_pX& f, long verbose=0); |
---|
99 | |
---|
100 | |
---|
101 | // returns a list of factors, with multiplicities. f must be monic. |
---|
102 | // Calls SquareFreeDecomp and SFCanZass. |
---|
103 | |
---|
104 | |
---|
105 | void mul(zz_pX& f, const vec_pair_zz_pX_long& v); |
---|
106 | zz_pX mul(const vec_pair_zz_pX_long& v); |
---|
107 | |
---|
108 | |
---|
109 | // multiplies polynomials, with multiplicities |
---|
110 | |
---|
111 | /**************************************************************************\ |
---|
112 | |
---|
113 | Irreducible Polynomials |
---|
114 | |
---|
115 | \**************************************************************************/ |
---|
116 | |
---|
117 | long ProbIrredTest(const zz_pX& f, long iter=1); |
---|
118 | |
---|
119 | // performs a fast, probabilistic irreduciblity test. The test can |
---|
120 | // err only if f is reducible, and the error probability is bounded by |
---|
121 | // p^{-iter}. This implements an algorithm from [Shoup, J. Symbolic |
---|
122 | // Comp. 17:371-391, 1994]. |
---|
123 | |
---|
124 | |
---|
125 | long DetIrredTest(const zz_pX& f); |
---|
126 | |
---|
127 | // performs a recursive deterministic irreducibility test. Fast in |
---|
128 | // the worst-case (when input is irreducible). This implements an |
---|
129 | // algorithm from [Shoup, J. Symbolic Comp. 17:371-391, 1994]. |
---|
130 | |
---|
131 | long IterIrredTest(const zz_pX& f); |
---|
132 | |
---|
133 | // performs an iterative deterministic irreducibility test, based on |
---|
134 | // DDF. Fast on average (when f has a small factor). |
---|
135 | |
---|
136 | void BuildIrred(zz_pX& f, long n); |
---|
137 | zz_pX BuildIrred_zz_pX(long n); |
---|
138 | |
---|
139 | // Build a monic irreducible poly of degree n. |
---|
140 | |
---|
141 | void BuildRandomIrred(zz_pX& f, const zz_pX& g); |
---|
142 | zz_pX BuildRandomIrred(const zz_pX& g); |
---|
143 | |
---|
144 | // g is a monic irreducible polynomial. Constructs a random monic |
---|
145 | // irreducible polynomial f of the same degree. |
---|
146 | |
---|
147 | long ComputeDegree(const zz_pX& h, const zz_pXModulus& F); |
---|
148 | |
---|
149 | // f is assumed to be an "equal degree" polynomial. h = X^p mod f. |
---|
150 | // The common degree of the irreducible factors of f is computed This |
---|
151 | // routine is useful in counting points on elliptic curves |
---|
152 | |
---|
153 | long ProbComputeDegree(const zz_pX& h, const zz_pXModulus& F); |
---|
154 | |
---|
155 | // same as above, but uses a slightly faster probabilistic algorithm. |
---|
156 | // The return value may be 0 or may be too big, but for large p |
---|
157 | // (relative to n), this happens with very low probability. |
---|
158 | |
---|
159 | void TraceMap(zz_pX& w, const zz_pX& a, long d, const zz_pXModulus& F, |
---|
160 | const zz_pX& h); |
---|
161 | |
---|
162 | zz_pX TraceMap(const zz_pX& a, long d, const zz_pXModulus& F, |
---|
163 | const zz_pX& h); |
---|
164 | |
---|
165 | // w = a+a^q+...+^{q^{d-1}} mod f; it is assumed that d >= 0, and h = |
---|
166 | // X^q mod f, q a power of p. This routine implements an algorithm |
---|
167 | // from [von zur Gathen and Shoup, Computational Complexity 2:187-224, |
---|
168 | // 1992] |
---|
169 | |
---|
170 | void PowerCompose(zz_pX& w, const zz_pX& h, long d, const zz_pXModulus& F); |
---|
171 | zz_pX PowerCompose(const zz_pX& h, long d, const zz_pXModulus& F); |
---|
172 | |
---|
173 | |
---|
174 | // w = X^{q^d} mod f; it is assumed that d >= 0, and h = X^q mod f, q |
---|
175 | // a power of p. This routine implements an algorithm from [von zur |
---|
176 | // Gathen and Shoup, Computational Complexity 2:187-224, 1992] |
---|
177 | |
---|