source: git/factory/cf_map_ext.cc @ f78374

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