My Project
cf_irred.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 
4 #include "config.h"
5 
6 
7 #include "cf_assert.h"
8 
9 #include "cf_defs.h"
10 #include "canonicalform.h"
11 #include "cf_algorithm.h"
12 #include "cf_random.h"
13 
14 #ifdef HAVE_NTL
15 #include "NTLconvert.h"
16 #endif
17 
18 #ifdef HAVE_FLINT
19 #include "FLINTconvert.h"
20 #endif
21 
22 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
23 /// computes a random monic irreducible univariate polynomial in x over Fp of
24 /// degree i via NTL/FLINT
26 randomIrredpoly (int i, const Variable & x)
27 {
28  int p= getCharacteristic();
29  #ifdef HAVE_FLINT
30  nmod_poly_t Irredpoly;
31  nmod_poly_init(Irredpoly,p);
32  nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, i+1);
33  CanonicalForm CFirredpoly=convertnmod_poly_t2FacCF(Irredpoly,x);
34  nmod_poly_clear(Irredpoly);
35  #elif defined(HAVE_NTL)
36  if (fac_NTL_char != p)
37  {
38  fac_NTL_char= p;
39  zz_p::init (p);
40  }
41  zz_pX NTLirredpoly;
42  BuildIrred (NTLirredpoly, i);
43  CanonicalForm CFirredpoly= convertNTLzzpX2CF (NTLirredpoly, x);
44  #else
45  factoryError("NTL/FLINT missing: randomIrredpoly");
46  #endif
47  return CFirredpoly;
48 }
49 #else
50 static bool
51 is_irreducible ( const CanonicalForm & f )
52 {
53  CFFList F = factorize( f );
54  return F.length() == 1 && F.getFirst().exp() == 1;
55 }
56 
58 find_irreducible ( int deg, CFRandom & gen, const Variable & x )
59 {
61  int i;
62  do {
63  result = power( x, deg );
64  for ( i = deg-1; i >= 0; i-- )
65  result += gen.generate() * power( x, i );
66  } while ( ! is_irreducible( result ) );
67  return result;
68 }
69 #endif
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
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.
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
assertions for Factory
factory switches.
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition: cf_irred.cc:26
CanonicalForm find_irreducible(int deg, CFRandom &gen, const Variable &x)
generate a random irreducible polynomial in x of degree deg
GLOBAL_VAR flint_rand_t FLINTrandom
Definition: cf_random.cc:25
generate random integers, random elements of finite fields
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
FILE * f
Definition: checklibs.c:9
virtual class for random element generation
Definition: cf_random.h:21
virtual CanonicalForm generate() const
Definition: cf_random.h:24
factory's main class
Definition: canonicalform.h:86
T getFirst() const
Definition: ftmpl_list.cc:279
int length() const
Definition: ftmpl_list.cc:273
factory's class for variables
Definition: factory.h:127
return result
Definition: facAbsBiFact.cc:75
nmod_poly_init(FLINTmipo, getCharacteristic())
nmod_poly_clear(FLINTmipo)
void init()
Definition: lintree.cc:864