source: git/factory/cf_map_ext.cc @ 8d1432e

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