64 mpz_ui_pow_ui ( qq, q, n );
66 if (
LC(
f ).isOne() )
78 for (
i = F;
i.hasItem(); ++
i ) {
79 d =
i.getItem().exp();
81 G = distinctDegreeFactorExt(
i.getItem().factor(), q, n );
83 G = distinctDegreeFactorFFGF(
i.getItem().factor(), q );
84 for (
j =
G;
j.hasItem(); ++
j ) {
88 HH = CantorZassenhausFactorExt(
j.getItem().factor(),
j.getItem().exp(), qq, tmpalpha );
92 HH = CantorZassenhausFactorExt(
j.getItem().factor(),
j.getItem().exp(), qq, tmpalphabeta );
95 else if ( galoisfield )
96 HH = CantorZassenhausFactorFFGF(
j.getItem().factor(),
j.getItem().exp(), q,
GFRandom() );
98 HH = CantorZassenhausFactorFFGF(
j.getItem().factor(),
j.getItem().exp(), q,
FFRandom() );
99 for (
k = HH;
k.hasItem(); ++
k ) {
100 fac =
k.getItem().factor();
117 while (
g.degree(
x) > 0 &&
i <=
g.degree(
x) ) {
118 r = powerMod( r, q,
g );
120 if (
h.degree(
x) > 0 ) {
126 ASSERT(
g.degree(
x) == 0,
"fatal fatal" );
138 while (
g.degree(
x) > 0 &&
i <=
g.degree(
x) ) {
139 r = powerMod( r,
p, n,
g );
141 if (
h.degree(
x) > 0 ) {
147 ASSERT(
g.degree(
x) == 0,
"fatal fatal" );
158 if ( (d=
f.degree(
x)) ==
s )
161 b = randomPoly( d,
x, gen );
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 );
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 );
185 if ( (d=
f.degree(
x)) ==
s )
188 b = randomPoly( d,
x, gen );
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 );
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 );
208 for (
int i = 0;
i < d;
i++ )
238 mpz_ui_pow_ui (
m,
p,
s );
239 while ( mpz_cmp_si(
m, 0 ) != 0 )
241 odd = mpz_fdiv_q_ui(
m,
m, 2 );
244 if ( mpz_cmp_si(
m, 0 ) != 0 )
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 )
265 odd = mpz_fdiv_q_ui(
m,
m, 2 );
268 if ( mpz_cmp_si(
m, 0 ) != 0 )
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 )
289 odd = mpz_fdiv_q_ui(
m,
m, 2 );
292 if ( mpz_cmp_si(
m, 0 ) != 0 )
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
#define ASSERT(expression, message)
generate random integers, random elements of finite fields
int ipower(int b, int m)
int ipower ( int b, int m )
generate random elements in F_p(alpha)
virtual class for random element generation
generate random elements in F_p
generate random elements in GF
factory's class for variables
const CanonicalForm int s
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
CanonicalForm getMipo(const Variable &alpha, const Variable &x)