My Project  debian-1:4.1.1-p2+ds-4
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 static bool
20 {
21  CFFList F = factorize( f );
22  return F.length() == 1 && F.getFirst().exp() == 1;
23 }
24 
26 find_irreducible ( int deg, CFRandom & gen, const Variable & x )
27 {
29  int i;
30  do {
31  result = power( x, deg );
32  for ( i = deg-1; i >= 0; i-- )
33  result += gen.generate() * power( x, i );
34  } while ( ! is_irreducible( result ) );
35  return result;
36 }
37 
38 #ifdef HAVE_NTL
39 /// computes a random monic irreducible univariate polynomial in x over Fp of
40 /// degree i via NTL
42 randomIrredpoly (int i, const Variable & x)
43 {
44  int p= getCharacteristic();
45  if (fac_NTL_char != p)
46  {
47  fac_NTL_char= p;
48  zz_p::init (p);
49  }
50  zz_pX NTLirredpoly;
51  CanonicalForm CFirredpoly;
52  BuildIrred (NTLirredpoly, i);
53  CFirredpoly= convertNTLzzpX2CF (NTLirredpoly, x);
54  return CFirredpoly;
55 }
56 #endif
fac_NTL_char
long fac_NTL_char
Definition: NTLconvert.cc:41
f
FILE * f
Definition: checklibs.c:9
canonicalform.h
x
Variable x
Definition: cfModGcd.cc:4023
result
return result
Definition: facAbsBiFact.cc:76
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
cf_random.h
randomIrredpoly
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL
Definition: cf_irred.cc:42
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm
factory's main class
Definition: canonicalform.h:77
is_irreducible
static bool is_irreducible(const CanonicalForm &f)
Definition: cf_irred.cc:19
i
int i
Definition: cfEzgcd.cc:125
CFRandom
virtual class for random element generation
Definition: cf_random.h:21
cf_defs.h
NTLconvert.h
cf_algorithm.h
find_irreducible
CanonicalForm find_irreducible(int deg, CFRandom &gen, const Variable &x)
generate a random irreducible polynomial in x of degree deg
Definition: cf_irred.cc:26
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
CFRandom::generate
virtual CanonicalForm generate() const
Definition: cf_random.h:24
List::length
int length() const
Definition: ftmpl_list.cc:273
Variable
factory's class for variables
Definition: factory.h:117
cf_assert.h
p
int p
Definition: cfModGcd.cc:4019
List
Definition: ftmpl_list.h:20
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248