source: git/factory/cf_map_ext.cc @ 55608a7

fieker-DuValspielwiese
Last change on this file since 55608a7 was 55608a7, checked in by Martin Lee <martinlee84@…>, 13 years ago
added new functionality to map between extension git-svn-id: file:///usr/local/Singular/svn/trunk@14232 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 11.0 KB
Line 
1// -*- c++ -*-
2//*****************************************************************************
3/** @file cf_map_ext.cc
4 *
5 * @author Martin Lee
6 * @date   16.11.2009
7 *
8 * This file implements functions to map between extensions of finite fields
9 *
10 * @par Copyright:
11 *   (c) by The SINGULAR Team, see LICENSE file
12 *
13 * @internal
14 * @version \$Id$
15 *
16**/
17//*****************************************************************************
18
19#include <config.h>
20
21#include "assert.h"
22#include "debug.h"
23
24#include "canonicalform.h"
25#include "cf_util.h"
26
27#ifdef HAVE_NTL
28#include <NTL/ZZ_pEXFactoring.h>
29#include "NTLconvert.h"
30#endif
31
32// cyclotomoic polys:
33#include "cf_cyclo.h"
34
35#include "cf_map_ext.h"
36
37#ifdef HAVE_NTL
38
39/// helper function
40int findItem (const CFList& list, const CanonicalForm& item)
41{
42  int result= 1;
43  for (CFListIterator i= list; i.hasItem(); i++, result++)
44  {
45    if (i.getItem() == item)
46      return result;
47  }
48  return 0;
49}
50
51/// helper function
52CanonicalForm getItem (const CFList& list, const int& pos)
53{
54  int j= 1;
55  if (pos > list.length() || pos < 1) return 0;
56  for (CFListIterator i= list; j <= pos; i++, j++)
57  {
58    if (j == pos)
59      return i.getItem();
60  }
61}
62
63
64/// \f$ F_{p} (\alpha ) \subset F_{p}(\beta ) \f$ and \f$ \alpha \f$ is a
65/// primitive element, returns the image of \f$ \alpha \f$
66static inline
67CanonicalForm mapUp (const Variable& alpha, const Variable& beta)
68{
69  int p= getCharacteristic ();
70  zz_p::init (p);
71  zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
72  zz_pE::init (NTL_mipo);
73  zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
74  zz_pE root= FindRoot (NTL_alpha_mipo);
75  return convertNTLzzpE2CF (root, beta);
76}
77
78/// the CanonicalForm G is the output of map_up, returns F considered as an
79/// element over \f$ F_{p}(\alpha ) \f$, WARNING: make sure coefficients of F
80/// are really elements of a subfield of \f$ F_{p}(\beta ) \f$ which is
81/// isomorphic to \f$ F_{p}(\alpha ) \f$
82static inline
83CanonicalForm
84mapDown (const CanonicalForm& F, const Variable& alpha, const
85          CanonicalForm& G, CFList& source, CFList& dest)
86{
87  CanonicalForm buf, buf2;
88  int counter= 0;
89  int pos;
90  int p= getCharacteristic();
91  int d= degree(getMipo(alpha));
92  int bound= ipower(p, d);
93  CanonicalForm result= 0;
94  CanonicalForm remainder;
95  CanonicalForm alpha_power;
96  if (degree(F) == 0) return F;
97  if (F.level() < 0 && F.isUnivariate())
98  {
99    buf= F;
100    remainder= mod (buf, G);
101    ASSERT (remainder.isZero(), "alpha is not primitive");
102    pos= findItem (source, buf);
103    if (pos == 0)
104      source.append (buf);
105    buf2= buf;
106    while (degree (buf) != 0 && counter < bound)
107    {
108      buf /= G;
109      counter++;
110      if (buf == buf2) break;
111    }
112    ASSERT (counter >= bound, "alpha is not primitive");
113    if (pos == 0)
114    {
115      alpha_power= power (alpha, counter);
116      dest.append (alpha_power);
117    }
118    else
119      alpha_power= getItem (dest, pos);
120    result = alpha_power;
121    return result;
122  }
123  else
124  {
125    for (CFIterator i= F; i.hasTerms(); i++)
126    {
127      buf= mapDown (i.coeff(), alpha, G, source, dest);
128      result += buf*power(F.mvar(), i.exp());
129    }
130    return result;
131  }
132}
133
134/// helper function
135static inline
136CanonicalForm GF2FalphaHelper (const CanonicalForm& F, const Variable& alpha)
137{
138  if (F.isZero())
139    return 0;
140  int exp;
141  CanonicalForm result= 0;
142  char gf_name_buf= gf_name;
143  InternalCF* buf;
144  if (F.inBaseDomain())
145  {
146    if (F.isOne()) return 1;
147    buf= F.getval();
148    exp= imm2int(buf);
149    result= power (alpha, exp).mapinto();
150    return result;
151  }
152  for (CFIterator i= F; i.hasTerms(); i++)
153    result += GF2FalphaHelper (i.coeff(), alpha)*power (F.mvar(), i.exp());
154  return result;
155}
156
157/// changes representation by primitive element to representation by residue
158/// classes modulo a Conway polynomial
159CanonicalForm GF2FalphaRep (const CanonicalForm& F, const Variable& alpha)
160{
161  Variable beta= rootOf (gf_mipo);
162  return GF2FalphaHelper (F, beta) (alpha, beta);
163}
164
165/// change representation by residue classes modulo a Conway polynomial
166/// to representation by primitive element
167CanonicalForm Falpha2GFRep (const CanonicalForm& F)
168{
169  CanonicalForm result= 0;
170  InternalCF* buf;
171
172  if (F.inCoeffDomain())
173  {
174    if (F.inBaseDomain())
175      return F.mapinto();
176    else
177    {
178      for (CFIterator i= F; i.hasTerms(); i++)
179      {
180        buf= int2imm_gf (i.exp());
181        result += i.coeff().mapinto()*CanonicalForm (buf);
182      }
183    }
184    return result;
185  }
186  for (CFIterator i= F; i.hasTerms(); i++)
187    result += Falpha2GFRep (i.coeff())*power (F.mvar(), i.exp());
188  return result;
189}
190
191/// GF_map_up helper
192static inline
193CanonicalForm GFPowUp (const CanonicalForm & F, int k)
194{
195  if (F.isOne()) return F;
196  CanonicalForm result= 0;
197  if (F.inBaseDomain())
198    return power(F, k);
199  for (CFIterator i= F; i.hasTerms(); i++)
200    result += GFPowUp (i.coeff(), k)*power (F.mvar(), i.exp());
201  return result;
202}
203
204/// maps a polynomial over \f$ GF(p^{k}) \f$ to a polynomial over
205/// \f$ GF(p^{d}) \f$ , d needs to be a multiple of k
206CanonicalForm GFMapUp (const CanonicalForm & F, int k)
207{
208  int d= getGFDegree();
209  ASSERT (d%k == 0, "multiple of GF degree expected");
210  int p= getCharacteristic();
211  int ext_field_size= ipower (p, d);
212  int field_size= ipower ( p, k);
213  int diff= (ext_field_size - 1)/(field_size - 1);
214  return GFPowUp (F, diff);
215}
216
217/// GFMapDown helper
218static inline
219CanonicalForm GFPowDown (const CanonicalForm & F, int k)
220{
221  if (F.isOne()) return F;
222  CanonicalForm result= 0;
223  int exp;
224  InternalCF* buf;
225  if (F.inBaseDomain())
226  {
227    buf= F.getval();
228    exp= imm2int (buf);
229    if ((exp % k) == 0)
230      exp= exp/k;
231    else
232      return -1;
233
234    buf= int2imm_gf (exp);
235    return CanonicalForm (buf);
236  }
237  for (CFIterator i= F; i.hasTerms(); i++)
238    result += GFPowDown (i.coeff(), k)*power (F.mvar(), i.exp());
239  return result;
240}
241
242/// maps a polynomial over \f$ GF(p^{d}) \f$ to a polynomial over
243/// \f$ GF(p^{k})\f$ , d needs to be a multiple of k
244CanonicalForm GFMapDown (const CanonicalForm & F, int k)
245{
246  int d= getGFDegree();
247  ASSERT (d % k == 0, "multiple of GF degree expected");
248  int p= getCharacteristic();
249  int ext_field_size= ipower (p, d);
250  int field_size= ipower ( p, k);
251  int diff= (ext_field_size - 1)/(field_size - 1);
252  return GFPowDown (F, diff);
253}
254
255static inline
256CanonicalForm mapUp (const CanonicalForm& F, const CanonicalForm& G,
257                      const Variable& alpha, const CanonicalForm& H,
258                      CFList& source, CFList& dest)
259{
260  CanonicalForm buf, buf2;
261  int counter= 0;
262  int pos;
263  int p= getCharacteristic();
264  int d= degree (getMipo(alpha));
265  int bound= ipower(p, d);
266  CanonicalForm result= 0;
267  CanonicalForm remainder;
268  CanonicalForm H_power;
269  if (degree(F) <= 0) return F;
270  if (F.level() < 0 && F.isUnivariate())
271  {
272    buf= F;
273    remainder= mod (buf, G);
274    ASSERT (remainder.isZero(), "alpha is not primitive");
275    pos= findItem (source, buf);
276    if (pos == 0)
277      source.append (buf);
278    buf2= buf;
279    while (degree (buf) != 0 && counter < bound)
280    {
281      buf /= G;
282      counter++;
283      if (buf == buf2) break;
284    }
285    ASSERT (counter >= bound, "alpha is not primitive");
286    if (pos == 0)
287    {
288      H_power= buf*power (H, counter);
289      dest.append (H_power);
290    }
291    else
292      H_power= getItem (dest, pos);
293    result = H_power;
294    return result;
295  }
296  else
297  {
298    for (CFIterator i= F; i.hasTerms(); i++)
299    {
300      buf= mapUp (i.coeff(), G, alpha, H, source, dest);
301      result += buf*power(F.mvar(), i.exp());
302    }
303    return result;
304  }
305}
306
307/// determine a primitive element of \f$ F_{p} (\alpha ) \f$,
308/// \f$ \beta \f$ is a primitive element of a field which is isomorphic to
309/// \f$ F_{p}(\alpha ) \f$
310CanonicalForm
311primitiveElement (const Variable& alpha, Variable& beta, bool fail)
312{
313  bool primitive= false;
314  fail= false;
315  primitive= isPrimitive (alpha, fail);
316  if (fail)
317    return 0;
318  if (primitive)
319  {
320    beta= alpha;
321    return alpha;
322  }
323  CanonicalForm mipo= getMipo (alpha);
324  int d= degree (mipo);
325  int p= getCharacteristic ();
326  zz_p::init (p);
327  zz_pX NTL_mipo;
328  CanonicalForm mipo2;
329  primitive= false;
330  fail= false;
331  do
332  {
333    BuildIrred (NTL_mipo, d);
334    mipo2= convertNTLzzpX2CF (NTL_mipo, Variable (1));
335    beta= rootOf (mipo2);
336    primitive= isPrimitive (beta, fail);
337    if (primitive)
338      break;
339    if (fail)
340      return 0;
341  } while (1);
342  zz_pX alpha_mipo= convertFacCF2NTLzzpX (mipo);
343  zz_pE::init (alpha_mipo);
344  zz_pEX NTL_beta_mipo= to_zz_pEX (NTL_mipo);
345  zz_pE root= FindRoot (NTL_beta_mipo);
346  return convertNTLzzpE2CF (root, alpha);
347}
348
349CanonicalForm
350mapDown (const CanonicalForm& F, const CanonicalForm& prim_elem, const
351          CanonicalForm& im_prim_elem, const Variable& alpha, CFList& source,
352          CFList& dest)
353{
354  return mapUp (F, im_prim_elem, alpha, prim_elem, dest, source);
355}
356
357CanonicalForm
358mapUp (const CanonicalForm& F, const Variable& alpha, const Variable& beta,
359        const CanonicalForm& prim_elem, const CanonicalForm& im_prim_elem,
360        CFList& source, CFList& dest)
361{
362  if (prim_elem == alpha)
363    return F (im_prim_elem, alpha);
364  return mapUp (F, prim_elem, alpha, im_prim_elem, source, dest);
365}
366
367CanonicalForm
368mapPrimElem (const CanonicalForm& primElem, const Variable& alpha,
369             const Variable& beta)
370{
371  if (primElem == alpha)
372    return mapUp (alpha, beta);
373  else
374  {
375    CanonicalForm primElemMipo= findMinPoly (primElem, alpha);
376    int p= getCharacteristic ();
377    zz_p::init (p);
378    zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (beta)); 
379    zz_pE::init (NTLMipo);
380    zz_pEX NTLPrimElemMipo= convertFacCF2NTLzz_pEX (primElemMipo, NTLMipo);
381    zz_pE root= FindRoot (NTLPrimElemMipo);
382    return convertNTLzzpE2CF (root, beta);
383  }
384}
385
386CanonicalForm
387map (const CanonicalForm& primElem, const Variable& alpha,
388     const CanonicalForm& F, const Variable& beta)
389{
390  CanonicalForm G= F;
391  int order= 0;
392  while (!G.isOne())
393  {
394    G /= primElem;
395    order++;
396  }
397  int p= getCharacteristic ();
398  zz_p::init (p);
399  zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta)); 
400  zz_pE::init (NTL_mipo);
401  zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
402  zz_pE NTLBeta= to_zz_pE (convertFacCF2NTLzzpX (beta));
403  vec_zz_pE roots= FindRoots (NTL_alpha_mipo);
404  long ind;
405  for (long i= 0; i < roots.length(); i++)
406  {
407    if (power (roots [i], order)== NTLBeta)
408    {
409      ind= i;
410      break;
411    }
412  }
413  return (convertNTLzzpE2CF (roots[ind], beta));
414}
415
416CanonicalForm
417findMinPoly (const CanonicalForm& F, const Variable& alpha)
418{
419  ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)");
420
421  zz_p::init (getCharacteristic());
422  zz_pX NTLF= convertFacCF2NTLzzpX (F);
423  int d= degree (getMipo (alpha));
424
425  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo(alpha));
426  zz_pE::init (NTLMipo);
427  vec_zz_p pows;
428  pows.SetLength (2*d);
429
430  zz_pE powNTLF;
431  set (powNTLF);
432  zz_pE NTLFE= to_zz_pE (NTLF);
433  zz_pX buf;
434  for (int i= 0; i < 2*d; i++)
435  {
436    buf= rep (powNTLF);
437    buf.rep.SetLength (d);
438    pows [i]= buf.rep[0];
439    powNTLF *= NTLFE;
440  }
441
442  zz_pX NTLMinPoly;
443  MinPolySeq (NTLMinPoly, pows, d);
444
445  return convertNTLzzpX2CF (NTLMinPoly, Variable (1));
446}
447
448#endif
Note: See TracBrowser for help on using the repository browser.