source: git/factory/cf_map_ext.cc @ 9fd0b1

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