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

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