[7bf145] | 1 | /*****************************************************************************\ |
---|
[806c18] | 2 | * Computer Algebra System SINGULAR |
---|
[7bf145] | 3 | \*****************************************************************************/ |
---|
| 4 | /** @file facFqBivar.h |
---|
[806c18] | 5 | * |
---|
[7bf145] | 6 | * This file provides functions for factorizing a bivariate polynomial over |
---|
[806c18] | 7 | * \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF. |
---|
[7bf145] | 8 | * |
---|
| 9 | * @author Martin Lee |
---|
| 10 | * |
---|
| 11 | * @internal @version \$Id$ |
---|
| 12 | * |
---|
| 13 | **/ |
---|
| 14 | /*****************************************************************************/ |
---|
| 15 | |
---|
| 16 | #ifndef FAC_FQ_BIVAR_H |
---|
| 17 | #define FAC_FQ_BIVAR_H |
---|
| 18 | |
---|
| 19 | #include <config.h> |
---|
| 20 | |
---|
| 21 | #include "assert.h" |
---|
| 22 | |
---|
| 23 | #include "facFqBivarUtil.h" |
---|
| 24 | #include "DegreePattern.h" |
---|
| 25 | #include "ExtensionInfo.h" |
---|
| 26 | #include "cf_util.h" |
---|
| 27 | #include "facFqSquarefree.h" |
---|
[f876a66] | 28 | #include "cf_map.h" |
---|
| 29 | #include "cfNewtonPolygon.h" |
---|
[7bf145] | 30 | |
---|
[33c8040] | 31 | static const double log2exp= 1.442695041; |
---|
[fd5b3a] | 32 | |
---|
[806c18] | 33 | /// Factorization of a squarefree bivariate polynomials over an arbitrary finite |
---|
[7bf145] | 34 | /// field, information on the current field we work over is in @a info. @a info |
---|
| 35 | /// may also contain information about the initial field if initial and current |
---|
[806c18] | 36 | /// field do not coincide. In this case the current field is an extension of the |
---|
[7bf145] | 37 | /// initial field and the factors returned are factors of F over the initial |
---|
[806c18] | 38 | /// field. |
---|
| 39 | /// |
---|
[7bf145] | 40 | /// @return @a biFactorize returns a list of factors of F. If F is not monic |
---|
[806c18] | 41 | /// its leading coefficient is not outputted. |
---|
[7bf145] | 42 | /// @sa extBifactorize() |
---|
[806c18] | 43 | CFList |
---|
[7bf145] | 44 | biFactorize (const CanonicalForm& F, ///< [in] a bivariate poly |
---|
| 45 | const ExtensionInfo& info ///< [in] information about extension |
---|
| 46 | ); |
---|
| 47 | |
---|
| 48 | /// factorize a squarefree bivariate polynomial over \f$ F_{p} \f$. |
---|
| 49 | /// |
---|
[806c18] | 50 | /// @return @a FpBiSqrfFactorize returns a list of monic factors, the first |
---|
| 51 | /// element is the leading coefficient. |
---|
[7bf145] | 52 | /// @sa FqBiSqrfFactorize(), GFBiSqrfFactorize() |
---|
[f876a66] | 53 | #ifdef HAVE_NTL |
---|
[7bf145] | 54 | inline |
---|
[f876a66] | 55 | CFList FpBiSqrfFactorize (const CanonicalForm & G ///< [in] a bivariate poly |
---|
[806c18] | 56 | ) |
---|
[7bf145] | 57 | { |
---|
| 58 | ExtensionInfo info= ExtensionInfo (false); |
---|
[f876a66] | 59 | CFMap N; |
---|
| 60 | CanonicalForm F= compress (G, N); |
---|
| 61 | CanonicalForm contentX= content (F, 1); |
---|
| 62 | CanonicalForm contentY= content (F, 2); |
---|
| 63 | F /= (contentX*contentY); |
---|
| 64 | CFFList contentXFactors, contentYFactors; |
---|
| 65 | contentXFactors= factorize (contentX); |
---|
| 66 | contentYFactors= factorize (contentY); |
---|
| 67 | if (contentXFactors.getFirst().factor().inCoeffDomain()) |
---|
| 68 | contentXFactors.removeFirst(); |
---|
| 69 | if (contentYFactors.getFirst().factor().inCoeffDomain()) |
---|
| 70 | contentYFactors.removeFirst(); |
---|
| 71 | if (F.inCoeffDomain()) |
---|
| 72 | { |
---|
| 73 | CFList result; |
---|
| 74 | for (CFFListIterator i= contentXFactors; i.hasItem(); i++) |
---|
| 75 | result.append (N (i.getItem().factor())); |
---|
| 76 | for (CFFListIterator i= contentYFactors; i.hasItem(); i++) |
---|
| 77 | result.append (N (i.getItem().factor())); |
---|
| 78 | normalize (result); |
---|
| 79 | result.insert (Lc (G)); |
---|
| 80 | return result; |
---|
| 81 | } |
---|
| 82 | mat_ZZ M; |
---|
| 83 | vec_ZZ S; |
---|
| 84 | F= compress (F, M, S); |
---|
[7bf145] | 85 | CFList result= biFactorize (F, info); |
---|
[f876a66] | 86 | for (CFListIterator i= result; i.hasItem(); i++) |
---|
| 87 | i.getItem()= N (decompress (i.getItem(), M, S)); |
---|
| 88 | for (CFFListIterator i= contentXFactors; i.hasItem(); i++) |
---|
| 89 | result.append (N(i.getItem().factor())); |
---|
| 90 | for (CFFListIterator i= contentYFactors; i.hasItem(); i++) |
---|
| 91 | result.append (N (i.getItem().factor())); |
---|
| 92 | normalize (result); |
---|
| 93 | result.insert (Lc(G)); |
---|
[7bf145] | 94 | return result; |
---|
| 95 | } |
---|
| 96 | |
---|
| 97 | /// factorize a squarefree bivariate polynomial over \f$ F_{p}(\alpha ) \f$. |
---|
| 98 | /// |
---|
[806c18] | 99 | /// @return @a FqBiSqrfFactorize returns a list of monic factors, the first |
---|
| 100 | /// element is the leading coefficient. |
---|
[7bf145] | 101 | /// @sa FpBiSqrfFactorize(), GFBiSqrfFactorize() |
---|
| 102 | inline |
---|
[f876a66] | 103 | CFList FqBiSqrfFactorize (const CanonicalForm & G, ///< [in] a bivariate poly |
---|
[7bf145] | 104 | const Variable& alpha ///< [in] algebraic variable |
---|
[806c18] | 105 | ) |
---|
[7bf145] | 106 | { |
---|
| 107 | ExtensionInfo info= ExtensionInfo (alpha, false); |
---|
[f876a66] | 108 | CFMap N; |
---|
| 109 | CanonicalForm F= compress (G, N); |
---|
| 110 | CanonicalForm contentX= content (F, 1); |
---|
| 111 | CanonicalForm contentY= content (F, 2); |
---|
| 112 | F /= (contentX*contentY); |
---|
| 113 | CFFList contentXFactors, contentYFactors; |
---|
| 114 | contentXFactors= factorize (contentX); |
---|
| 115 | contentYFactors= factorize (contentY); |
---|
| 116 | if (contentXFactors.getFirst().factor().inCoeffDomain()) |
---|
| 117 | contentXFactors.removeFirst(); |
---|
| 118 | if (contentYFactors.getFirst().factor().inCoeffDomain()) |
---|
| 119 | contentYFactors.removeFirst(); |
---|
| 120 | if (F.inCoeffDomain()) |
---|
| 121 | { |
---|
| 122 | CFList result; |
---|
| 123 | for (CFFListIterator i= contentXFactors; i.hasItem(); i++) |
---|
| 124 | result.append (N (i.getItem().factor())); |
---|
| 125 | for (CFFListIterator i= contentYFactors; i.hasItem(); i++) |
---|
| 126 | result.append (N (i.getItem().factor())); |
---|
| 127 | normalize (result); |
---|
| 128 | result.insert (Lc (G)); |
---|
| 129 | return result; |
---|
| 130 | } |
---|
| 131 | mat_ZZ M; |
---|
| 132 | vec_ZZ S; |
---|
| 133 | F= compress (F, M, S); |
---|
[7bf145] | 134 | CFList result= biFactorize (F, info); |
---|
[f876a66] | 135 | for (CFListIterator i= result; i.hasItem(); i++) |
---|
| 136 | i.getItem()= N (decompress (i.getItem(), M, S)); |
---|
| 137 | for (CFFListIterator i= contentXFactors; i.hasItem(); i++) |
---|
| 138 | result.append (N(i.getItem().factor())); |
---|
| 139 | for (CFFListIterator i= contentYFactors; i.hasItem(); i++) |
---|
| 140 | result.append (N (i.getItem().factor())); |
---|
| 141 | normalize (result); |
---|
| 142 | result.insert (Lc(G)); |
---|
[7bf145] | 143 | return result; |
---|
| 144 | } |
---|
| 145 | |
---|
| 146 | /// factorize a squarefree bivariate polynomial over GF |
---|
| 147 | /// |
---|
[806c18] | 148 | /// @return @a GFBiSqrfFactorize returns a list of monic factors, the first |
---|
| 149 | /// element is the leading coefficient. |
---|
| 150 | /// @sa FpBiSqrfFactorize(), FqBiSqrfFactorize() |
---|
[7bf145] | 151 | inline |
---|
[f876a66] | 152 | CFList GFBiSqrfFactorize (const CanonicalForm & G ///< [in] a bivariate poly |
---|
[806c18] | 153 | ) |
---|
[7bf145] | 154 | { |
---|
[806c18] | 155 | ASSERT (CFFactory::gettype() == GaloisFieldDomain, |
---|
[7bf145] | 156 | "GF as base field expected"); |
---|
| 157 | ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false); |
---|
[f876a66] | 158 | CFMap N; |
---|
| 159 | CanonicalForm F= compress (G, N); |
---|
| 160 | CanonicalForm contentX= content (F, 1); |
---|
| 161 | CanonicalForm contentY= content (F, 2); |
---|
| 162 | F /= (contentX*contentY); |
---|
| 163 | CFList contentXFactors, contentYFactors; |
---|
| 164 | contentXFactors= biFactorize (contentX, info); |
---|
| 165 | contentYFactors= biFactorize (contentY, info); |
---|
| 166 | if (contentXFactors.getFirst().inCoeffDomain()) |
---|
| 167 | contentXFactors.removeFirst(); |
---|
| 168 | if (contentYFactors.getFirst().inCoeffDomain()) |
---|
| 169 | contentYFactors.removeFirst(); |
---|
| 170 | if (F.inCoeffDomain()) |
---|
| 171 | { |
---|
| 172 | CFList result; |
---|
| 173 | for (CFListIterator i= contentXFactors; i.hasItem(); i++) |
---|
| 174 | result.append (N (i.getItem())); |
---|
| 175 | for (CFListIterator i= contentYFactors; i.hasItem(); i++) |
---|
| 176 | result.append (N (i.getItem())); |
---|
| 177 | normalize (result); |
---|
| 178 | result.insert (Lc (G)); |
---|
| 179 | return result; |
---|
| 180 | } |
---|
| 181 | mat_ZZ M; |
---|
| 182 | vec_ZZ S; |
---|
| 183 | F= compress (F, M, S); |
---|
[7bf145] | 184 | CFList result= biFactorize (F, info); |
---|
[f876a66] | 185 | for (CFListIterator i= result; i.hasItem(); i++) |
---|
| 186 | i.getItem()= N (decompress (i.getItem(), M, S)); |
---|
| 187 | for (CFListIterator i= contentXFactors; i.hasItem(); i++) |
---|
| 188 | result.append (N(i.getItem())); |
---|
| 189 | for (CFListIterator i= contentYFactors; i.hasItem(); i++) |
---|
| 190 | result.append (N (i.getItem())); |
---|
| 191 | normalize (result); |
---|
| 192 | result.insert (Lc(G)); |
---|
[7bf145] | 193 | return result; |
---|
| 194 | } |
---|
| 195 | |
---|
| 196 | /// factorize a bivariate polynomial over \f$ F_{p} \f$ |
---|
| 197 | /// |
---|
[806c18] | 198 | /// @return @a FpBiFactorize returns a list of monic factors with |
---|
| 199 | /// multiplicity, the first element is the leading coefficient. |
---|
| 200 | /// @sa FqBiFactorize(), GFBiFactorize() |
---|
[7bf145] | 201 | inline |
---|
[f876a66] | 202 | CFFList FpBiFactorize (const CanonicalForm & G ///< [in] a bivariate poly |
---|
[806c18] | 203 | ) |
---|
[7bf145] | 204 | { |
---|
| 205 | ExtensionInfo info= ExtensionInfo (false); |
---|
[f876a66] | 206 | CFMap N; |
---|
| 207 | CanonicalForm F= compress (G, N); |
---|
[806c18] | 208 | CanonicalForm LcF= Lc (F); |
---|
[f876a66] | 209 | CanonicalForm contentX= content (F, 1); |
---|
| 210 | CanonicalForm contentY= content (F, 2); |
---|
| 211 | F /= (contentX*contentY); |
---|
| 212 | CFFList contentXFactors, contentYFactors; |
---|
| 213 | contentXFactors= factorize (contentX); |
---|
| 214 | contentYFactors= factorize (contentY); |
---|
| 215 | if (contentXFactors.getFirst().factor().inCoeffDomain()) |
---|
| 216 | contentXFactors.removeFirst(); |
---|
| 217 | if (contentYFactors.getFirst().factor().inCoeffDomain()) |
---|
| 218 | contentYFactors.removeFirst(); |
---|
| 219 | decompress (contentXFactors, N); |
---|
| 220 | decompress (contentYFactors, N); |
---|
| 221 | CFFList result, resultRoot; |
---|
| 222 | if (F.inCoeffDomain()) |
---|
| 223 | { |
---|
| 224 | result= Union (contentXFactors, contentYFactors); |
---|
| 225 | normalize (result); |
---|
| 226 | result.insert (CFFactor (LcF, 1)); |
---|
| 227 | return result; |
---|
| 228 | } |
---|
| 229 | mat_ZZ M; |
---|
| 230 | vec_ZZ S; |
---|
| 231 | F= compress (F, M, S); |
---|
[7bf145] | 232 | CanonicalForm pthRoot, A; |
---|
| 233 | CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, info.getAlpha()); |
---|
| 234 | CFList buf, bufRoot; |
---|
| 235 | int p= getCharacteristic(); |
---|
| 236 | int l; |
---|
| 237 | if (degree (pthRoot) > 0) |
---|
| 238 | { |
---|
| 239 | pthRoot= maxpthRoot (pthRoot, p, l); |
---|
| 240 | result= FpBiFactorize (pthRoot); |
---|
| 241 | result.removeFirst(); |
---|
| 242 | for (CFFListIterator i= result; i.hasItem(); i++) |
---|
[f876a66] | 243 | i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)), |
---|
| 244 | i.getItem().exp()*ipower (p,l)); |
---|
| 245 | result= Union (result, contentXFactors); |
---|
| 246 | result= Union (result, contentYFactors); |
---|
| 247 | normalize (result); |
---|
[7bf145] | 248 | result.insert (CFFactor (LcF, 1)); |
---|
| 249 | return result; |
---|
| 250 | } |
---|
| 251 | else |
---|
[806c18] | 252 | { |
---|
[7bf145] | 253 | buf= biFactorize (sqrfP, info); |
---|
| 254 | A= F/LcF; |
---|
| 255 | result= multiplicity (A, buf); |
---|
[f876a66] | 256 | for (CFFListIterator i= result; i.hasItem(); i++) |
---|
| 257 | i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)), |
---|
| 258 | i.getItem().exp()); |
---|
[7bf145] | 259 | } |
---|
| 260 | if (degree (A) > 0) |
---|
| 261 | { |
---|
| 262 | resultRoot= FpBiFactorize (A); |
---|
| 263 | resultRoot.removeFirst(); |
---|
[f876a66] | 264 | for (CFFListIterator i= resultRoot; i.hasItem(); i++) |
---|
| 265 | i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)), |
---|
| 266 | i.getItem().exp()); |
---|
[7bf145] | 267 | result= Union (result, resultRoot); |
---|
| 268 | } |
---|
[f876a66] | 269 | result= Union (result, contentXFactors); |
---|
| 270 | result= Union (result, contentYFactors); |
---|
| 271 | normalize (result); |
---|
[7bf145] | 272 | result.insert (CFFactor (LcF, 1)); |
---|
| 273 | return result; |
---|
| 274 | } |
---|
| 275 | |
---|
| 276 | /// factorize a bivariate polynomial over \f$ F_{p}(\alpha ) \f$ |
---|
| 277 | /// |
---|
[806c18] | 278 | /// @return @a FqBiFactorize returns a list of monic factors with |
---|
| 279 | /// multiplicity, the first element is the leading coefficient. |
---|
| 280 | /// @sa FpBiFactorize(), FqBiFactorize() |
---|
[7bf145] | 281 | inline |
---|
[f876a66] | 282 | CFFList FqBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly |
---|
[7bf145] | 283 | const Variable & alpha ///< [in] algebraic variable |
---|
| 284 | ) |
---|
| 285 | { |
---|
| 286 | ExtensionInfo info= ExtensionInfo (alpha, false); |
---|
[f876a66] | 287 | CFMap N; |
---|
| 288 | CanonicalForm F= compress (G, N); |
---|
[806c18] | 289 | CanonicalForm LcF= Lc (F); |
---|
[f876a66] | 290 | CanonicalForm contentX= content (F, 1); |
---|
| 291 | CanonicalForm contentY= content (F, 2); |
---|
| 292 | F /= (contentX*contentY); |
---|
| 293 | CFFList contentXFactors, contentYFactors; |
---|
| 294 | contentXFactors= factorize (contentX); |
---|
| 295 | contentYFactors= factorize (contentY); |
---|
| 296 | if (contentXFactors.getFirst().factor().inCoeffDomain()) |
---|
| 297 | contentXFactors.removeFirst(); |
---|
| 298 | if (contentYFactors.getFirst().factor().inCoeffDomain()) |
---|
| 299 | contentYFactors.removeFirst(); |
---|
| 300 | decompress (contentXFactors, N); |
---|
| 301 | decompress (contentYFactors, N); |
---|
| 302 | CFFList result, resultRoot; |
---|
| 303 | if (F.inCoeffDomain()) |
---|
| 304 | { |
---|
| 305 | result= Union (contentXFactors, contentYFactors); |
---|
| 306 | normalize (result); |
---|
| 307 | result.insert (CFFactor (LcF, 1)); |
---|
| 308 | return result; |
---|
| 309 | } |
---|
| 310 | mat_ZZ M; |
---|
| 311 | vec_ZZ S; |
---|
| 312 | CanonicalForm oldF= F; |
---|
| 313 | F= compress (F, M, S); |
---|
| 314 | CanonicalForm pthRoot, A, tmp; |
---|
[7bf145] | 315 | CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, alpha); |
---|
| 316 | CFList buf, bufRoot; |
---|
| 317 | int p= getCharacteristic(); |
---|
| 318 | int q= ipower (p, degree (getMipo (alpha))); |
---|
| 319 | int l; |
---|
| 320 | if (degree (pthRoot) > 0) |
---|
| 321 | { |
---|
| 322 | pthRoot= maxpthRoot (pthRoot, q, l); |
---|
| 323 | result= FqBiFactorize (pthRoot, alpha); |
---|
| 324 | result.removeFirst(); |
---|
| 325 | for (CFFListIterator i= result; i.hasItem(); i++) |
---|
[f876a66] | 326 | i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)), |
---|
| 327 | i.getItem().exp()*ipower (p,l)); |
---|
| 328 | result= Union (result, contentXFactors); |
---|
| 329 | result= Union (result, contentYFactors); |
---|
| 330 | normalize (result); |
---|
[7bf145] | 331 | result.insert (CFFactor (LcF, 1)); |
---|
| 332 | return result; |
---|
| 333 | } |
---|
| 334 | else |
---|
[806c18] | 335 | { |
---|
[7bf145] | 336 | buf= biFactorize (sqrfP, info); |
---|
| 337 | A= F/LcF; |
---|
| 338 | result= multiplicity (A, buf); |
---|
[f876a66] | 339 | for (CFFListIterator i= result; i.hasItem(); i++) |
---|
| 340 | i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)), |
---|
| 341 | i.getItem().exp()); |
---|
[7bf145] | 342 | } |
---|
| 343 | if (degree (A) > 0) |
---|
| 344 | { |
---|
| 345 | resultRoot= FqBiFactorize (A, alpha); |
---|
| 346 | resultRoot.removeFirst(); |
---|
[f876a66] | 347 | for (CFFListIterator i= resultRoot; i.hasItem(); i++) |
---|
| 348 | i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)), |
---|
| 349 | i.getItem().exp()); |
---|
[7bf145] | 350 | result= Union (result, resultRoot); |
---|
| 351 | } |
---|
[f876a66] | 352 | result= Union (result, contentXFactors); |
---|
| 353 | result= Union (result, contentYFactors); |
---|
| 354 | normalize (result); |
---|
[7bf145] | 355 | result.insert (CFFactor (LcF, 1)); |
---|
| 356 | return result; |
---|
| 357 | } |
---|
| 358 | |
---|
| 359 | /// factorize a bivariate polynomial over GF |
---|
[806c18] | 360 | /// |
---|
| 361 | /// @return @a GFBiFactorize returns a list of monic factors with |
---|
| 362 | /// multiplicity, the first element is the leading coefficient. |
---|
| 363 | /// @sa FpBiFactorize(), FqBiFactorize() |
---|
[7bf145] | 364 | inline |
---|
[f876a66] | 365 | CFFList GFBiFactorize (const CanonicalForm & G ///< [in] a bivariate poly |
---|
[806c18] | 366 | ) |
---|
[7bf145] | 367 | { |
---|
[806c18] | 368 | ASSERT (CFFactory::gettype() == GaloisFieldDomain, |
---|
[7bf145] | 369 | "GF as base field expected"); |
---|
| 370 | ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false); |
---|
[f876a66] | 371 | CFMap N; |
---|
| 372 | CanonicalForm F= compress (G, N); |
---|
[7bf145] | 373 | CanonicalForm LcF= Lc (F); |
---|
[f876a66] | 374 | CanonicalForm contentX= content (F, 1); |
---|
| 375 | CanonicalForm contentY= content (F, 2); |
---|
| 376 | F /= (contentX*contentY); |
---|
| 377 | CFFList contentXFactors, contentYFactors; |
---|
| 378 | contentXFactors= factorize (contentX); |
---|
| 379 | contentYFactors= factorize (contentY); |
---|
| 380 | if (contentXFactors.getFirst().factor().inCoeffDomain()) |
---|
| 381 | contentXFactors.removeFirst(); |
---|
| 382 | if (contentYFactors.getFirst().factor().inCoeffDomain()) |
---|
| 383 | contentYFactors.removeFirst(); |
---|
| 384 | decompress (contentXFactors, N); |
---|
| 385 | decompress (contentYFactors, N); |
---|
| 386 | CFFList result, resultRoot; |
---|
| 387 | if (F.inCoeffDomain()) |
---|
| 388 | { |
---|
| 389 | result= Union (contentXFactors, contentYFactors); |
---|
| 390 | normalize (result); |
---|
| 391 | result.insert (CFFactor (LcF, 1)); |
---|
| 392 | return result; |
---|
| 393 | } |
---|
| 394 | mat_ZZ M; |
---|
| 395 | vec_ZZ S; |
---|
| 396 | F= compress (F, M, S); |
---|
[7bf145] | 397 | CanonicalForm pthRoot, A; |
---|
| 398 | CanonicalForm sqrfP= sqrfPart (F/LcF, pthRoot, info.getAlpha()); |
---|
| 399 | CFList buf; |
---|
| 400 | int p= getCharacteristic(); |
---|
| 401 | int q= ipower (p, getGFDegree()); |
---|
| 402 | int l; |
---|
| 403 | if (degree (pthRoot) > 0) |
---|
| 404 | { |
---|
| 405 | pthRoot= maxpthRoot (pthRoot, q, l); |
---|
| 406 | result= GFBiFactorize (pthRoot); |
---|
| 407 | result.removeFirst(); |
---|
| 408 | for (CFFListIterator i= result; i.hasItem(); i++) |
---|
[f876a66] | 409 | i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)), |
---|
| 410 | i.getItem().exp()*ipower (p,l)); |
---|
| 411 | result= Union (result, contentXFactors); |
---|
| 412 | result= Union (result, contentYFactors); |
---|
| 413 | normalize (result); |
---|
[7bf145] | 414 | result.insert (CFFactor (LcF, 1)); |
---|
| 415 | return result; |
---|
| 416 | } |
---|
| 417 | else |
---|
| 418 | { |
---|
| 419 | buf= biFactorize (sqrfP, info); |
---|
| 420 | A= F/LcF; |
---|
| 421 | result= multiplicity (A, buf); |
---|
[f876a66] | 422 | for (CFFListIterator i= result; i.hasItem(); i++) |
---|
| 423 | i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)), |
---|
| 424 | i.getItem().exp()); |
---|
[7bf145] | 425 | } |
---|
| 426 | if (degree (A) > 0) |
---|
| 427 | { |
---|
| 428 | resultRoot= GFBiFactorize (A); |
---|
| 429 | resultRoot.removeFirst(); |
---|
[f876a66] | 430 | for (CFFListIterator i= resultRoot; i.hasItem(); i++) |
---|
| 431 | i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)), |
---|
| 432 | i.getItem().exp()); |
---|
[7bf145] | 433 | result= Union (result, resultRoot); |
---|
| 434 | } |
---|
[f876a66] | 435 | result= Union (result, contentXFactors); |
---|
| 436 | result= Union (result, contentYFactors); |
---|
| 437 | normalize (result); |
---|
[7bf145] | 438 | result.insert (CFFactor (LcF, 1)); |
---|
| 439 | return result; |
---|
| 440 | } |
---|
| 441 | |
---|
[f876a66] | 442 | #endif |
---|
| 443 | |
---|
[7bf145] | 444 | /// \f$ \prod_{f\in L} {f (0, x)} \ mod\ M \f$ via divide-and-conquer |
---|
| 445 | /// |
---|
| 446 | /// @return @a prodMod0 computes the above defined product |
---|
| 447 | /// @sa prodMod() |
---|
[806c18] | 448 | CanonicalForm prodMod0 (const CFList& L, ///< [in] a list of compressed, |
---|
[7bf145] | 449 | ///< bivariate polynomials |
---|
| 450 | const CanonicalForm& M ///< [in] a power of Variable (2) |
---|
| 451 | ); |
---|
| 452 | |
---|
[806c18] | 453 | /// find an evaluation point p, s.t. F(p,y) is squarefree and |
---|
| 454 | /// \f$ deg_{y} (F(p,y))= deg_{y} (F(x,y)) \f$. |
---|
[7bf145] | 455 | /// |
---|
| 456 | /// @return @a evalPoint returns an evaluation point, which is valid if and only |
---|
| 457 | /// if fail == false. |
---|
[806c18] | 458 | CanonicalForm |
---|
| 459 | evalPoint (const CanonicalForm& F, ///< [in] compressed, bivariate poly |
---|
[7bf145] | 460 | CanonicalForm & eval, ///< [in,out] F (p, y) |
---|
| 461 | const Variable& alpha, ///< [in] algebraic variable |
---|
| 462 | CFList& list, ///< [in] list of points already considered |
---|
| 463 | const bool& GF, ///< [in] GaloisFieldDomain? |
---|
| 464 | bool& fail ///< [in,out] equals true, if there is no |
---|
[806c18] | 465 | ///< valid evaluation point |
---|
[7bf145] | 466 | ); |
---|
| 467 | |
---|
| 468 | /// Univariate factorization of squarefree monic polys over finite fields via |
---|
[806c18] | 469 | /// NTL. If the characteristic is even special GF2 routines of NTL are used. |
---|
[7bf145] | 470 | /// |
---|
| 471 | /// @return @a uniFactorizer returns a list of monic factors |
---|
[5f4463] | 472 | CFList |
---|
[7bf145] | 473 | uniFactorizer (const CanonicalForm& A, ///< [in] squarefree univariate poly |
---|
| 474 | const Variable& alpha, ///< [in] algebraic variable |
---|
[806c18] | 475 | const bool& GF ///< [in] GaloisFieldDomain? |
---|
[7bf145] | 476 | ); |
---|
| 477 | |
---|
[806c18] | 478 | /// naive factor recombination over an extension of the initial field. |
---|
[7bf145] | 479 | /// Uses precomputed data to exclude combinations that are not possible. |
---|
| 480 | /// |
---|
| 481 | /// @return @a extFactorRecombination returns a list of factors over the initial |
---|
[806c18] | 482 | /// field, whose shift to zero is reversed. |
---|
| 483 | /// @sa factorRecombination(), extEarlyFactorDetection() |
---|
[368602a] | 484 | CFList |
---|
[7bf145] | 485 | extFactorRecombination ( |
---|
[c1b9927] | 486 | CFList& factors, ///< [in,out] list of lifted factors that are |
---|
[11bf82] | 487 | ///< monic wrt Variable (1), |
---|
| 488 | ///< original factors-factors found |
---|
| 489 | CanonicalForm& F, ///< [in,out] poly to be factored, |
---|
| 490 | ///< F/factors found |
---|
| 491 | const CanonicalForm& M, ///< [in] Variable (2)^liftBound |
---|
[c1b9927] | 492 | const ExtensionInfo& info,///< [in] contains information about |
---|
[11bf82] | 493 | ///< extension |
---|
| 494 | DegreePattern& degs, |
---|
| 495 | const CanonicalForm& eval,///< [in] evaluation point |
---|
| 496 | int s, ///< [in] algorithm starts checking subsets |
---|
| 497 | ///< of size s |
---|
| 498 | int thres ///< [in] threshold for the size of subsets |
---|
| 499 | ///< which are checked, for a full factor |
---|
[c1b9927] | 500 | ///< recombination choose |
---|
[11bf82] | 501 | ///< thres= factors.length()/2 |
---|
[7bf145] | 502 | ); |
---|
| 503 | |
---|
[806c18] | 504 | /// naive factor recombination. |
---|
[7bf145] | 505 | /// Uses precomputed data to exclude combinations that are not possible. |
---|
| 506 | /// |
---|
| 507 | /// @return @a factorRecombination returns a list of factors of F. |
---|
| 508 | /// @sa extFactorRecombination(), earlyFactorDetectection() |
---|
[368602a] | 509 | CFList |
---|
[7bf145] | 510 | factorRecombination ( |
---|
[11bf82] | 511 | CFList& factors, ///< [in,out] list of lifted factors |
---|
| 512 | ///< that are monic wrt Variable (1) |
---|
| 513 | CanonicalForm& F, ///< [in,out] poly to be factored |
---|
| 514 | const CanonicalForm& M,///< [in] Variable (2)^liftBound |
---|
| 515 | DegreePattern& degs, ///< [in] degree pattern |
---|
| 516 | int s, ///< [in] algorithm starts checking |
---|
| 517 | ///< subsets of size s |
---|
| 518 | int thres ///< [in] threshold for the size of |
---|
| 519 | ///< subsets which are checked, for a |
---|
[c1b9927] | 520 | ///< full factor recombination choose |
---|
[11bf82] | 521 | ///< thres= factors.length()/2 |
---|
[7bf145] | 522 | ); |
---|
| 523 | |
---|
| 524 | /// chooses a field extension. |
---|
| 525 | /// |
---|
| 526 | /// @return @a chooseExtension returns an extension specified by @a beta of |
---|
| 527 | /// appropiate size |
---|
| 528 | Variable chooseExtension ( |
---|
[11bf82] | 529 | const Variable & alpha, ///< [in] some algebraic variable |
---|
| 530 | const Variable & beta, ///< [in] some algebraic variable |
---|
| 531 | int k ///< [in] some int |
---|
[7bf145] | 532 | ); |
---|
| 533 | |
---|
| 534 | /// detects factors of @a F at stage @a deg of Hensel lifting. |
---|
| 535 | /// No combinations of more than one factor are tested. Lift bound and possible |
---|
[806c18] | 536 | /// degree pattern are updated. |
---|
| 537 | /// |
---|
[7bf145] | 538 | /// @return @a earlyFactorDetection returns a list of factors of F (possibly in- |
---|
| 539 | /// complete), in case of success. Otherwise an empty list. |
---|
| 540 | /// @sa factorRecombination(), extEarlyFactorDetection() |
---|
[368602a] | 541 | CFList |
---|
[7bf145] | 542 | earlyFactorDetection ( |
---|
| 543 | CanonicalForm& F, ///< [in,out] poly to be factored, returns |
---|
| 544 | ///< poly divided by detected factors in case |
---|
| 545 | ///< of success |
---|
[806c18] | 546 | CFList& factors, ///< [in,out] list of factors lifted up to |
---|
[7bf145] | 547 | ///< @a deg, returns a list of factors |
---|
| 548 | ///< without detected factors |
---|
[806c18] | 549 | int& adaptedLiftBound, ///< [in,out] adapted lift bound |
---|
[7bf145] | 550 | DegreePattern& degs, ///< [in,out] degree pattern, is updated |
---|
| 551 | ///< whenever we find a factor |
---|
| 552 | bool& success, ///< [in,out] indicating success |
---|
| 553 | int deg ///< [in] stage of Hensel lifting |
---|
| 554 | ); |
---|
| 555 | |
---|
| 556 | /// detects factors of @a F at stage @a deg of Hensel lifting. |
---|
| 557 | /// No combinations of more than one factor are tested. Lift bound and possible |
---|
[806c18] | 558 | /// degree pattern are updated. |
---|
| 559 | /// |
---|
| 560 | /// @return @a extEarlyFactorDetection returns a list of factors of F (possibly |
---|
[7bf145] | 561 | /// incomplete), whose shift to zero is reversed, in case of success. |
---|
| 562 | /// Otherwise an empty list. |
---|
| 563 | /// @sa factorRecombination(), earlyFactorDetection() |
---|
[368602a] | 564 | CFList |
---|
[7bf145] | 565 | extEarlyFactorDetection ( |
---|
[806c18] | 566 | CanonicalForm& F, ///< [in,out] poly to be factored, returns |
---|
| 567 | ///< poly divided by detected factors in case |
---|
[7bf145] | 568 | ///< of success |
---|
[806c18] | 569 | CFList& factors, ///< [in,out] list of factors lifted up to |
---|
[7bf145] | 570 | ///< @a deg, returns a list of factors |
---|
| 571 | ///< without detected factors |
---|
| 572 | int& adaptedLiftBound, ///< [in,out] adapted lift bound |
---|
| 573 | DegreePattern& degs, ///< [in,out] degree pattern, is updated |
---|
| 574 | ///< whenever we find a factor |
---|
| 575 | bool& success, ///< [in,out] indicating success |
---|
| 576 | const ExtensionInfo& info, ///< [in] information about extension |
---|
| 577 | const CanonicalForm& eval, ///< [in] evaluation point |
---|
| 578 | int deg ///< [in] stage of Hensel lifting |
---|
| 579 | ); |
---|
| 580 | |
---|
[806c18] | 581 | /// hensel Lifting and early factor detection |
---|
[7bf145] | 582 | /// |
---|
[806c18] | 583 | /// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted |
---|
[7bf145] | 584 | /// factors without factors which have been detected at an early stage |
---|
| 585 | /// of Hensel lifting |
---|
[806c18] | 586 | /// @sa earlyFactorDetection(), extEarlyFactorDetection() |
---|
[7bf145] | 587 | |
---|
[368602a] | 588 | CFList |
---|
[7bf145] | 589 | henselLiftAndEarly ( |
---|
[806c18] | 590 | CanonicalForm& A, ///< [in,out] poly to be factored, |
---|
| 591 | ///< returns poly divided by detected factors |
---|
[7bf145] | 592 | ///< in case of success |
---|
| 593 | bool& earlySuccess, ///< [in,out] indicating success |
---|
| 594 | CFList& earlyFactors, ///< [in,out] list of factors detected |
---|
[806c18] | 595 | ///< at early stage of Hensel lifting |
---|
| 596 | DegreePattern& degs, ///< [in,out] degree pattern |
---|
[7bf145] | 597 | int& liftBound, ///< [in,out] (adapted) lift bound |
---|
| 598 | const CFList& uniFactors, ///< [in] univariate factors |
---|
| 599 | const ExtensionInfo& info, ///< [in] information about extension |
---|
| 600 | const CanonicalForm& eval ///< [in] evaluation point |
---|
| 601 | ); |
---|
| 602 | |
---|
| 603 | /// Factorization over an extension of initial field |
---|
| 604 | /// |
---|
| 605 | /// @return @a extBiFactorize returns factorization of F over initial field |
---|
| 606 | /// @sa biFactorize() |
---|
[368602a] | 607 | CFList |
---|
[806c18] | 608 | extBiFactorize (const CanonicalForm& F, ///< [in] poly to be factored |
---|
| 609 | const ExtensionInfo& info ///< [in] info about extension |
---|
[7bf145] | 610 | ); |
---|
| 611 | |
---|
| 612 | |
---|
| 613 | #endif |
---|
| 614 | /* FAC_FQ_BIVAR_H */ |
---|
| 615 | |
---|