1 | /**************************************** |
---|
2 | * Computer Algebra System SINGULAR * |
---|
3 | ****************************************/ |
---|
4 | /** |
---|
5 | * ABSTRACT: numbers in an algebraic extension field K[a] / < f(a) > |
---|
6 | * Assuming that we have a coeffs object cf, then these numbers |
---|
7 | * are polynomials in the polynomial ring K[a] represented by |
---|
8 | * cf->extRing. |
---|
9 | * IMPORTANT ASSUMPTIONS: |
---|
10 | * 1.) So far we assume that cf->extRing is a valid polynomial |
---|
11 | * ring in exactly one variable, i.e., K[a], where K is allowed |
---|
12 | * to be any field (representable in SINGULAR and which may |
---|
13 | * itself be some extension field, thus allowing for extension |
---|
14 | * towers). |
---|
15 | * 2.) Moreover, this implementation assumes that |
---|
16 | * cf->extRing->minideal is not NULL but an ideal with at |
---|
17 | * least one non-zero generator which may be accessed by |
---|
18 | * cf->extRing->minideal->m[0] and which represents the minimal |
---|
19 | * polynomial f(a) of the extension variable 'a' in K[a]. |
---|
20 | * 3.) As soon as an std method for polynomial rings becomes |
---|
21 | * availabe, all reduction steps modulo f(a) should be replaced |
---|
22 | * by a call to std. Moreover, in this situation one can finally |
---|
23 | * move from K[a] / < f(a) > to |
---|
24 | * K[a_1, ..., a_s] / I, with I some zero-dimensional ideal |
---|
25 | * in K[a_1, ..., a_s] given by a lex |
---|
26 | * Gröbner basis. |
---|
27 | * The code in algext.h and algext.cc is then capable of |
---|
28 | * computing in K[a_1, ..., a_s] / I. |
---|
29 | **/ |
---|
30 | |
---|
31 | #include "config.h" |
---|
32 | #include <misc/auxiliary.h> |
---|
33 | |
---|
34 | #include <omalloc/omalloc.h> |
---|
35 | |
---|
36 | #include <reporter/reporter.h> |
---|
37 | |
---|
38 | #include <coeffs/coeffs.h> |
---|
39 | #include <coeffs/numbers.h> |
---|
40 | #include <coeffs/longrat.h> |
---|
41 | |
---|
42 | #include <polys/monomials/ring.h> |
---|
43 | #include <polys/monomials/p_polys.h> |
---|
44 | #include <polys/simpleideals.h> |
---|
45 | |
---|
46 | #include "ext_fields/algext.h" |
---|
47 | |
---|
48 | #ifdef LDEBUG |
---|
49 | #define naTest(a) naDBTest(a,__FILE__,__LINE__,cf) |
---|
50 | BOOLEAN naDBTest(number a, const char *f, const int l, const coeffs r); |
---|
51 | #else |
---|
52 | #define naTest(a) |
---|
53 | #endif |
---|
54 | |
---|
55 | /// Our own type! |
---|
56 | static const n_coeffType ID = n_algExt; |
---|
57 | |
---|
58 | /* polynomial ring in which our numbers live */ |
---|
59 | #define naRing cf->extRing |
---|
60 | |
---|
61 | /* coeffs object in which the coefficients of our numbers live; |
---|
62 | * methods attached to naCoeffs may be used to compute with the |
---|
63 | * coefficients of our numbers, e.g., use naCoeffs->nAdd to add |
---|
64 | * coefficients of our numbers */ |
---|
65 | #define naCoeffs cf->extRing->cf |
---|
66 | |
---|
67 | /* minimal polynomial */ |
---|
68 | #define naMinpoly naRing->minideal->m[0] |
---|
69 | |
---|
70 | |
---|
71 | /// forward declarations |
---|
72 | BOOLEAN naGreaterZero(number a, const coeffs cf); |
---|
73 | BOOLEAN naGreater(number a, number b, const coeffs cf); |
---|
74 | BOOLEAN naEqual(number a, number b, const coeffs cf); |
---|
75 | BOOLEAN naIsOne(number a, const coeffs cf); |
---|
76 | BOOLEAN naIsMOne(number a, const coeffs cf); |
---|
77 | BOOLEAN naIsZero(number a, const coeffs cf); |
---|
78 | number naInit(int i, const coeffs cf); |
---|
79 | int naInt(number &a, const coeffs cf); |
---|
80 | number naNeg(number a, const coeffs cf); |
---|
81 | number naInvers(number a, const coeffs cf); |
---|
82 | number naAdd(number a, number b, const coeffs cf); |
---|
83 | number naSub(number a, number b, const coeffs cf); |
---|
84 | number naMult(number a, number b, const coeffs cf); |
---|
85 | number naDiv(number a, number b, const coeffs cf); |
---|
86 | void naPower(number a, int exp, number *b, const coeffs cf); |
---|
87 | number naCopy(number a, const coeffs cf); |
---|
88 | void naWrite(number &a, const coeffs cf); |
---|
89 | number naRePart(number a, const coeffs cf); |
---|
90 | number naImPart(number a, const coeffs cf); |
---|
91 | number naGetDenom(number &a, const coeffs cf); |
---|
92 | number naGetNumerator(number &a, const coeffs cf); |
---|
93 | number naGcd(number a, number b, const coeffs cf); |
---|
94 | number naLcm(number a, number b, const coeffs cf); |
---|
95 | int naSize(number a, const coeffs cf); |
---|
96 | void naDelete(number *a, const coeffs cf); |
---|
97 | void naCoeffWrite(const coeffs cf); |
---|
98 | number naIntDiv(number a, number b, const coeffs cf); |
---|
99 | const char * naRead(const char *s, number *a, const coeffs cf); |
---|
100 | static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void * param); |
---|
101 | |
---|
102 | #ifdef LDEBUG |
---|
103 | BOOLEAN naDBTest(number a, const char *f, const int l, const coeffs cf) |
---|
104 | { |
---|
105 | assume(getCoeffType(cf) == ID); |
---|
106 | if (a == NULL) return TRUE; |
---|
107 | p_Test((poly)a, naRing); |
---|
108 | assume(p_Totaldegree((poly)a, naRing) <= p_Totaldegree(naMinpoly, naRing)); |
---|
109 | return TRUE; |
---|
110 | } |
---|
111 | #endif |
---|
112 | |
---|
113 | void heuristicReduce(poly &p, poly reducer, const coeffs cf); |
---|
114 | void definiteReduce(poly &p, poly reducer, const coeffs cf); |
---|
115 | |
---|
116 | /* returns the bottom field in this field extension tower; if the tower |
---|
117 | is flat, i.e., if there is no extension, then r itself is returned; |
---|
118 | as a side-effect, the counter 'height' is filled with the height of |
---|
119 | the extension tower (in case the tower is flat, 'height' is zero) */ |
---|
120 | static coeffs nCoeff_bottom(const coeffs r, int &height) |
---|
121 | { |
---|
122 | assume(r != NULL); |
---|
123 | coeffs cf = r; |
---|
124 | height = 0; |
---|
125 | while (nCoeff_is_Extension(cf)) |
---|
126 | { |
---|
127 | assume(cf->extRing != NULL); assume(cf->extRing->cf != NULL); |
---|
128 | cf = cf->extRing->cf; |
---|
129 | height++; |
---|
130 | } |
---|
131 | return cf; |
---|
132 | } |
---|
133 | |
---|
134 | BOOLEAN naIsZero(number a, const coeffs cf) |
---|
135 | { |
---|
136 | naTest(a); |
---|
137 | return (a == NULL); |
---|
138 | } |
---|
139 | |
---|
140 | void naDelete(number * a, const coeffs cf) |
---|
141 | { |
---|
142 | if (*a == NULL) return; |
---|
143 | poly aAsPoly = (poly)(*a); |
---|
144 | p_Delete(&aAsPoly, naRing); |
---|
145 | *a = NULL; |
---|
146 | } |
---|
147 | |
---|
148 | BOOLEAN naEqual(number a, number b, const coeffs cf) |
---|
149 | { |
---|
150 | naTest(a); naTest(b); |
---|
151 | |
---|
152 | /// simple tests |
---|
153 | if (a == b) return TRUE; |
---|
154 | if ((a == NULL) && (b != NULL)) return FALSE; |
---|
155 | if ((b == NULL) && (a != NULL)) return FALSE; |
---|
156 | |
---|
157 | /// deg test |
---|
158 | int aDeg = 0; |
---|
159 | if (a != NULL) aDeg = p_Totaldegree((poly)a, naRing); |
---|
160 | int bDeg = 0; |
---|
161 | if (b != NULL) bDeg = p_Totaldegree((poly)b, naRing); |
---|
162 | if (aDeg != bDeg) return FALSE; |
---|
163 | |
---|
164 | /// subtraction test |
---|
165 | number c = naSub(a, b, cf); |
---|
166 | BOOLEAN result = naIsZero(c, cf); |
---|
167 | naDelete(&c, naCoeffs); |
---|
168 | return result; |
---|
169 | } |
---|
170 | |
---|
171 | number naCopy(number a, const coeffs cf) |
---|
172 | { |
---|
173 | naTest(a); |
---|
174 | if (a == NULL) return NULL; |
---|
175 | return (number)p_Copy((poly)a, naRing); |
---|
176 | } |
---|
177 | |
---|
178 | number naGetNumerator(number &a, const coeffs cf) |
---|
179 | { |
---|
180 | return naCopy(a, cf); |
---|
181 | } |
---|
182 | |
---|
183 | number naGetDenom(number &a, const coeffs cf) |
---|
184 | { |
---|
185 | naTest(a); |
---|
186 | return naInit(1, cf); |
---|
187 | } |
---|
188 | |
---|
189 | BOOLEAN naIsOne(number a, const coeffs cf) |
---|
190 | { |
---|
191 | naTest(a); |
---|
192 | poly aAsPoly = (poly)a; |
---|
193 | if (!p_IsConstant(aAsPoly, naRing)) return FALSE; |
---|
194 | return n_IsOne(p_GetCoeff(aAsPoly, naRing), naCoeffs); |
---|
195 | } |
---|
196 | |
---|
197 | BOOLEAN naIsMOne(number a, const coeffs cf) |
---|
198 | { |
---|
199 | naTest(a); |
---|
200 | poly aAsPoly = (poly)a; |
---|
201 | if (!p_IsConstant(aAsPoly, naRing)) return FALSE; |
---|
202 | return n_IsMOne(p_GetCoeff(aAsPoly, naRing), naCoeffs); |
---|
203 | } |
---|
204 | |
---|
205 | /// this is in-place, modifies a |
---|
206 | number naNeg(number a, const coeffs cf) |
---|
207 | { |
---|
208 | naTest(a); |
---|
209 | if (a != NULL) a = (number)p_Neg((poly)a, naRing); |
---|
210 | return a; |
---|
211 | } |
---|
212 | |
---|
213 | number naImPart(number a, const coeffs cf) |
---|
214 | { |
---|
215 | naTest(a); |
---|
216 | return NULL; |
---|
217 | } |
---|
218 | |
---|
219 | number naInit(int i, const coeffs cf) |
---|
220 | { |
---|
221 | if (i == 0) return NULL; |
---|
222 | else return (number)p_ISet(i, naRing); |
---|
223 | } |
---|
224 | |
---|
225 | int naInt(number &a, const coeffs cf) |
---|
226 | { |
---|
227 | naTest(a); |
---|
228 | poly aAsPoly = (poly)a; |
---|
229 | if (!p_IsConstant(aAsPoly, naRing)) return 0; |
---|
230 | return n_Int(p_GetCoeff(aAsPoly, naRing), naCoeffs); |
---|
231 | } |
---|
232 | |
---|
233 | /* TRUE iff (a != 0 and (b == 0 or deg(a) > deg(b))) */ |
---|
234 | BOOLEAN naGreater(number a, number b, const coeffs cf) |
---|
235 | { |
---|
236 | naTest(a); naTest(b); |
---|
237 | if (naIsZero(a, cf)) return FALSE; |
---|
238 | if (naIsZero(b, cf)) return TRUE; |
---|
239 | int aDeg = 0; |
---|
240 | if (a != NULL) aDeg = p_Totaldegree((poly)a, naRing); |
---|
241 | int bDeg = 0; |
---|
242 | if (b != NULL) bDeg = p_Totaldegree((poly)b, naRing); |
---|
243 | return (aDeg > bDeg); |
---|
244 | } |
---|
245 | |
---|
246 | /* TRUE iff a != 0 and (LC(a) > 0 or deg(a) > 0) */ |
---|
247 | BOOLEAN naGreaterZero(number a, const coeffs cf) |
---|
248 | { |
---|
249 | naTest(a); |
---|
250 | if (a == NULL) return FALSE; |
---|
251 | if (n_GreaterZero(p_GetCoeff((poly)a, naRing), naCoeffs)) return TRUE; |
---|
252 | if (p_Totaldegree((poly)a, naRing) > 0) return TRUE; |
---|
253 | return FALSE; |
---|
254 | } |
---|
255 | |
---|
256 | void naCoeffWrite(const coeffs cf) |
---|
257 | { |
---|
258 | char *x = rRingVar(0, naRing); |
---|
259 | Print("// Coefficients live in the extension field K[%s]/<f(%s)>\n", x, x); |
---|
260 | Print("// with the minimal polynomial f(%s) = %s\n", x, |
---|
261 | p_String(naMinpoly, naRing)); |
---|
262 | PrintS("// and K: "); n_CoeffWrite(cf->extRing->cf); |
---|
263 | } |
---|
264 | |
---|
265 | number naAdd(number a, number b, const coeffs cf) |
---|
266 | { |
---|
267 | naTest(a); naTest(b); |
---|
268 | if (a == NULL) return naCopy(b, cf); |
---|
269 | if (b == NULL) return naCopy(a, cf); |
---|
270 | poly aPlusB = p_Add_q(p_Copy((poly)a, naRing), |
---|
271 | p_Copy((poly)b, naRing), naRing); |
---|
272 | definiteReduce(aPlusB, naMinpoly, cf); |
---|
273 | return (number)aPlusB; |
---|
274 | } |
---|
275 | |
---|
276 | number naSub(number a, number b, const coeffs cf) |
---|
277 | { |
---|
278 | naTest(a); naTest(b); |
---|
279 | if (b == NULL) return naCopy(a, cf); |
---|
280 | poly minusB = p_Neg(p_Copy((poly)b, naRing), naRing); |
---|
281 | if (a == NULL) return (number)minusB; |
---|
282 | poly aMinusB = p_Add_q(p_Copy((poly)a, naRing), minusB, naRing); |
---|
283 | definiteReduce(aMinusB, naMinpoly, cf); |
---|
284 | return (number)aMinusB; |
---|
285 | } |
---|
286 | |
---|
287 | number naMult(number a, number b, const coeffs cf) |
---|
288 | { |
---|
289 | naTest(a); naTest(b); |
---|
290 | if (a == NULL) return NULL; |
---|
291 | if (b == NULL) return NULL; |
---|
292 | poly aTimesB = p_Mult_q(p_Copy((poly)a, naRing), |
---|
293 | p_Copy((poly)b, naRing), naRing); |
---|
294 | definiteReduce(aTimesB, naMinpoly, cf); |
---|
295 | return (number)aTimesB; |
---|
296 | } |
---|
297 | |
---|
298 | number naDiv(number a, number b, const coeffs cf) |
---|
299 | { |
---|
300 | naTest(a); naTest(b); |
---|
301 | if (b == NULL) WerrorS(nDivBy0); |
---|
302 | if (a == NULL) return NULL; |
---|
303 | poly bInverse = (poly)naInvers(b, cf); |
---|
304 | poly aDivB = p_Mult_q(p_Copy((poly)a, naRing), bInverse, naRing); |
---|
305 | definiteReduce(aDivB, naMinpoly, cf); |
---|
306 | return (number)aDivB; |
---|
307 | } |
---|
308 | |
---|
309 | /* 0^0 = 0; |
---|
310 | for |exp| <= 7 compute power by a simple multiplication loop; |
---|
311 | for |exp| >= 8 compute power along binary presentation of |exp|, e.g. |
---|
312 | p^13 = p^1 * p^4 * p^8, where we utilise that |
---|
313 | p^(2^(k+1)) = p^(2^k) * p^(2^k); |
---|
314 | intermediate reduction modulo the minimal polynomial is controlled by |
---|
315 | the in-place method heuristicReduce(poly, poly, coeffs); see there. |
---|
316 | */ |
---|
317 | void naPower(number a, int exp, number *b, const coeffs cf) |
---|
318 | { |
---|
319 | naTest(a); |
---|
320 | |
---|
321 | /* special cases first */ |
---|
322 | if (a == NULL) |
---|
323 | { |
---|
324 | if (exp >= 0) *b = NULL; |
---|
325 | else WerrorS(nDivBy0); |
---|
326 | } |
---|
327 | else if (exp == 0) *b = naInit(1, cf); |
---|
328 | else if (exp == 1) *b = naCopy(a, cf); |
---|
329 | else if (exp == -1) *b = naInvers(a, cf); |
---|
330 | |
---|
331 | int expAbs = exp; if (expAbs < 0) expAbs = -expAbs; |
---|
332 | |
---|
333 | /* now compute a^expAbs */ |
---|
334 | poly pow; poly aAsPoly = (poly)a; |
---|
335 | if (expAbs <= 7) |
---|
336 | { |
---|
337 | pow = p_Copy(aAsPoly, naRing); |
---|
338 | for (int i = 2; i <= expAbs; i++) |
---|
339 | { |
---|
340 | pow = p_Mult_q(pow, p_Copy(aAsPoly, naRing), naRing); |
---|
341 | heuristicReduce(pow, naMinpoly, cf); |
---|
342 | } |
---|
343 | definiteReduce(pow, naMinpoly, cf); |
---|
344 | } |
---|
345 | else |
---|
346 | { |
---|
347 | pow = p_ISet(1, naRing); |
---|
348 | poly factor = p_Copy(aAsPoly, naRing); |
---|
349 | while (expAbs != 0) |
---|
350 | { |
---|
351 | if (expAbs & 1) |
---|
352 | { |
---|
353 | pow = p_Mult_q(pow, p_Copy(factor, naRing), naRing); |
---|
354 | heuristicReduce(pow, naMinpoly, cf); |
---|
355 | } |
---|
356 | expAbs = expAbs / 2; |
---|
357 | if (expAbs != 0) |
---|
358 | { |
---|
359 | factor = p_Mult_q(factor, factor, naRing); |
---|
360 | heuristicReduce(factor, naMinpoly, cf); |
---|
361 | } |
---|
362 | } |
---|
363 | p_Delete(&factor, naRing); |
---|
364 | definiteReduce(pow, naMinpoly, cf); |
---|
365 | } |
---|
366 | |
---|
367 | /* invert if original exponent was negative */ |
---|
368 | number n = (number)pow; |
---|
369 | if (exp < 0) |
---|
370 | { |
---|
371 | number m = naInvers(n, cf); |
---|
372 | naDelete(&n, cf); |
---|
373 | n = m; |
---|
374 | } |
---|
375 | *b = n; |
---|
376 | } |
---|
377 | |
---|
378 | /* may reduce p modulo the reducer by calling definiteReduce; |
---|
379 | the decision is made based on the following heuristic |
---|
380 | (which should also only be changed here in this method): |
---|
381 | if (deg(p) > 10*deg(reducer) then perform reduction; |
---|
382 | modifies p */ |
---|
383 | void heuristicReduce(poly &p, poly reducer, const coeffs cf) |
---|
384 | { |
---|
385 | #ifdef LDEBUG |
---|
386 | p_Test((poly)p, naRing); |
---|
387 | p_Test((poly)reducer, naRing); |
---|
388 | #endif |
---|
389 | if (p_Totaldegree(p, naRing) > 10 * p_Totaldegree(reducer, naRing)) |
---|
390 | definiteReduce(p, reducer, cf); |
---|
391 | } |
---|
392 | |
---|
393 | void naWrite(number &a, const coeffs cf) |
---|
394 | { |
---|
395 | naTest(a); |
---|
396 | if (a == NULL) |
---|
397 | StringAppendS("0"); |
---|
398 | else |
---|
399 | { |
---|
400 | poly aAsPoly = (poly)a; |
---|
401 | /* basically, just write aAsPoly using p_Write, |
---|
402 | but use brackets around the output, if a is not |
---|
403 | a constant living in naCoeffs = cf->extRing->cf */ |
---|
404 | BOOLEAN useBrackets = !(p_IsConstant(aAsPoly, naRing)); |
---|
405 | if (useBrackets) StringAppendS("("); |
---|
406 | p_String0(aAsPoly, naRing, naRing); |
---|
407 | if (useBrackets) StringAppendS(")"); |
---|
408 | } |
---|
409 | } |
---|
410 | |
---|
411 | const char * naRead(const char *s, number *a, const coeffs cf) |
---|
412 | { |
---|
413 | poly aAsPoly; |
---|
414 | const char * result = p_Read(s, aAsPoly, naRing); |
---|
415 | *a = (number)aAsPoly; |
---|
416 | return result; |
---|
417 | } |
---|
418 | |
---|
419 | /* implemented by the rule lcm(a, b) = a * b / gcd(a, b) */ |
---|
420 | number naLcm(number a, number b, const coeffs cf) |
---|
421 | { |
---|
422 | naTest(a); naTest(b); |
---|
423 | if (a == NULL) return NULL; |
---|
424 | if (b == NULL) return NULL; |
---|
425 | number theProduct = (number)p_Mult_q(p_Copy((poly)a, naRing), |
---|
426 | p_Copy((poly)b, naRing), naRing); |
---|
427 | /* note that theProduct needs not be reduced w.r.t. naMinpoly; |
---|
428 | but the final division will take care of the necessary reduction */ |
---|
429 | number theGcd = naGcd(a, b, cf); |
---|
430 | return naDiv(theProduct, theGcd, cf); |
---|
431 | } |
---|
432 | |
---|
433 | /* expects *param to be castable to AlgExtInfo */ |
---|
434 | static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void * param) |
---|
435 | { |
---|
436 | if (ID != n) return FALSE; |
---|
437 | AlgExtInfo *e = (AlgExtInfo *)param; |
---|
438 | /* for extension coefficient fields we expect the underlying |
---|
439 | polynomial rings to be IDENTICAL, i.e. the SAME OBJECT; |
---|
440 | this expectation is based on the assumption that we have properly |
---|
441 | registered cf and perform reference counting rather than creating |
---|
442 | multiple copies of the same coefficient field/domain/ring */ |
---|
443 | return (naRing == e->r); |
---|
444 | /* (Note that then also the minimal ideals will necessarily be |
---|
445 | the same, as they are attached to the ring.) */ |
---|
446 | } |
---|
447 | |
---|
448 | int naSize(number a, const coeffs cf) |
---|
449 | { |
---|
450 | if (a == NULL) return -1; |
---|
451 | /* this has been taken from the old implementation of field extensions, |
---|
452 | where we computed the sum of the degree and the number of terms in |
---|
453 | (poly)a; so we leave it at that, for the time being; |
---|
454 | maybe, the number of terms alone is a better measure? */ |
---|
455 | poly aAsPoly = (poly)a; |
---|
456 | int theDegree = 0; int noOfTerms = 0; |
---|
457 | while (aAsPoly != NULL) |
---|
458 | { |
---|
459 | noOfTerms++; |
---|
460 | int d = p_GetExp(aAsPoly, 1, naRing); |
---|
461 | if (d > theDegree) theDegree = d; |
---|
462 | pIter(aAsPoly); |
---|
463 | } |
---|
464 | return theDegree + noOfTerms; |
---|
465 | } |
---|
466 | |
---|
467 | /* performs polynomial division and overrides p by the remainder |
---|
468 | of division of p by the reducer; |
---|
469 | modifies p */ |
---|
470 | void definiteReduce(poly &p, poly reducer, const coeffs cf) |
---|
471 | { |
---|
472 | #ifdef LDEBUG |
---|
473 | p_Test((poly)p, naRing); |
---|
474 | p_Test((poly)reducer, naRing); |
---|
475 | #endif |
---|
476 | p_PolyDiv(p, reducer, FALSE, naRing); |
---|
477 | } |
---|
478 | |
---|
479 | /* IMPORTANT NOTE: Since an algebraic field extension is again a field, |
---|
480 | the gcd of two elements is not very interesting. (It |
---|
481 | is actually any unit in the field, i.e., any non- |
---|
482 | zero element.) Note that the below method does not operate |
---|
483 | in this strong sense but rather computes the gcd of |
---|
484 | two given elements in the underlying polynomial ring. */ |
---|
485 | number naGcd(number a, number b, const coeffs cf) |
---|
486 | { |
---|
487 | naTest(a); naTest(b); |
---|
488 | if ((a == NULL) && (b == NULL)) WerrorS(nDivBy0); |
---|
489 | return (number)p_Gcd((poly)a, (poly)b, naRing); |
---|
490 | } |
---|
491 | |
---|
492 | number naInvers(number a, const coeffs cf) |
---|
493 | { |
---|
494 | naTest(a); |
---|
495 | if (a == NULL) WerrorS(nDivBy0); |
---|
496 | poly aFactor = NULL; poly mFactor = NULL; |
---|
497 | poly theGcd = p_ExtGcd((poly)a, aFactor, naMinpoly, mFactor, naRing); |
---|
498 | naTest((number)theGcd); naTest((number)aFactor); naTest((number)mFactor); |
---|
499 | /* the gcd must be 1 since naMinpoly is irreducible and a != NULL: */ |
---|
500 | assume(naIsOne((number)theGcd, cf)); |
---|
501 | p_Delete(&theGcd, naRing); |
---|
502 | p_Delete(&mFactor, naRing); |
---|
503 | return (number)(aFactor); |
---|
504 | } |
---|
505 | |
---|
506 | /* assumes that src = Q, dst = Q(a) */ |
---|
507 | number naMap00(number a, const coeffs src, const coeffs dst) |
---|
508 | { |
---|
509 | if (n_IsZero(a, src)) return NULL; |
---|
510 | assume(src == dst->extRing->cf); |
---|
511 | poly result = p_One(dst->extRing); |
---|
512 | p_SetCoeff(result, naCopy(a, src), dst->extRing); |
---|
513 | return (number)result; |
---|
514 | } |
---|
515 | |
---|
516 | /* assumes that src = Z/p, dst = Q(a) */ |
---|
517 | number naMapP0(number a, const coeffs src, const coeffs dst) |
---|
518 | { |
---|
519 | if (n_IsZero(a, src)) return NULL; |
---|
520 | /* mapping via intermediate int: */ |
---|
521 | int n = n_Int(a, src); |
---|
522 | number q = n_Init(n, dst->extRing->cf); |
---|
523 | poly result = p_One(dst->extRing); |
---|
524 | p_SetCoeff(result, q, dst->extRing); |
---|
525 | return (number)result; |
---|
526 | } |
---|
527 | |
---|
528 | /* assumes that either src = Q(a), dst = Q(a), or |
---|
529 | src = Z/p(a), dst = Z/p(a) */ |
---|
530 | number naCopyMap(number a, const coeffs src, const coeffs dst) |
---|
531 | { |
---|
532 | return naCopy(a, dst); |
---|
533 | } |
---|
534 | |
---|
535 | /* assumes that src = Q, dst = Z/p(a) */ |
---|
536 | number naMap0P(number a, const coeffs src, const coeffs dst) |
---|
537 | { |
---|
538 | if (n_IsZero(a, src)) return NULL; |
---|
539 | int p = rChar(dst->extRing); |
---|
540 | int n = nlModP(a, p, src); |
---|
541 | number q = n_Init(n, dst->extRing->cf); |
---|
542 | poly result = p_One(dst->extRing); |
---|
543 | p_SetCoeff(result, q, dst->extRing); |
---|
544 | return (number)result; |
---|
545 | } |
---|
546 | |
---|
547 | /* assumes that src = Z/p, dst = Z/p(a) */ |
---|
548 | number naMapPP(number a, const coeffs src, const coeffs dst) |
---|
549 | { |
---|
550 | if (n_IsZero(a, src)) return NULL; |
---|
551 | assume(src == dst->extRing->cf); |
---|
552 | poly result = p_One(dst->extRing); |
---|
553 | p_SetCoeff(result, naCopy(a, src), dst->extRing); |
---|
554 | return (number)result; |
---|
555 | } |
---|
556 | |
---|
557 | /* assumes that src = Z/u, dst = Z/p(a), where u != p */ |
---|
558 | number naMapUP(number a, const coeffs src, const coeffs dst) |
---|
559 | { |
---|
560 | if (n_IsZero(a, src)) return NULL; |
---|
561 | /* mapping via intermediate int: */ |
---|
562 | int n = n_Int(a, src); |
---|
563 | number q = n_Init(n, dst->extRing->cf); |
---|
564 | poly result = p_One(dst->extRing); |
---|
565 | p_SetCoeff(result, q, dst->extRing); |
---|
566 | return (number)result; |
---|
567 | } |
---|
568 | |
---|
569 | nMapFunc naSetMap(const coeffs src, const coeffs dst) |
---|
570 | { |
---|
571 | /* dst is expected to be an algebraic field extension */ |
---|
572 | assume(getCoeffType(dst) == ID); |
---|
573 | |
---|
574 | int h = 0; /* the height of the extension tower given by dst */ |
---|
575 | coeffs bDst = nCoeff_bottom(dst, h); /* the bottom field in the tower dst */ |
---|
576 | |
---|
577 | /* for the time being, we only provide maps if h = 1 and if b is Q or |
---|
578 | some field Z/pZ: */ |
---|
579 | if (h != 1) return NULL; |
---|
580 | if ((!nCoeff_is_Zp(bDst)) && (!nCoeff_is_Q(bDst))) return NULL; |
---|
581 | |
---|
582 | if (nCoeff_is_Q(src) && nCoeff_is_Q(bDst)) |
---|
583 | return naMap00; /// Q --> Q(a) |
---|
584 | |
---|
585 | if (nCoeff_is_Zp(src) && nCoeff_is_Q(bDst)) |
---|
586 | return naMapP0; /// Z/p --> Q(a) |
---|
587 | |
---|
588 | if (nCoeff_is_Q(src) && nCoeff_is_Zp(bDst)) |
---|
589 | return naMap0P; /// Q --> Z/p(a) |
---|
590 | |
---|
591 | if (nCoeff_is_Zp(src) && nCoeff_is_Zp(bDst)) |
---|
592 | { |
---|
593 | if (src->ch == dst->ch) return naMapPP; /// Z/p --> Z/p(a) |
---|
594 | else return naMapUP; /// Z/u --> Z/p(a) |
---|
595 | } |
---|
596 | |
---|
597 | coeffs bSrc = nCoeff_bottom(src, h); /* the bottom field in the tower src */ |
---|
598 | if (h != 1) return NULL; |
---|
599 | if ((!nCoeff_is_Zp(bSrc)) && (!nCoeff_is_Q(bSrc))) return NULL; |
---|
600 | |
---|
601 | if (nCoeff_is_Q(bSrc) && nCoeff_is_Q(bDst)) |
---|
602 | { |
---|
603 | if (strcmp(rRingVar(0, src->extRing), |
---|
604 | rRingVar(0, dst->extRing)) == 0) |
---|
605 | return naCopyMap; /// Q(a) --> Q(a) |
---|
606 | else |
---|
607 | return NULL; /// Q(b) --> Q(a) |
---|
608 | } |
---|
609 | |
---|
610 | if (nCoeff_is_Zp(bSrc) && nCoeff_is_Zp(bDst)) |
---|
611 | { |
---|
612 | if (strcmp(rParameter(src->extRing)[0], |
---|
613 | rParameter(dst->extRing)[0]) == 0) |
---|
614 | return naCopyMap; /// Z/p(a) --> Z/p(a) |
---|
615 | else |
---|
616 | return NULL; /// Z/p(b) --> Z/p(a) |
---|
617 | } |
---|
618 | |
---|
619 | return NULL; /// default |
---|
620 | } |
---|
621 | |
---|
622 | BOOLEAN naInitChar(coeffs cf, void * infoStruct) |
---|
623 | { |
---|
624 | AlgExtInfo *e = (AlgExtInfo *)infoStruct; |
---|
625 | /// first check whether cf->extRing != NULL and delete old ring??? |
---|
626 | cf->extRing = e->r; |
---|
627 | cf->extRing->minideal = e->i; |
---|
628 | |
---|
629 | assume(cf->extRing != NULL); // extRing; |
---|
630 | assume((cf->extRing->minideal != NULL) && // minideal has one |
---|
631 | (IDELEMS(cf->extRing->minideal) != 0) && // non-zero generator |
---|
632 | (cf->extRing->minideal->m[0] != NULL) ); // at m[0]; |
---|
633 | assume(cf->extRing->cf != NULL); // extRing->cf; |
---|
634 | assume(getCoeffType(cf) == ID); // coeff type; |
---|
635 | |
---|
636 | /* propagate characteristic up so that it becomes |
---|
637 | directly accessible in cf: */ |
---|
638 | cf->ch = cf->extRing->cf->ch; |
---|
639 | |
---|
640 | #ifdef LDEBUG |
---|
641 | p_Test((poly)naMinpoly, naRing); |
---|
642 | #endif |
---|
643 | |
---|
644 | cf->cfGreaterZero = naGreaterZero; |
---|
645 | cf->cfGreater = naGreater; |
---|
646 | cf->cfEqual = naEqual; |
---|
647 | cf->cfIsZero = naIsZero; |
---|
648 | cf->cfIsOne = naIsOne; |
---|
649 | cf->cfIsMOne = naIsMOne; |
---|
650 | cf->cfInit = naInit; |
---|
651 | cf->cfInt = naInt; |
---|
652 | cf->cfNeg = naNeg; |
---|
653 | cf->cfAdd = naAdd; |
---|
654 | cf->cfSub = naSub; |
---|
655 | cf->cfMult = naMult; |
---|
656 | cf->cfDiv = naDiv; |
---|
657 | cf->cfExactDiv = naDiv; |
---|
658 | cf->cfPower = naPower; |
---|
659 | cf->cfCopy = naCopy; |
---|
660 | cf->cfWrite = naWrite; |
---|
661 | cf->cfRead = naRead; |
---|
662 | cf->cfDelete = naDelete; |
---|
663 | cf->cfSetMap = naSetMap; |
---|
664 | cf->cfGetDenom = naGetDenom; |
---|
665 | cf->cfGetNumerator = naGetNumerator; |
---|
666 | cf->cfRePart = naCopy; |
---|
667 | cf->cfImPart = naImPart; |
---|
668 | cf->cfCoeffWrite = naCoeffWrite; |
---|
669 | cf->cfDBTest = naDBTest; |
---|
670 | cf->cfGcd = naGcd; |
---|
671 | cf->cfLcm = naLcm; |
---|
672 | cf->cfSize = naSize; |
---|
673 | cf->nCoeffIsEqual = naCoeffIsEqual; |
---|
674 | cf->cfInvers = naInvers; |
---|
675 | cf->cfIntDiv = naDiv; |
---|
676 | |
---|
677 | return FALSE; |
---|
678 | } |
---|
679 | |
---|
680 | |
---|
681 | number naParam(const short iParameter, const coeffs cf) |
---|
682 | { |
---|
683 | assume(getCoeffType(cf) == ID); |
---|
684 | |
---|
685 | const ring R = cf->extRing; |
---|
686 | assume( R != NULL ); |
---|
687 | assume( 0 < iParameter && iParameter <= rVar(R) ); |
---|
688 | |
---|
689 | poly p = p_One(R); p_SetExp(p, iParameter, 1, R); p_Setm(p, R); |
---|
690 | |
---|
691 | return (number) p; |
---|
692 | } |
---|
693 | |
---|
694 | |
---|
695 | /// if m == var(i)/1 => return i, |
---|
696 | int naIsParam(number m, const coeffs cf) |
---|
697 | { |
---|
698 | assume(getCoeffType(cf) == ID); |
---|
699 | |
---|
700 | const ring R = cf->extRing; |
---|
701 | assume( R != NULL ); |
---|
702 | |
---|
703 | return p_Var( (poly)m, R ); |
---|
704 | } |
---|