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 #endif
34
35 // cyclotomoic polys:
36 #include "cf_cyclo.h"
37
38 #include "cf_map_ext.h"
39
40 /// helper function
findItem(const CFList & list,const CanonicalForm & item)41 int findItem (const CFList& list, const CanonicalForm& item)
42 {
43 int result= 1;
44 for (CFListIterator i= list; i.hasItem(); i++, result++)
45 {
46 if (i.getItem() == item)
47 return result;
48 }
49 return 0;
50 }
51
52 /// helper function
getItem(const CFList & list,const int & pos)53 CanonicalForm getItem (const CFList& list, const int& pos)
54 {
55 int j= 1;
56 if ((pos > 0) && (pos <= list.length()))
57 {
58 for (CFListIterator i= list; j <= pos; i++, j++)
59 {
60 if (j == pos)
61 return i.getItem();
62 }
63 }
64 return 0;
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$
69 static inline
mapUp(const Variable & alpha,const Variable & beta)70 CanonicalForm mapUp (const Variable& alpha, const Variable& beta)
71 {
72 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
73 // convert mipo1
74 nmod_poly_t mipo1;
75 convertFacCF2nmod_poly_t(mipo1,getMipo(beta));
76 fq_nmod_ctx_t ctx;
77 fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
78 nmod_poly_clear(mipo1);
79 // convert mipo2 (alpah)
80 fq_nmod_poly_t mipo2;
81 convertFacCF2Fq_nmod_poly_t(mipo2,getMipo(alpha),ctx);
82 fq_nmod_poly_factor_t fac;
83 fq_nmod_poly_factor_init(fac,ctx);
84 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
85 // root of first (linear) factor: -absolute Term
86 fq_nmod_t r0;
87 fq_nmod_init(r0, ctx);
88 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
89 fq_nmod_neg(r0, r0, ctx);
90 // convert
91 CanonicalForm r1=convertFq_nmod_t2FacCF(r0,beta,ctx);
92 // cleanup
93 fq_nmod_poly_factor_clear(fac,ctx);
94 fq_nmod_clear(r0, ctx);
95 fq_nmod_poly_clear(mipo2,ctx);
96 fq_nmod_ctx_clear(ctx);
97 return r1;
98 #elif defined(HAVE_NTL)
99 int p= getCharacteristic ();
100 if (fac_NTL_char != p)
101 {
102 fac_NTL_char= p;
103 zz_p::init (p);
104 }
105 zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
106 zz_pE::init (NTL_mipo);
107 zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
108 zz_pE root= FindRoot (NTL_alpha_mipo);
109 return convertNTLzzpE2CF (root, beta);
110 #else
111 factoryError("NTL/FLINT missing: mapUp");
112 return CanonicalForm(0); // to avoid warnings
113 #endif
114 }
115
116
117 /// the CanonicalForm G is the output of map_up, returns F considered as an
118 /// element over \f$ F_{p}(\alpha ) \f$, WARNING: make sure coefficients of F
119 /// are really elements of a subfield of \f$ F_{p}(\beta ) \f$ which is
120 /// isomorphic to \f$ F_{p}(\alpha ) \f$
121 static inline
122 CanonicalForm
mapDown(const CanonicalForm & F,const Variable & alpha,const CanonicalForm & G,CFList & source,CFList & dest)123 mapDown (const CanonicalForm& F, const Variable& alpha, const
124 CanonicalForm& G, CFList& source, CFList& dest)
125 {
126 CanonicalForm buf, buf2;
127 int counter= 0;
128 int pos;
129 int p= getCharacteristic();
130 int d= degree(getMipo(alpha));
131 int bound= ipower(p, d);
132 CanonicalForm result= 0;
133 CanonicalForm remainder;
134 CanonicalForm alpha_power;
135 if (degree(F) == 0) return F;
136 if (F.level() < 0 && F.isUnivariate())
137 {
138 buf= F;
139 remainder= mod (buf, G);
140 ASSERT (remainder.isZero(), "alpha is not primitive");
141 pos= findItem (source, buf);
142 if (pos == 0)
143 source.append (buf);
144 buf2= buf;
145 while (degree (buf) != 0 && counter < bound)
146 {
147 buf /= G;
148 counter++;
149 if (buf == buf2) break;
150 }
151 ASSERT (counter >= bound, "alpha is not primitive");
152 if (pos == 0)
153 {
154 alpha_power= power (alpha, counter);
155 dest.append (alpha_power);
156 }
157 else
158 alpha_power= getItem (dest, pos);
159 result = alpha_power;
160 return result;
161 }
162 else
163 {
164 for (CFIterator i= F; i.hasTerms(); i++)
165 {
166 buf= mapDown (i.coeff(), alpha, G, source, dest);
167 result += buf*power(F.mvar(), i.exp());
168 }
169 return result;
170 }
171 }
172
173 /// helper function
174 static inline
GF2FalphaHelper(const CanonicalForm & F,const Variable & alpha)175 CanonicalForm GF2FalphaHelper (const CanonicalForm& F, const Variable& alpha)
176 {
177 if (F.isZero())
178 return 0;
179 int exp;
180 CanonicalForm result= 0;
181 InternalCF* buf;
182 if (F.inBaseDomain())
183 {
184 if (F.isOne()) return 1;
185 buf= F.getval();
186 exp= imm2int(buf);
187 result= power (alpha, exp).mapinto();
188 return result;
189 }
190 for (CFIterator i= F; i.hasTerms(); i++)
191 result += GF2FalphaHelper (i.coeff(), alpha)*power (F.mvar(), i.exp());
192 return result;
193 }
194
GF2FalphaRep(const CanonicalForm & F,const Variable & alpha)195 CanonicalForm GF2FalphaRep (const CanonicalForm& F, const Variable& alpha)
196 {
197 Variable beta= rootOf (gf_mipo);
198 CanonicalForm result= GF2FalphaHelper (F, beta) (alpha, beta);
199 prune (beta);
200 return result;
201 }
202
Falpha2GFRep(const CanonicalForm & F)203 CanonicalForm Falpha2GFRep (const CanonicalForm& F)
204 {
205 CanonicalForm result= 0;
206 InternalCF* buf;
207
208 if (F.inCoeffDomain())
209 {
210 if (F.inBaseDomain())
211 return F.mapinto();
212 else
213 {
214 for (CFIterator i= F; i.hasTerms(); i++)
215 {
216 buf= int2imm_gf (i.exp());
217 result += i.coeff().mapinto()*CanonicalForm (buf);
218 }
219 }
220 return result;
221 }
222 for (CFIterator i= F; i.hasTerms(); i++)
223 result += Falpha2GFRep (i.coeff())*power (F.mvar(), i.exp());
224 return result;
225 }
226
227 /// GF_map_up helper
228 static inline
GFPowUp(const CanonicalForm & F,int k)229 CanonicalForm GFPowUp (const CanonicalForm & F, int k)
230 {
231 if (F.isOne()) return F;
232 CanonicalForm result= 0;
233 if (F.inBaseDomain())
234 return power(F, k);
235 for (CFIterator i= F; i.hasTerms(); i++)
236 result += GFPowUp (i.coeff(), k)*power (F.mvar(), i.exp());
237 return result;
238 }
239
GFMapUp(const CanonicalForm & F,int k)240 CanonicalForm GFMapUp (const CanonicalForm & F, int k)
241 {
242 int d= getGFDegree();
243 ASSERT (d%k == 0, "multiple of GF degree expected");
244 int p= getCharacteristic();
245 int ext_field_size= ipower (p, d);
246 int field_size= ipower ( p, k);
247 int diff= (ext_field_size - 1)/(field_size - 1);
248 return GFPowUp (F, diff);
249 }
250
251 /// GFMapDown helper
252 static inline
GFPowDown(const CanonicalForm & F,int k)253 CanonicalForm GFPowDown (const CanonicalForm & F, int k)
254 {
255 if (F.isOne()) return F;
256 CanonicalForm result= 0;
257 int exp;
258 InternalCF* buf;
259 if (F.inBaseDomain())
260 {
261 buf= F.getval();
262 exp= imm2int (buf);
263 if ((exp % k) == 0)
264 exp= exp/k;
265 else
266 return -1;
267
268 buf= int2imm_gf (exp);
269 return CanonicalForm (buf);
270 }
271 for (CFIterator i= F; i.hasTerms(); i++)
272 result += GFPowDown (i.coeff(), k)*power (F.mvar(), i.exp());
273 return result;
274 }
275
GFMapDown(const CanonicalForm & F,int k)276 CanonicalForm GFMapDown (const CanonicalForm & F, int k)
277 {
278 int d= getGFDegree();
279 ASSERT (d % k == 0, "multiple of GF degree expected");
280 int p= getCharacteristic();
281 int ext_field_size= ipower (p, d);
282 int field_size= ipower ( p, k);
283 int diff= (ext_field_size - 1)/(field_size - 1);
284 return GFPowDown (F, diff);
285 }
286
287 /// map F in \f$ F_{p} (\alpha ) \f$ which is generated by G into some
288 /// \f$ F_{p}(\beta ) \f$ which is generated by H
289 static inline
mapUp(const CanonicalForm & F,const CanonicalForm & G,const Variable & alpha,const CanonicalForm & H,CFList & source,CFList & dest)290 CanonicalForm mapUp (const CanonicalForm& F, const CanonicalForm& G,
291 const Variable& alpha, const CanonicalForm& H,
292 CFList& source, CFList& dest)
293 {
294 CanonicalForm buf, buf2;
295 int counter= 0;
296 int pos;
297 int p= getCharacteristic();
298 int d= degree (getMipo(alpha));
299 int bound= ipower(p, d);
300 CanonicalForm result= 0;
301 CanonicalForm remainder;
302 CanonicalForm H_power;
303 if (degree(F) <= 0) return F;
304 if (F.level() < 0 && F.isUnivariate())
305 {
306 buf= F;
307 remainder= mod (buf, G);
308 ASSERT (remainder.isZero(), "alpha is not primitive");
309 pos= findItem (source, buf);
310 if (pos == 0)
311 source.append (buf);
312 buf2= buf;
313 while (degree (buf) != 0 && counter < bound)
314 {
315 buf /= G;
316 counter++;
317 if (buf == buf2) break;
318 }
319 ASSERT (counter <= bound, "alpha is not primitive");
320 if (pos == 0)
321 {
322 H_power= buf*power (H, counter);
323 dest.append (H_power);
324 }
325 else
326 H_power= getItem (dest, pos);
327 result = H_power;
328 return result;
329 }
330 else
331 {
332 for (CFIterator i= F; i.hasTerms(); i++)
333 {
334 buf= mapUp (i.coeff(), G, alpha, H, source, dest);
335 result += buf*power(F.mvar(), i.exp());
336 }
337 return result;
338 }
339 }
340
341 CanonicalForm
primitiveElement(const Variable & alpha,Variable & beta,bool & fail)342 primitiveElement (const Variable& alpha, Variable& beta, bool& fail)
343 {
344 bool primitive= false;
345 fail= false;
346 primitive= isPrimitive (alpha, fail);
347 if (fail)
348 return 0;
349 if (primitive)
350 {
351 beta= alpha;
352 return alpha;
353 }
354 CanonicalForm mipo= getMipo (alpha);
355 int d= degree (mipo);
356 int p= getCharacteristic ();
357 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
358 nmod_poly_t FLINT_mipo;
359 nmod_poly_init(FLINT_mipo,p);
360 #elif defined(HAVE_NTL)
361 if (fac_NTL_char != p)
362 {
363 fac_NTL_char= p;
364 zz_p::init (p);
365 }
366 zz_pX NTL_mipo;
367 #else
368 factoryError("NTL/FLINT missing: primitiveElement");
369 return CanonicalForm(0);
370 #endif
371 CanonicalForm mipo2;
372 primitive= false;
373 fail= false;
374 bool initialized= false;
375 do
376 {
377 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
378 nmod_poly_randtest_monic_irreducible(FLINT_mipo, FLINTrandom, d+1);
379 mipo2=convertnmod_poly_t2FacCF(FLINT_mipo,Variable(1));
380 #elif defined(HAVE_NTL)
381 BuildIrred (NTL_mipo, d);
382 mipo2= convertNTLzzpX2CF (NTL_mipo, Variable (1));
383 #endif
384 if (!initialized)
385 beta= rootOf (mipo2);
386 else
387 setMipo (beta, mipo2);
388 primitive= isPrimitive (beta, fail);
389 if (primitive)
390 break;
391 if (fail)
392 return 0;
393 } while (1);
394 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
395 nmod_poly_clear(FLINT_mipo);
396 // convert alpha_mipo
397 nmod_poly_t alpha_mipo;
398 convertFacCF2nmod_poly_t(alpha_mipo,mipo);
399 fq_nmod_ctx_t ctx;
400 fq_nmod_ctx_init_modulus(ctx,alpha_mipo,"t");
401 nmod_poly_clear(alpha_mipo);
402 // convert beta_mipo (mipo2)
403 fq_nmod_poly_t FLINT_beta_mipo;
404 convertFacCF2Fq_nmod_poly_t(FLINT_beta_mipo,mipo2,ctx);
405 fq_nmod_poly_factor_t fac;
406 fq_nmod_poly_factor_init(fac,ctx);
407 fq_nmod_poly_roots(fac, FLINT_beta_mipo, 0, ctx);
408 // root of first (linear) factor: -absolute Term
409 fq_nmod_t r0;
410 fq_nmod_init(r0, ctx);
411 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
412 fq_nmod_neg(r0, r0, ctx);
413 // convert
414 CanonicalForm r1=convertFq_nmod_t2FacCF(r0,alpha,ctx);
415 // cleanup
416 fq_nmod_poly_factor_clear(fac,ctx);
417 fq_nmod_clear(r0, ctx);
418 fq_nmod_poly_clear(FLINT_beta_mipo,ctx);
419 fq_nmod_ctx_clear(ctx);
420 return r1;
421 #elif defined(HAVE_NTL)
422 zz_pX alpha_mipo= convertFacCF2NTLzzpX (mipo);
423 zz_pE::init (alpha_mipo);
424 zz_pEX NTL_beta_mipo= to_zz_pEX (NTL_mipo);
425 zz_pE root= FindRoot (NTL_beta_mipo);
426 return convertNTLzzpE2CF (root, alpha);
427 #endif
428 }
429
430 CanonicalForm
mapDown(const CanonicalForm & F,const CanonicalForm & prim_elem,const CanonicalForm & im_prim_elem,const Variable & alpha,CFList & source,CFList & dest)431 mapDown (const CanonicalForm& F, const CanonicalForm& prim_elem, const
432 CanonicalForm& im_prim_elem, const Variable& alpha, CFList& source,
433 CFList& dest)
434 {
435 return mapUp (F, im_prim_elem, alpha, prim_elem, dest, source);
436 }
437
438 CanonicalForm
mapUp(const CanonicalForm & F,const Variable & alpha,const Variable &,const CanonicalForm & prim_elem,const CanonicalForm & im_prim_elem,CFList & source,CFList & dest)439 mapUp (const CanonicalForm& F, const Variable& alpha, const Variable& /*beta*/,
440 const CanonicalForm& prim_elem, const CanonicalForm& im_prim_elem,
441 CFList& source, CFList& dest)
442 {
443 if (prim_elem == alpha)
444 return F (im_prim_elem, alpha);
445 return mapUp (F, prim_elem, alpha, im_prim_elem, source, dest);
446 }
447
448 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
449 CanonicalForm
mapPrimElem(const CanonicalForm & primElem,const Variable & alpha,const Variable & beta)450 mapPrimElem (const CanonicalForm& primElem, const Variable& alpha,
451 const Variable& beta)
452 {
453 if (primElem == alpha)
454 return mapUp (alpha, beta);
455 else
456 {
457 CanonicalForm primElemMipo= findMinPoly (primElem, alpha);
458 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
459 // convert mipo1
460 nmod_poly_t mipo1;
461 convertFacCF2nmod_poly_t(mipo1,getMipo(beta));
462 fq_nmod_ctx_t ctx;
463 fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
464 nmod_poly_clear(mipo1);
465 // convert mipo2 (primElemMipo)
466 fq_nmod_poly_t mipo2;
467 convertFacCF2Fq_nmod_poly_t(mipo2,primElemMipo,ctx);
468 fq_nmod_poly_factor_t fac;
469 fq_nmod_poly_factor_init(fac,ctx);
470 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
471 // root of first (linear) factor: -absolute Term
472 fq_nmod_t r0;
473 fq_nmod_init(r0, ctx);
474 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
475 fq_nmod_neg(r0, r0, ctx);
476 // convert
477 CanonicalForm r1=convertFq_nmod_t2FacCF(r0,beta,ctx);
478 // cleanup
479 fq_nmod_poly_factor_clear(fac,ctx);
480 fq_nmod_clear(r0, ctx);
481 fq_nmod_poly_clear(mipo2,ctx);
482 fq_nmod_ctx_clear(ctx);
483 return r1;
484 #elif defined(HAVE_NTL)
485 int p= getCharacteristic ();
486 if (fac_NTL_char != p)
487 {
488 fac_NTL_char= p;
489 zz_p::init (p);
490 }
491 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (beta));
492 zz_pE::init (NTLMipo);
493 zz_pEX NTLPrimElemMipo= convertFacCF2NTLzz_pEX (primElemMipo, NTLMipo);
494 zz_pE root= FindRoot (NTLPrimElemMipo);
495 return convertNTLzzpE2CF (root, beta);
496 #else
497 factoryError("NTL/FLINT missing: mapPrimElem");
498 #endif
499 }
500 }
501 #endif
502
503 CanonicalForm
map(const CanonicalForm & primElem,const Variable & alpha,const CanonicalForm & F,const Variable & beta)504 map (const CanonicalForm& primElem, const Variable& alpha,
505 const CanonicalForm& F, const Variable& beta)
506 {
507 CanonicalForm G= F;
508 int order= 0;
509 while (!G.isOne())
510 {
511 G /= primElem;
512 order++;
513 }
514 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
515 // convert mipo
516 nmod_poly_t mipo1;
517 convertFacCF2nmod_poly_t(mipo1,getMipo(beta));
518 fq_nmod_ctx_t ctx;
519 fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
520 nmod_poly_clear(mipo1);
521 // convert mipo2 (alpha)
522 fq_nmod_poly_t mipo2;
523 convertFacCF2Fq_nmod_poly_t(mipo2,getMipo(alpha),ctx);
524 fq_nmod_poly_factor_t fac;
525 fq_nmod_poly_factor_init(fac,ctx);
526 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
527 // roots in fac, #=fac->num
528 int ind=-1;
529 fq_nmod_t r0,FLINTbeta;
530 fq_nmod_init(r0, ctx);
531 fq_nmod_init(FLINTbeta, ctx);
532 convertFacCF2Fq_nmod_t(FLINTbeta,beta,ctx);
533 fmpz_t FLINTorder;
534 fmpz_set_si(FLINTorder,order);
535 for(int i=0;i< fac->num;i++)
536 {
537 // get the root (-abs.term of linear factor)
538 fq_nmod_poly_get_coeff(r0,fac->poly+i,0,ctx);
539 fq_nmod_neg(r0,r0,ctx);
540 // r^order
541 fq_nmod_pow(r0,r0,FLINTorder,ctx);
542 // ==beta?
543 if (fq_nmod_equal(r0,FLINTbeta,ctx))
544 {
545 ind=i;
546 break;
547 }
548 }
549 fmpz_clear(FLINTorder);
550 // convert
551 fq_nmod_poly_get_coeff(r0,fac->poly+ind,0,ctx);
552 fq_nmod_neg(r0,r0,ctx);
553 CanonicalForm r1=convertFq_nmod_t2FacCF(r0,beta,ctx);
554 // cleanup
555 fq_nmod_poly_factor_clear(fac,ctx);
556 fq_nmod_clear(r0, ctx);
557 fq_nmod_clear(FLINTbeta,ctx);
558 fq_nmod_poly_clear(mipo2,ctx);
559 fq_nmod_ctx_clear(ctx);
560 return r1;
561 #elif defined(HAVE_NTL)
562 int p= getCharacteristic ();
563 if (fac_NTL_char != p)
564 {
565 fac_NTL_char= p;
566 zz_p::init (p);
567 }
568 zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
569 zz_pE::init (NTL_mipo);
570 zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
571 zz_pE NTLBeta= to_zz_pE (convertFacCF2NTLzzpX (beta));
572 vec_zz_pE roots= FindRoots (NTL_alpha_mipo);
573 long ind=-1;
574 for (long i= 0; i < roots.length(); i++)
575 {
576 if (power (roots [i], order)== NTLBeta)
577 {
578 ind= i;
579 break;
580 }
581 }
582 return (convertNTLzzpE2CF (roots[ind], beta));
583 #else
584 factoryError("NTL/FLINT missing: map");
585 return CanonicalForm(0);
586 #endif
587 }
588
589 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
590 /*
591 g is in Fp[x]
592 F is in Fp[t]
593 h is in Fp[t]
594 In the finite field Fp[t]/h(t), find g(x) in Fp[x] such that
595 g(F(t)) = 0 mod h(t)
596 i.e. g is the minpoly of the element F(t) of the finite field.
597 */
minpoly(nmod_poly_t g,const nmod_poly_t F,const nmod_poly_t h)598 static void minpoly(nmod_poly_t g, const nmod_poly_t F, const nmod_poly_t h)
599 {
600 slong i;
601 slong d = nmod_poly_degree(h);
602 mp_limb_t p = h->mod.n;
603 nmod_poly_t Fpow;
604 nmod_berlekamp_massey_t bma;
605
606 nmod_poly_init(Fpow, p);
607 nmod_berlekamp_massey_init(bma, p);
608
609 nmod_poly_one(Fpow);
610 for (i = 0; i < 2*d; i++)
611 {
612 nmod_berlekamp_massey_add_point(bma, nmod_poly_get_coeff_ui(Fpow, 0));
613 nmod_poly_mulmod(Fpow, Fpow, F, h);
614 }
615
616 nmod_berlekamp_massey_reduce(bma);
617
618 /* something went horribly wrong if V does not kill the whole sequence */
619 FLINT_ASSERT(nmod_poly_degree(nmod_berlekamp_massey_R_poly(bma)) <
620 nmod_poly_degree(nmod_berlekamp_massey_V_poly(bma)));
621
622 nmod_poly_make_monic(g, nmod_berlekamp_massey_V_poly(bma));
623 #if WANT_ASSERT
624 {
625 nmod_poly_t z;
626 nmod_poly_init(z, p);
627 nmod_poly_compose_mod(z, g, F, h);
628 FLINT_ASSERT(nmod_poly_is_zero(z));
629 nmod_poly_clear(z);
630 }
631 #endif
632 nmod_poly_clear(Fpow);
633 nmod_berlekamp_massey_clear(bma);
634 }
635 #endif
636
637
638 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
639 CanonicalForm
findMinPoly(const CanonicalForm & F,const Variable & alpha)640 findMinPoly (const CanonicalForm& F, const Variable& alpha)
641 {
642 ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)");
643
644 int p=getCharacteristic();
645 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
646 nmod_poly_t FLINT_F,FLINT_alpha,g;
647 nmod_poly_init(g,p);
648 convertFacCF2nmod_poly_t(FLINT_F,F);
649 convertFacCF2nmod_poly_t(FLINT_alpha,getMipo(alpha));
650 minpoly(g,FLINT_F,FLINT_alpha);
651 nmod_poly_clear(FLINT_alpha);
652 nmod_poly_clear(FLINT_F);
653 CanonicalForm res=convertnmod_poly_t2FacCF(g,Variable(1));
654 nmod_poly_clear(g);
655 return res;
656 #elif defined(HAVE_NTL)
657 if (fac_NTL_char != p)
658 {
659 fac_NTL_char= p;
660 zz_p::init (p);
661 }
662 zz_pX NTLF= convertFacCF2NTLzzpX (F);
663 int d= degree (getMipo (alpha));
664
665 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo(alpha));
666 zz_pE::init (NTLMipo);
667 vec_zz_p pows;
668 pows.SetLength (2*d);
669
670 zz_pE powNTLF;
671 set (powNTLF);
672 zz_pE NTLFE= to_zz_pE (NTLF);
673 zz_pX buf;
674 for (int i= 0; i < 2*d; i++)
675 {
676 buf= rep (powNTLF);
677 buf.rep.SetLength (d);
678 pows [i]= buf.rep[0];
679 powNTLF *= NTLFE;
680 }
681
682 zz_pX NTLMinPoly;
683 MinPolySeq (NTLMinPoly, pows, d);
684
685 return convertNTLzzpX2CF (NTLMinPoly, Variable (1));
686 #else
687 factoryError("NTL/FLINT missing: findMinPoly");
688 #endif
689 }
690 #endif
691