source: git/factory/cf_map_ext.cc @ 464b18

spielwiese
Last change on this file since 464b18 was 72bfc8, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: deleted @internal
  • Property mode set to 100644
File size: 11.1 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**/
14//*****************************************************************************
15
16#include "config.h"
17
18#include "cf_assert.h"
19#include "debug.h"
20
21#include "canonicalform.h"
22#include "cf_util.h"
23#include "imm.h"
24#include "cf_iter.h"
25
26#ifdef HAVE_NTL
27#include "NTLconvert.h"
28#endif
29
30// cyclotomoic polys:
31#include "cf_cyclo.h"
32
33#include "cf_map_ext.h"
34
35/// helper function
36int findItem (const CFList& list, const CanonicalForm& item)
37{
38  int result= 1;
39  for (CFListIterator i= list; i.hasItem(); i++, result++)
40  {
41    if (i.getItem() == item)
42      return result;
43  }
44  return 0;
45}
46
47/// helper function
48CanonicalForm getItem (const CFList& list, const int& pos)
49{
50  int j= 1;
51  if ((pos > 0) && (pos <= list.length()))
52  {
53    for (CFListIterator i= list; j <= pos; i++, j++)
54    {
55      if (j == pos)
56        return i.getItem();
57    }
58  }
59  return 0;
60}
61
62#ifdef HAVE_NTL
63/// \f$ F_{p} (\alpha ) \subset F_{p}(\beta ) \f$ and \f$ \alpha \f$ is a
64/// primitive element, returns the image of \f$ \alpha \f$
65static inline
66CanonicalForm mapUp (const Variable& alpha, const Variable& beta)
67{
68  int p= getCharacteristic ();
69  zz_p::init (p);
70  zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
71  zz_pE::init (NTL_mipo);
72  zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
73  zz_pE root= FindRoot (NTL_alpha_mipo);
74  return convertNTLzzpE2CF (root, beta);
75}
76
77#endif
78
79/// the CanonicalForm G is the output of map_up, returns F considered as an
80/// element over \f$ F_{p}(\alpha ) \f$, WARNING: make sure coefficients of F
81/// are really elements of a subfield of \f$ F_{p}(\beta ) \f$ which is
82/// isomorphic to \f$ F_{p}(\alpha ) \f$
83static inline
84CanonicalForm
85mapDown (const CanonicalForm& F, const Variable& alpha, const
86          CanonicalForm& G, CFList& source, CFList& dest)
87{
88  CanonicalForm buf, buf2;
89  int counter= 0;
90  int pos;
91  int p= getCharacteristic();
92  int d= degree(getMipo(alpha));
93  int bound= ipower(p, d);
94  CanonicalForm result= 0;
95  CanonicalForm remainder;
96  CanonicalForm alpha_power;
97  if (degree(F) == 0) return F;
98  if (F.level() < 0 && F.isUnivariate())
99  {
100    buf= F;
101    remainder= mod (buf, G);
102    ASSERT (remainder.isZero(), "alpha is not primitive");
103    pos= findItem (source, buf);
104    if (pos == 0)
105      source.append (buf);
106    buf2= buf;
107    while (degree (buf) != 0 && counter < bound)
108    {
109      buf /= G;
110      counter++;
111      if (buf == buf2) break;
112    }
113    ASSERT (counter >= bound, "alpha is not primitive");
114    if (pos == 0)
115    {
116      alpha_power= power (alpha, counter);
117      dest.append (alpha_power);
118    }
119    else
120      alpha_power= getItem (dest, pos);
121    result = alpha_power;
122    return result;
123  }
124  else
125  {
126    for (CFIterator i= F; i.hasTerms(); i++)
127    {
128      buf= mapDown (i.coeff(), alpha, G, source, dest);
129      result += buf*power(F.mvar(), i.exp());
130    }
131    return result;
132  }
133}
134
135/// helper function
136static inline
137CanonicalForm GF2FalphaHelper (const CanonicalForm& F, const Variable& alpha)
138{
139  if (F.isZero())
140    return 0;
141  int exp;
142  CanonicalForm result= 0;
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#ifdef HAVE_NTL
308/// determine a primitive element of \f$ F_{p} (\alpha ) \f$,
309/// \f$ \beta \f$ is a primitive element of a field which is isomorphic to
310/// \f$ F_{p}(\alpha ) \f$
311CanonicalForm
312primitiveElement (const Variable& alpha, Variable& beta, bool fail)
313{
314  bool primitive= false;
315  fail= false;
316  primitive= isPrimitive (alpha, fail);
317  if (fail)
318    return 0;
319  if (primitive)
320  {
321    beta= alpha;
322    return alpha;
323  }
324  CanonicalForm mipo= getMipo (alpha);
325  int d= degree (mipo);
326  int p= getCharacteristic ();
327  zz_p::init (p);
328  zz_pX NTL_mipo;
329  CanonicalForm mipo2;
330  primitive= false;
331  fail= false;
332  do
333  {
334    BuildIrred (NTL_mipo, d);
335    mipo2= convertNTLzzpX2CF (NTL_mipo, Variable (1));
336    beta= rootOf (mipo2);
337    primitive= isPrimitive (beta, fail);
338    if (primitive)
339      break;
340    if (fail)
341      return 0;
342  } while (1);
343  zz_pX alpha_mipo= convertFacCF2NTLzzpX (mipo);
344  zz_pE::init (alpha_mipo);
345  zz_pEX NTL_beta_mipo= to_zz_pEX (NTL_mipo);
346  zz_pE root= FindRoot (NTL_beta_mipo);
347  return convertNTLzzpE2CF (root, alpha);
348}
349#endif
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
369#ifdef HAVE_NTL
370CanonicalForm
371mapPrimElem (const CanonicalForm& primElem, const Variable& alpha,
372             const Variable& beta)
373{
374  if (primElem == alpha)
375    return mapUp (alpha, beta);
376  else
377  {
378    CanonicalForm primElemMipo= findMinPoly (primElem, alpha);
379    int p= getCharacteristic ();
380    zz_p::init (p);
381    zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (beta));
382    zz_pE::init (NTLMipo);
383    zz_pEX NTLPrimElemMipo= convertFacCF2NTLzz_pEX (primElemMipo, NTLMipo);
384    zz_pE root= FindRoot (NTLPrimElemMipo);
385    return convertNTLzzpE2CF (root, beta);
386  }
387}
388
389CanonicalForm
390map (const CanonicalForm& primElem, const Variable& alpha,
391     const CanonicalForm& F, const Variable& beta)
392{
393  CanonicalForm G= F;
394  int order= 0;
395  while (!G.isOne())
396  {
397    G /= primElem;
398    order++;
399  }
400  int p= getCharacteristic ();
401  zz_p::init (p);
402  zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
403  zz_pE::init (NTL_mipo);
404  zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
405  zz_pE NTLBeta= to_zz_pE (convertFacCF2NTLzzpX (beta));
406  vec_zz_pE roots= FindRoots (NTL_alpha_mipo);
407  long ind=-1;
408  for (long i= 0; i < roots.length(); i++)
409  {
410    if (power (roots [i], order)== NTLBeta)
411    {
412      ind= i;
413      break;
414    }
415  }
416  return (convertNTLzzpE2CF (roots[ind], beta));
417}
418
419CanonicalForm
420findMinPoly (const CanonicalForm& F, const Variable& alpha)
421{
422  ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)");
423
424  zz_p::init (getCharacteristic());
425  zz_pX NTLF= convertFacCF2NTLzzpX (F);
426  int d= degree (getMipo (alpha));
427
428  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo(alpha));
429  zz_pE::init (NTLMipo);
430  vec_zz_p pows;
431  pows.SetLength (2*d);
432
433  zz_pE powNTLF;
434  set (powNTLF);
435  zz_pE NTLFE= to_zz_pE (NTLF);
436  zz_pX buf;
437  for (int i= 0; i < 2*d; i++)
438  {
439    buf= rep (powNTLF);
440    buf.rep.SetLength (d);
441    pows [i]= buf.rep[0];
442    powNTLF *= NTLFE;
443  }
444
445  zz_pX NTLMinPoly;
446  MinPolySeq (NTLMinPoly, pows, d);
447
448  return convertNTLzzpX2CF (NTLMinPoly, Variable (1));
449}
450
451#endif
Note: See TracBrowser for help on using the repository browser.