My Project
fac_cantzass.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 #include <config.h>
4 
5 #include "factory/cf_gmp.h"
6 
7 #include "assert.h"
8 
9 #include "cf_defs.h"
10 #include "cf_random.h"
11 #include "cf_util.h"
12 #include "fac_cantzass.h"
13 #include "fac_sqrfree.h"
14 #include "gmpext.h"
15 
16 #ifdef HAVE_FLINT
17 #include"FLINTconvert.h"
18 #endif
19 
20 #if !defined(HAVE_NTL)
21 static CanonicalForm randomPoly( int n, const Variable & x, const CFRandom & gen );
22 
23 static CFFList CantorZassenhausFactorFFGF( const CanonicalForm & f, int d, int q, const CFRandom & );
24 
25 static CFFList CantorZassenhausFactorExt( const CanonicalForm & g, int s, mpz_t q, const CFRandom & gen );
26 
27 static CFFList distinctDegreeFactorFFGF ( const CanonicalForm & f, int q );
28 
29 static CFFList distinctDegreeFactorExt ( const CanonicalForm & f, int p, int n );
30 
31 // calculates f^m % d
32 
33 static CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d );
34 
35 // calculates f^(p^s) % d
36 
37 static CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d );
38 
39 // calculates f^((p^s-1)/2) % d
40 
41 static CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d );
42 
43 static CanonicalForm powerMod2( const CanonicalForm & f, mpz_t q, int s, const CanonicalForm & d );
44 
45 CFFList FpFactorizeUnivariateCZ( const CanonicalForm& f, bool issqrfree, int numext, const Variable alpha, const Variable beta )
46 {
47  CFFList F, G, H, HH;
48  CanonicalForm fac;
50  int d, q, n = 0;
51  bool galoisfield = getGFDegree() > 1;
52  mpz_t qq;
53 
54  if ( galoisfield )
56  else
57  q = getCharacteristic();
58  if ( numext > 0 ) {
59  if ( numext == 1 )
60  n = getMipo( alpha ).degree();
61  else
62  n = getMipo( alpha ).degree() * getMipo( beta ).degree();
63  mpz_init( qq );
64  mpz_ui_pow_ui ( qq, q, n );
65  }
66  if ( LC( f ).isOne() )
67  if ( issqrfree )
68  F.append( CFFactor( f, 1 ) );
69  else
70  F = sqrFreeFp( f );
71  else {
72  if ( issqrfree )
73  F.append( CFFactor( f / LC( f ), 1 ) );
74  else
75  F = sqrFreeFp( f / LC( f ) );
76  H.append( LC( f ) );
77  }
78  for ( i = F; i.hasItem(); ++i ) {
79  d = i.getItem().exp();
80  if ( numext > 0 )
81  G = distinctDegreeFactorExt( i.getItem().factor(), q, n );
82  else
83  G = distinctDegreeFactorFFGF( i.getItem().factor(), q );
84  for ( j = G; j.hasItem(); ++j ) {
85  if ( numext > 0 ) {
86  if ( numext == 1 ) {
87  AlgExtRandomF tmpalpha( alpha );
88  HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), qq, tmpalpha );
89  }
90  else {
91  AlgExtRandomF tmpalphabeta( alpha, beta );
92  HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), qq, tmpalphabeta );
93  }
94  }
95  else if ( galoisfield )
96  HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, GFRandom() );
97  else
98  HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, FFRandom() );
99  for ( k = HH; k.hasItem(); ++k ) {
100  fac = k.getItem().factor();
101  H.append( CFFactor( fac / LC( fac ), d ) );
102  }
103  }
104  }
105  if ( numext > 0 )
106  mpz_clear( qq );
107  return H;
108 }
109 
110 CFFList distinctDegreeFactorFFGF ( const CanonicalForm & f, int q )
111 {
112  int i;
113  Variable x = f.mvar();
114  CanonicalForm g = f, h, r = x;
115  CFFList F;
116  i = 1;
117  while ( g.degree(x) > 0 && i <= g.degree(x) ) {
118  r = powerMod( r, q, g );
119  h = gcd( g, r - x );
120  if ( h.degree(x) > 0 ) {
121  F.append( CFFactor( h, i ) );
122  g /= h;
123  }
124  i++;
125  }
126  ASSERT( g.degree(x) == 0, "fatal fatal" );
127  return F;
128 }
129 
130 CFFList distinctDegreeFactorExt ( const CanonicalForm & f, int p, int n )
131 {
132  Variable x = f.mvar();
133  if (f.degree(x) <= 1) return CFFList(CFFactor(f,1));
134  int i;
135  CanonicalForm g = f, h, r = x;
136  CFFList F;
137  i = 1;
138  while ( g.degree(x) > 0 && i <= g.degree(x) ) {
139  r = powerMod( r, p, n, g );
140  h = gcd( g, r - x );
141  if ( h.degree(x) > 0 ) {
142  F.append( CFFactor( h, i ) );
143  g /= h;
144  }
145  i++;
146  }
147  ASSERT( g.degree(x) == 0, "fatal fatal" );
148  return F;
149 }
150 
151 CFFList CantorZassenhausFactorFFGF( const CanonicalForm & g, int s, int q, const CFRandom & gen )
152 {
153  CanonicalForm f = g;
154  CanonicalForm b, f1;
155  int d, d1;
156  Variable x = f.mvar();
157 
158  if ( (d=f.degree(x)) == s )
159  return CFFactor( f, 1 );
160  else while ( 1 ) {
161  b = randomPoly( d, x, gen );
162  f1 = gcd( b, f );
163  if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
164  CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
165  CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
166  return Union( firstFactor, secondFactor );
167  } else {
168  f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
169  if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
170  CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
171  CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
172  return Union( firstFactor, secondFactor );
173  }
174  }
175  }
176 }
177 
178 CFFList CantorZassenhausFactorExt( const CanonicalForm & g, int s, mpz_t q, const CFRandom & gen )
179 {
180  CanonicalForm f = g;
181  CanonicalForm b, f1;
182  int d, d1;
183  Variable x = f.mvar();
184 
185  if ( (d=f.degree(x)) == s )
186  return CFFactor( f, 1 );
187  else while ( 1 ) {
188  b = randomPoly( d, x, gen );
189  f1 = gcd( b, f );
190  if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
191  CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
192  CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
193  return Union( firstFactor, secondFactor );
194  } else {
195  f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
196  if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
197  CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
198  CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
199  return Union( firstFactor, secondFactor );
200  }
201  }
202  }
203 }
204 
205 CanonicalForm randomPoly( int d, const Variable & x, const CFRandom & g )
206 {
207  CanonicalForm result = 0;
208  for ( int i = 0; i < d; i++ )
209  result += power( x, i ) * g.generate();
210  result += power( x, d );
211  return result;
212 }
213 
214 CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d )
215 {
216  CanonicalForm prod = 1;
217  CanonicalForm b = f % d;
218 
219  while ( m != 0 ) {
220  if ( m % 2 != 0 )
221  prod = (prod * b) % d;
222  m /= 2;
223  if ( m != 0 )
224  b = (b * b) % d;
225  }
226  return prod;
227 }
228 
229 CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
230 {
231  CanonicalForm prod = 1;
232  CanonicalForm b = f % d;
233  int odd;
234 
235  mpz_t m;
236 
237  mpz_init( m );
238  mpz_ui_pow_ui ( m, p, s );
239  while ( mpz_cmp_si( m, 0 ) != 0 )
240  {
241  odd = mpz_fdiv_q_ui( m, m, 2 );
242  if ( odd != 0 )
243  prod = (prod * b) % d;
244  if ( mpz_cmp_si( m, 0 ) != 0 )
245  b = (b*b) % d;
246  }
247  mpz_clear( m );
248  return prod;
249 }
250 
251 CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
252 {
253  CanonicalForm prod = 1;
254  CanonicalForm b = f % d;
255  int odd;
256 
257  mpz_t m;
258 
259  mpz_init( m );
260  mpz_ui_pow_ui ( m, p, s );
261  mpz_sub_ui( m, m, 1 );
262  mpz_fdiv_q_ui( m, m, 2 );
263  while ( mpz_cmp_si( m, 0 ) != 0 )
264  {
265  odd = mpz_fdiv_q_ui( m, m, 2 );
266  if ( odd != 0 )
267  prod = (prod * b) % d;
268  if ( mpz_cmp_si( m, 0 ) != 0 )
269  b = (b*b) % d;
270  }
271  mpz_clear( m );
272  return prod;
273 }
274 
275 CanonicalForm powerMod2( const CanonicalForm & f, mpz_t q, int s, const CanonicalForm & d )
276 {
277  CanonicalForm prod = 1;
278  CanonicalForm b = f % d;
279  int odd;
280 
281  mpz_t m;
282 
283  mpz_init( m );
284  mpz_pow_ui( m, q, s );
285  mpz_sub_ui( m, m, 1 );
286  mpz_fdiv_q_ui( m, m, 2 );
287  while ( mpz_cmp_si( m, 0 ) != 0 )
288  {
289  odd = mpz_fdiv_q_ui( m, m, 2 );
290  if ( odd != 0 )
291  prod = (prod * b) % d;
292  if ( mpz_cmp_si( m, 0 ) != 0 )
293  b = (b*b) % d;
294  }
295  mpz_clear( m );
296  return prod;
297 }
298 #endif
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int getGFDegree()
Definition: cf_char.cc:75
List< CFFactor > CFFList
Factor< CanonicalForm > CFFactor
CanonicalForm LC(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4084
int p
Definition: cfModGcd.cc:4080
g
Definition: cfModGcd.cc:4092
CanonicalForm b
Definition: cfModGcd.cc:4105
#define ASSERT(expression, message)
Definition: cf_assert.h:99
factory switches.
generate random integers, random elements of finite fields
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
FILE * f
Definition: checklibs.c:9
generate random elements in F_p(alpha)
Definition: cf_random.h:70
virtual class for random element generation
Definition: cf_random.h:21
factory's main class
Definition: canonicalform.h:86
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
generate random elements in F_p
Definition: cf_random.h:44
generate random elements in GF
Definition: cf_random.h:32
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: factory.h:134
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int s
Definition: facAbsFact.cc:51
Variable beta
Definition: facAbsFact.cc:95
CanonicalForm H
Definition: facAbsFact.cc:60
int j
Definition: facHensel.cc:110
fq_nmod_poly_t prod
Definition: facHensel.cc:100
CFFList FpFactorizeUnivariateCZ(const CanonicalForm &f, bool issqrfree, int numext, const Variable alpha, const Variable beta)
squarefree part and factorization over Q, Q(a)
CFFList sqrFreeFp(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
utility functions for gmp
STATIC_VAR TreeM * G
Definition: janet.cc:31
STATIC_VAR Poly * h
Definition: janet.cc:971
int gcd(int a, int b)
Definition: walkSupport.cc:836