My Project
Loading...
Searching...
No Matches
cf_map_ext.cc
Go to the documentation of this file.
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#ifdef HAVE_FLINT
32#include "FLINTconvert.h"
33#include <flint/fq_nmod_poly_factor.h>
34#endif
35
36// cyclotomoic polys:
37#include "cf_cyclo.h"
38
39#include "cf_map_ext.h"
40
41/// helper function
42int findItem (const CFList& list, const CanonicalForm& item)
43{
44 int result= 1;
45 for (CFListIterator i= list; i.hasItem(); i++, result++)
46 {
47 if (i.getItem() == item)
48 return result;
49 }
50 return 0;
51}
52
53/// helper function
54CanonicalForm getItem (const CFList& list, const int& pos)
55{
56 int j= 1;
57 if ((pos > 0) && (pos <= list.length()))
58 {
59 for (CFListIterator i= list; j <= pos; i++, j++)
60 {
61 if (j == pos)
62 return i.getItem();
63 }
64 }
65 return 0;
66}
67
68/// \f$ F_{p} (\alpha ) \subset F_{p}(\beta ) \f$ and \f$ \alpha \f$ is a
69/// primitive element, returns the image of \f$ \alpha \f$
70static inline
72{
73 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
74 // convert mipo1
80 // convert mipo2 (alpah)
86 // root of first (linear) factor: -absolute Term
89 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
91 // convert
93 // cleanup
98 return r1;
99 #elif defined(HAVE_NTL)
100 int p= getCharacteristic ();
101 if (fac_NTL_char != p)
102 {
104 zz_p::init (p);
105 }
107 zz_pE::init (NTL_mipo);
110 return convertNTLzzpE2CF (root, beta);
111 #else
112 factoryError("NTL/FLINT missing: mapUp");
113 return CanonicalForm(0); // to avoid warnings
114 #endif
115}
116
117
118/// the CanonicalForm G is the output of map_up, returns F considered as an
119/// element over \f$ F_{p}(\alpha ) \f$, WARNING: make sure coefficients of F
120/// are really elements of a subfield of \f$ F_{p}(\beta ) \f$ which is
121/// isomorphic to \f$ F_{p}(\alpha ) \f$
122static inline
124mapDown (const CanonicalForm& F, const Variable& alpha, const
126{
128 int counter= 0;
129 int pos;
130 int p= getCharacteristic();
131 int d= degree(getMipo(alpha));
132 int bound= ipower(p, d);
136 if (degree(F) == 0) return F;
137 if (F.level() < 0 && F.isUnivariate())
138 {
139 buf= F;
140 remainder= mod (buf, G);
141 ASSERT (remainder.isZero(), "alpha is not primitive");
142 pos= findItem (source, buf);
143 if (pos == 0)
144 source.append (buf);
145 buf2= buf;
146 while (degree (buf) != 0 && counter < bound)
147 {
148 buf /= G;
149 counter++;
150 if (buf == buf2) break;
151 }
152 ASSERT (counter >= bound, "alpha is not primitive");
153 if (pos == 0)
154 {
155 alpha_power= power (alpha, counter);
156 dest.append (alpha_power);
157 }
158 else
159 alpha_power= getItem (dest, pos);
161 return result;
162 }
163 else
164 {
165 for (CFIterator i= F; i.hasTerms(); i++)
166 {
167 buf= mapDown (i.coeff(), alpha, G, source, dest);
168 result += buf*power(F.mvar(), i.exp());
169 }
170 return result;
171 }
172}
173
174/// helper function
175static inline
177{
178 if (F.isZero())
179 return 0;
180 int exp;
183 if (F.inBaseDomain())
184 {
185 if (F.isOne()) return 1;
186 buf= F.getval();
187 exp= imm2int(buf);
189 return result;
190 }
191 for (CFIterator i= F; i.hasTerms(); i++)
192 result += GF2FalphaHelper (i.coeff(), alpha)*power (F.mvar(), i.exp());
193 return result;
194}
195
203
205{
208
209 if (F.inCoeffDomain())
210 {
211 if (F.inBaseDomain())
212 return F.mapinto();
213 else
214 {
215 for (CFIterator i= F; i.hasTerms(); i++)
216 {
217 buf= int2imm_gf (i.exp());
218 result += i.coeff().mapinto()*CanonicalForm (buf);
219 }
220 }
221 return result;
222 }
223 for (CFIterator i= F; i.hasTerms(); i++)
224 result += Falpha2GFRep (i.coeff())*power (F.mvar(), i.exp());
225 return result;
226}
227
228/// GF_map_up helper
229static inline
231{
232 if (F.isOne()) return F;
234 if (F.inBaseDomain())
235 return power(F, k);
236 for (CFIterator i= F; i.hasTerms(); i++)
237 result += GFPowUp (i.coeff(), k)*power (F.mvar(), i.exp());
238 return result;
239}
240
242{
243 int d= getGFDegree();
244 ASSERT (d%k == 0, "multiple of GF degree expected");
245 int p= getCharacteristic();
246 int ext_field_size= ipower (p, d);
247 int field_size= ipower ( p, k);
248 int diff= (ext_field_size - 1)/(field_size - 1);
249 return GFPowUp (F, diff);
250}
251
252/// GFMapDown helper
253static inline
255{
256 if (F.isOne()) return F;
258 int exp;
260 if (F.inBaseDomain())
261 {
262 buf= F.getval();
263 exp= imm2int (buf);
264 if ((exp % k) == 0)
265 exp= exp/k;
266 else
267 return -1;
268
269 buf= int2imm_gf (exp);
270 return CanonicalForm (buf);
271 }
272 for (CFIterator i= F; i.hasTerms(); i++)
273 result += GFPowDown (i.coeff(), k)*power (F.mvar(), i.exp());
274 return result;
275}
276
278{
279 int d= getGFDegree();
280 ASSERT (d % k == 0, "multiple of GF degree expected");
281 int p= getCharacteristic();
282 int ext_field_size= ipower (p, d);
283 int field_size= ipower ( p, k);
284 int diff= (ext_field_size - 1)/(field_size - 1);
285 return GFPowDown (F, diff);
286}
287
288/// map F in \f$ F_{p} (\alpha ) \f$ which is generated by G into some
289/// \f$ F_{p}(\beta ) \f$ which is generated by H
290static inline
292 const Variable& alpha, const CanonicalForm& H,
293 CFList& source, CFList& dest)
294{
296 int counter= 0;
297 int pos;
298 int p= getCharacteristic();
299 int d= degree (getMipo(alpha));
300 int bound= ipower(p, d);
304 if (degree(F) <= 0) return F;
305 if (F.level() < 0 && F.isUnivariate())
306 {
307 buf= F;
308 remainder= mod (buf, G);
309 ASSERT (remainder.isZero(), "alpha is not primitive");
310 pos= findItem (source, buf);
311 if (pos == 0)
312 source.append (buf);
313 buf2= buf;
314 while (degree (buf) != 0 && counter < bound)
315 {
316 buf /= G;
317 counter++;
318 if (buf == buf2) break;
319 }
320 ASSERT (counter <= bound, "alpha is not primitive");
321 if (pos == 0)
322 {
323 H_power= buf*power (H, counter);
324 dest.append (H_power);
325 }
326 else
327 H_power= getItem (dest, pos);
328 result = H_power;
329 return result;
330 }
331 else
332 {
333 for (CFIterator i= F; i.hasTerms(); i++)
334 {
335 buf= mapUp (i.coeff(), G, alpha, H, source, dest);
336 result += buf*power(F.mvar(), i.exp());
337 }
338 return result;
339 }
340}
341
344{
345 bool primitive= false;
346 fail= false;
348 if (fail)
349 return 0;
350 if (primitive)
351 {
352 beta= alpha;
353 return alpha;
354 }
356 int d= degree (mipo);
357 int p= getCharacteristic ();
358 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
361 #elif defined(HAVE_NTL)
362 if (fac_NTL_char != p)
363 {
365 zz_p::init (p);
366 }
368 #else
369 factoryError("NTL/FLINT missing: primitiveElement");
370 return CanonicalForm(0);
371 #endif
373 primitive= false;
374 fail= false;
375 bool initialized= false;
376 do
377 {
378 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
381 #elif defined(HAVE_NTL)
382 BuildIrred (NTL_mipo, d);
384 #endif
385 if (!initialized)
386 beta= rootOf (mipo2);
387 else
388 setMipo (beta, mipo2);
390 if (primitive)
391 break;
392 if (fail)
393 return 0;
394 } while (1);
395 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
397 // convert alpha_mipo
403 // convert beta_mipo (mipo2)
409 // root of first (linear) factor: -absolute Term
412 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
413 fq_nmod_neg(r0, r0, ctx);
414 // convert
416 // cleanup
421 return r1;
422 #elif defined(HAVE_NTL)
424 zz_pE::init (alpha_mipo);
427 return convertNTLzzpE2CF (root, alpha);
428 #endif
429}
430
434 CFList& dest)
435{
436 return mapUp (F, im_prim_elem, alpha, prim_elem, dest, source);
437}
438
440mapUp (const CanonicalForm& F, const Variable& alpha, const Variable& /*beta*/,
442 CFList& source, CFList& dest)
443{
444 if (prim_elem == alpha)
445 return F (im_prim_elem, alpha);
446 return mapUp (F, prim_elem, alpha, im_prim_elem, source, dest);
447}
448
449#if defined(HAVE_NTL) || defined(HAVE_FLINT)
452 const Variable& beta)
453{
454 if (primElem == alpha)
455 return mapUp (alpha, beta);
456 else
457 {
459 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
460 // convert mipo1
466 // convert mipo2 (primElemMipo)
471 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
472 // root of first (linear) factor: -absolute Term
475 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
476 fq_nmod_neg(r0, r0, ctx);
477 // convert
479 // cleanup
484 return r1;
485 #elif defined(HAVE_NTL)
486 int p= getCharacteristic ();
487 if (fac_NTL_char != p)
488 {
490 zz_p::init (p);
491 }
493 zz_pE::init (NTLMipo);
496 return convertNTLzzpE2CF (root, beta);
497 #else
498 factoryError("NTL/FLINT missing: mapPrimElem");
499 #endif
500 }
501}
502#endif
503
506 const CanonicalForm& F, const Variable& beta)
507{
508 CanonicalForm G= F;
509 int order= 0;
510 while (!G.isOne())
511 {
512 G /= primElem;
513 order++;
514 }
515 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
516 // convert mipo
522 // convert mipo2 (alpha)
527 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
528 // roots in fac, #=fac->num
529 int ind=-1;
535 fmpz_set_si(FLINTorder,order);
536 for(int i=0;i< fac->num;i++)
537 {
538 // get the root (-abs.term of linear factor)
539 fq_nmod_poly_get_coeff(r0,fac->poly+i,0,ctx);
541 // r^order
543 // ==beta?
545 {
546 ind=i;
547 break;
548 }
549 }
551 // convert
552 fq_nmod_poly_get_coeff(r0,fac->poly+ind,0,ctx);
555 // cleanup
561 return r1;
562 #elif defined(HAVE_NTL)
563 int p= getCharacteristic ();
564 if (fac_NTL_char != p)
565 {
567 zz_p::init (p);
568 }
570 zz_pE::init (NTL_mipo);
574 long ind=-1;
575 for (long i= 0; i < roots.length(); i++)
576 {
577 if (power (roots [i], order)== NTLBeta)
578 {
579 ind= i;
580 break;
581 }
582 }
583 return (convertNTLzzpE2CF (roots[ind], beta));
584 #else
585 factoryError("NTL/FLINT missing: map");
586 return CanonicalForm(0);
587 #endif
588}
589
590#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
591/*
592 g is in Fp[x]
593 F is in Fp[t]
594 h is in Fp[t]
595 In the finite field Fp[t]/h(t), find g(x) in Fp[x] such that
596 g(F(t)) = 0 mod h(t)
597 i.e. g is the minpoly of the element F(t) of the finite field.
598*/
599static void minpoly(nmod_poly_t g, const nmod_poly_t F, const nmod_poly_t h)
600{
601 slong i;
603 mp_limb_t p = h->mod.n;
606
609
611 for (i = 0; i < 2*d; i++)
612 {
615 }
616
618
619 /* something went horribly wrong if V does not kill the whole sequence */
622
624#if WANT_ASSERT
625 {
626 nmod_poly_t z;
627 nmod_poly_init(z, p);
628 nmod_poly_compose_mod(z, g, F, h);
631 }
632#endif
635}
636#endif
637
638
639#if defined(HAVE_NTL) || defined(HAVE_FLINT)
642{
643 ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)");
644
645 int p=getCharacteristic();
646 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
651 minpoly(g,FLINT_F,FLINT_alpha);
656 return res;
657 #elif defined(HAVE_NTL)
658 if (fac_NTL_char != p)
659 {
661 zz_p::init (p);
662 }
664 int d= degree (getMipo (alpha));
665
667 zz_pE::init (NTLMipo);
669 pows.SetLength (2*d);
670
672 set (powNTLF);
674 zz_pX buf;
675 for (int i= 0; i < 2*d; i++)
676 {
677 buf= rep (powNTLF);
678 buf.rep.SetLength (d);
679 pows [i]= buf.rep[0];
680 powNTLF *= NTLFE;
681 }
682
685
687 #else
688 factoryError("NTL/FLINT missing: findMinPoly");
689 #endif
690}
691#endif
void convertFacCF2Fq_nmod_t(fq_nmod_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory element of F_q to a FLINT fq_nmod_t, does not do any memory allocation for po...
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
CanonicalForm convertFq_nmod_t2FacCF(const fq_nmod_t poly, const Variable &alpha, const fq_nmod_ctx_t)
conversion of a FLINT element of F_q to a CanonicalForm with alg. variable alpha
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
VAR long fac_NTL_char
Definition NTLconvert.cc:46
Conversion to and from NTL.
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
int getGFDegree()
Definition cf_char.cc:75
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
int i
Definition cfEzgcd.cc:132
int k
Definition cfEzgcd.cc:99
int p
Definition cfModGcd.cc:4086
g
Definition cfModGcd.cc:4098
assertions for Factory
#define ASSERT(expression, message)
Definition cf_assert.h:99
bool isPrimitive(const Variable &alpha, bool &fail)
checks if alpha is a primitive element, alpha is assumed to be an algebraic variable over some finite...
Definition cf_cyclo.cc:131
Compute cyclotomic polynomials and factorize integers by brute force.
Iterators for CanonicalForm's.
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition cf_map_ext.cc:42
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
static CanonicalForm GF2FalphaHelper(const CanonicalForm &F, const Variable &alpha)
helper function
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition cf_map_ext.cc:54
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition cf_map_ext.cc:71
static CanonicalForm GFPowUp(const CanonicalForm &F, int k)
GF_map_up helper.
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto
static CanonicalForm GFPowDown(const CanonicalForm &F, int k)
GFMapDown helper.
This file implements functions to map between extensions of finite fields.
GLOBAL_VAR flint_rand_t FLINTrandom
Definition cf_random.cc:25
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
class to iterate through CanonicalForm's
Definition cf_iter.h:44
factory's main class
CF_NO_INLINE bool isZero() const
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
InternalCF * getval() const
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
bool inBaseDomain() const
CanonicalForm mapinto() const
bool isUnivariate() const
virtual class for internal CanonicalForm's
Definition int_cf.h:47
int length() const
void append(const T &)
factory's class for variables
Definition factory.h:127
functions to print debug output
Variable alpha
return result
#define slong
CanonicalForm res
Definition facAbsFact.cc:60
Variable beta
Definition facAbsFact.cc:95
CanonicalForm H
Definition facAbsFact.cc:60
CanonicalForm mipo
Definition facAlgExt.cc:57
CanonicalForm buf2
Definition facFqBivar.cc:76
int j
Definition facHensel.cc:110
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
Definition fac_util.cc:115
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition variable.cc:162
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition variable.cc:219
INST_VAR CanonicalForm gf_mipo
Definition gfops.cc:56
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
static long imm2int(const InternalCF *const imm)
Definition imm.h:70
InternalCF * int2imm_gf(long i)
Definition imm.h:106
STATIC_VAR TreeM * G
Definition janet.cc:31
STATIC_VAR Poly * h
Definition janet.cc:971
gmp_float exp(const gmp_float &a)
STATIC_VAR gmp_float * diff
int status int void * buf
Definition si_signals.h:69