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 | static bool |
---|
23 | is_irreducible ( const CanonicalForm & f ) |
---|
24 | { |
---|
25 | CFFList F = factorize( f ); |
---|
26 | return F.length() == 1 && F.getFirst().exp() == 1; |
---|
27 | } |
---|
28 | |
---|
29 | #if defined(HAVE_NTL) || defined(HAVE_FLINT) |
---|
30 | /// computes a random monic irreducible univariate polynomial in x over Fp of |
---|
31 | /// degree i via NTL/FLINT |
---|
32 | CanonicalForm |
---|
33 | randomIrredpoly (int i, const Variable & x) |
---|
34 | { |
---|
35 | int p= getCharacteristic(); |
---|
36 | #ifdef HAVE_FLINT |
---|
37 | nmod_poly_t Irredpoly; |
---|
38 | nmod_poly_init(Irredpoly,p); |
---|
39 | nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, i+1); |
---|
40 | CanonicalForm CFirredpoly=convertnmod_poly_t2FacCF(Irredpoly,Variable(1)); |
---|
41 | nmod_poly_clear(Irredpoly); |
---|
42 | #elif defined(HAVE_NTL) |
---|
43 | if (fac_NTL_char != p) |
---|
44 | { |
---|
45 | fac_NTL_char= p; |
---|
46 | zz_p::init (p); |
---|
47 | } |
---|
48 | zz_pX NTLirredpoly; |
---|
49 | BuildIrred (NTLirredpoly, i); |
---|
50 | CanonicalForm CFirredpoly= convertNTLzzpX2CF (NTLirredpoly, x); |
---|
51 | #endif |
---|
52 | return CFirredpoly; |
---|
53 | } |
---|
54 | #else |
---|
55 | CanonicalForm |
---|
56 | find_irreducible ( int deg, CFRandom & gen, const Variable & x ) |
---|
57 | { |
---|
58 | CanonicalForm result; |
---|
59 | int i; |
---|
60 | do { |
---|
61 | result = power( x, deg ); |
---|
62 | for ( i = deg-1; i >= 0; i-- ) |
---|
63 | result += gen.generate() * power( x, i ); |
---|
64 | } while ( ! is_irreducible( result ) ); |
---|
65 | return result; |
---|
66 | } |
---|
67 | #endif |
---|