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