My Project
Loading...
Searching...
No Matches
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)
21static CanonicalForm randomPoly( int n, const Variable & x, const CFRandom & gen );
22
23static CFFList CantorZassenhausFactorFFGF( const CanonicalForm & f, int d, int q, const CFRandom & );
24
25static CFFList CantorZassenhausFactorExt( const CanonicalForm & g, int s, mpz_t q, const CFRandom & gen );
26
27static CFFList distinctDegreeFactorFFGF ( const CanonicalForm & f, int q );
28
29static CFFList distinctDegreeFactorExt ( const CanonicalForm & f, int p, int n );
30
31// calculates f^m % d
32
33static CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d );
34
35// calculates f^(p^s) % d
36
37static CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d );
38
39// calculates f^((p^s-1)/2) % d
40
41static CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d );
42
43static CanonicalForm powerMod2( const CanonicalForm & f, mpz_t q, int s, const CanonicalForm & d );
44
45CFFList 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
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
110CFFList 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
130CFFList 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
151CFFList 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
178CFFList 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
205CanonicalForm randomPoly( int d, const Variable & x, const CFRandom & g )
206{
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
214CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d )
215{
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
229CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
230{
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
251CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
252{
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
275CanonicalForm powerMod2( const CanonicalForm & f, mpz_t q, int s, const CanonicalForm & d )
276{
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:4082
int p
Definition: cfModGcd.cc:4078
g
Definition: cfModGcd.cc:4090
CanonicalForm b
Definition: cfModGcd.cc:4103
#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: variable.h:33
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)
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
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int gcd(int a, int b)
Definition: walkSupport.cc:836