001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010import java.util.Map; 011import java.util.SortedMap; 012import java.util.TreeMap; 013 014import org.apache.logging.log4j.LogManager; 015import org.apache.logging.log4j.Logger; 016 017import edu.jas.poly.AlgebraicNumber; 018import edu.jas.poly.AlgebraicNumberRing; 019import edu.jas.poly.GenPolynomial; 020import edu.jas.poly.GenPolynomialRing; 021import edu.jas.poly.PolyUtil; 022import edu.jas.structure.GcdRingElem; 023import edu.jas.structure.RingFactory; 024 025 026/** 027 * Absolute factorization algorithms class. This class contains implementations 028 * of methods for factorization over algebraically closed fields. The required 029 * field extension is computed along with the factors. The methods have been 030 * tested for prime fields of characteristic zero, that is for 031 * <code>BigRational</code>. It might eventually also be used for prime fields 032 * of non-zero characteristic, that is with <code>ModInteger</code>. The field 033 * extension may yet not be minimal. 034 * @author Heinz Kredel 035 * @param <C> coefficient type 036 */ 037 038public abstract class FactorAbsolute<C extends GcdRingElem<C>> extends FactorAbstract<C> { 039 040 041 private static final Logger logger = LogManager.getLogger(FactorAbsolute.class); 042 043 044 private static final boolean debug = logger.isDebugEnabled(); 045 046 047 /* 048 * Factorization engine for algebraic number coefficients. 049 */ 050 //not possible here because of recursion AN -> Int|Mod -> AN -> ... 051 //public final FactorAbstract<AlgebraicNumber<C>> aengine; 052 053 /** 054 * No argument constructor. <b>Note:</b> can't use this constructor. 055 */ 056 protected FactorAbsolute() { 057 throw new IllegalArgumentException("don't use this constructor"); 058 } 059 060 061 /** 062 * Constructor. 063 * @param cfac coefficient ring factory. 064 */ 065 public FactorAbsolute(RingFactory<C> cfac) { 066 super(cfac); 067 //GenPolynomialRing<C> fac = new GenPolynomialRing<C>(cfac,1); 068 //GenPolynomial<C> p = fac.univariate(0); 069 //AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(p); 070 //aengine = null; //FactorFactory.<C>getImplementation(afac); // hack 071 } 072 073 074 /** 075 * Get the String representation. 076 * @see java.lang.Object#toString() 077 */ 078 @Override 079 public String toString() { 080 return getClass().getName(); 081 } 082 083 084 /** 085 * GenPolynomial test if is absolute irreducible. 086 * @param P GenPolynomial. 087 * @return true if P is absolute irreducible, else false. 088 */ 089 public boolean isAbsoluteIrreducible(GenPolynomial<C> P) { 090 if (!isIrreducible(P)) { 091 return false; 092 } 093 Factors<C> F = factorsAbsoluteIrreducible(P); 094 if (F.afac == null) { 095 return true; 096 } else if (F.afactors.size() > 2) { 097 return false; 098 } else { //F.size() == 2 099 boolean cnst = false; 100 for (GenPolynomial<AlgebraicNumber<C>> p : F.afactors) { 101 if (p.isConstant()) { 102 cnst = true; 103 } 104 } 105 return cnst; 106 } 107 } 108 109 110 /** 111 * GenPolynomial absolute base factorization of a polynomial. 112 * @param P univariate GenPolynomial. 113 * @return factors map container: [p_1 -> e_1, ..., p_k -> e_k] with P 114 * = prod_{i=1,...,k} p_i**e_i. <b>Note:</b> K(alpha) not yet 115 * minimal. 116 */ 117 // @Override 118 public FactorsMap<C> baseFactorsAbsolute(GenPolynomial<C> P) { 119 if (P == null) { 120 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 121 } 122 SortedMap<GenPolynomial<C>, Long> factors = new TreeMap<GenPolynomial<C>, Long>(); 123 if (P.isZERO()) { 124 return new FactorsMap<C>(P, factors); 125 } 126 //System.out.println("\nP_base = " + P); 127 GenPolynomialRing<C> pfac = P.ring; // K[x] 128 if (pfac.nvar > 1) { 129 //System.out.println("\nfacs_base: univ"); 130 throw new IllegalArgumentException("only for univariate polynomials"); 131 } 132 if (!pfac.coFac.isField()) { 133 //System.out.println("\nfacs_base: field"); 134 throw new IllegalArgumentException("only for field coefficients"); 135 } 136 if (P.degree(0) <= 1) { 137 factors.put(P, 1L); 138 return new FactorsMap<C>(P, factors); 139 } 140 // factor over K (=C) 141 SortedMap<GenPolynomial<C>, Long> facs = baseFactors(P); 142 if (debug && !isFactorization(P, facs)) { 143 System.out.println("facs = " + facs); 144 throw new ArithmeticException("isFactorization = false"); 145 } 146 logger.info("all K factors = {}", facs); // Q[X] 147 // factor over some K(alpha) 148 SortedMap<Factors<C>, Long> afactors = new TreeMap<Factors<C>, Long>(); 149 for (Map.Entry<GenPolynomial<C>, Long> me : facs.entrySet()) { 150 GenPolynomial<C> p = me.getKey(); 151 Long e = me.getValue(); //facs.get(p); 152 if (p.degree(0) <= 1) { 153 factors.put(p, e); 154 } else { 155 Factors<C> afacs = baseFactorsAbsoluteIrreducible(p); 156 //System.out.println("afacs = " + afacs); 157 afactors.put(afacs, e); 158 } 159 } 160 //System.out.println("K(alpha) factors = " + factors); 161 return new FactorsMap<C>(P, factors, afactors); 162 } 163 164 165 /** 166 * GenPolynomial absolute base factorization of a squarefree polynomial. 167 * @param P squarefree and primitive univariate GenPolynomial. 168 * @return factors list container: [p_1,...,p_k] with P = prod_{i=1, ..., k} 169 * p_i. <b>Note:</b> K(alpha) not yet minimal. 170 */ 171 // @Override 172 public FactorsList<C> baseFactorsAbsoluteSquarefree(GenPolynomial<C> P) { 173 if (P == null) { 174 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 175 } 176 List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>(); 177 if (P.isZERO()) { 178 return new FactorsList<C>(P, factors); 179 } 180 //System.out.println("\nP_base_sqf = " + P); 181 GenPolynomialRing<C> pfac = P.ring; // K[x] 182 if (pfac.nvar > 1) { 183 //System.out.println("facs_base_sqf: univ"); 184 throw new IllegalArgumentException("only for univariate polynomials"); 185 } 186 if (!pfac.coFac.isField()) { 187 //System.out.println("facs_base_sqf: field"); 188 throw new IllegalArgumentException("only for field coefficients"); 189 } 190 if (P.degree(0) <= 1) { 191 factors.add(P); 192 return new FactorsList<C>(P, factors); 193 } 194 // factor over K (=C) 195 List<GenPolynomial<C>> facs = baseFactorsSquarefree(P); 196 //System.out.println("facs_base_irred = " + facs); 197 if (debug && !isFactorization(P, facs)) { 198 throw new ArithmeticException("isFactorization = false"); 199 } 200 logger.info("all K factors = {}", facs); // Q[X] 201 // factor over K(alpha) 202 List<Factors<C>> afactors = new ArrayList<Factors<C>>(); 203 for (GenPolynomial<C> p : facs) { 204 //System.out.println("facs_base_sqf_p = " + p); 205 if (p.degree(0) <= 1) { 206 factors.add(p); 207 } else { 208 Factors<C> afacs = baseFactorsAbsoluteIrreducible(p); 209 //System.out.println("afacs_base_sqf = " + afacs); 210 logger.info("K(alpha) factors = {}", afacs); // K(alpha)[X] 211 afactors.add(afacs); 212 } 213 } 214 //System.out.println("K(alpha) factors = " + factors); 215 return new FactorsList<C>(P, factors, afactors); 216 } 217 218 219 /** 220 * GenPolynomial base absolute factorization of a irreducible polynomial. 221 * @param P irreducible! univariate GenPolynomial. 222 * @return factors container: [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i 223 * in K(alpha)[x] for suitable alpha and p_i irreducible over L[x], 224 * where K \subset K(alpha) \subset L is an algebraically closed 225 * field over K. <b>Note:</b> K(alpha) not yet minimal. 226 */ 227 public Factors<C> baseFactorsAbsoluteIrreducible(GenPolynomial<C> P) { 228 if (P == null) { 229 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 230 } 231 if (P.isZERO()) { 232 return new Factors<C>(P); 233 } 234 //System.out.println("\nP_base_irred = " + P); 235 GenPolynomialRing<C> pfac = P.ring; // K[x] 236 if (pfac.nvar > 1) { 237 //System.out.println("facs_base_irred: univ"); 238 throw new IllegalArgumentException("only for univariate polynomials"); 239 } 240 if (!pfac.coFac.isField()) { 241 //System.out.println("facs_base_irred: field"); 242 throw new IllegalArgumentException("only for field coefficients"); 243 } 244 if (P.degree(0) <= 1) { 245 return new Factors<C>(P); 246 } 247 // setup field extension K(alpha) where alpha = z_xx 248 //String[] vars = new String[] { "z_" + Math.abs(P.hashCode() % 1000) }; 249 String[] vars = pfac.newVars("z_"); 250 pfac = pfac.copy(); 251 vars = pfac.setVars(vars); 252 GenPolynomial<C> aP = pfac.copy(P); // hack to exchange the variables 253 AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(aP, true); // since irreducible 254 if (logger.isInfoEnabled()) { 255 logger.info("K(alpha) = {}", afac); 256 logger.info("K(alpha) = {}", afac.toScript()); 257 } 258 GenPolynomialRing<AlgebraicNumber<C>> pafac = new GenPolynomialRing<AlgebraicNumber<C>>(afac, 259 aP.ring.nvar, aP.ring.tord, /*old*/vars); 260 // convert to K(alpha) 261 GenPolynomial<AlgebraicNumber<C>> Pa = PolyUtil.<C> convertToAlgebraicCoefficients(pafac, P); 262 logger.info("P over K(alpha) = {}", Pa); 263 // factor over K(alpha) 264 FactorAbstract<AlgebraicNumber<C>> engine = FactorFactory.<C> getImplementation(afac); 265 //System.out.println("K(alpha) engine = " + engine); 266 List<GenPolynomial<AlgebraicNumber<C>>> factors = engine.baseFactorsSquarefree(Pa); 267 //System.out.println("factors = " + factors); 268 logger.info("factors over K(alpha) = {}", factors); 269 List<GenPolynomial<AlgebraicNumber<C>>> faca = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>( 270 factors.size()); 271 List<Factors<AlgebraicNumber<C>>> facar = new ArrayList<Factors<AlgebraicNumber<C>>>(); 272 for (GenPolynomial<AlgebraicNumber<C>> fi : factors) { 273 if (fi.degree(0) <= 1) { 274 faca.add(fi); 275 } else { 276 //System.out.println("fi.deg > 1 = " + fi); 277 FactorAbsolute<AlgebraicNumber<C>> aengine = (FactorAbsolute<AlgebraicNumber<C>>) FactorFactory 278 .<C> getImplementation(afac); 279 Factors<AlgebraicNumber<C>> fif = aengine.baseFactorsAbsoluteIrreducible(fi); 280 //System.out.println("fif = " + fif); 281 facar.add(fif); 282 } 283 } 284 if (facar.size() == 0) { 285 facar = null; 286 } 287 // find minimal field extension K(beta) \subset K(alpha) 288 return new Factors<C>(P, afac, Pa, faca, facar); 289 } 290 291 292 /** 293 * Univariate GenPolynomial algebraic partial fraction decomposition, 294 * Absolute factorization for elementary integration algorithm to linear 295 * factors. 296 * @param A univariate GenPolynomial, deg(A) ≤ deg(P). 297 * @param P univariate squarefree GenPolynomial, gcd(A,P) == 1. 298 * @return partial fraction container. 299 */ 300 public PartialFraction<C> baseAlgebraicPartialFraction(GenPolynomial<C> A, GenPolynomial<C> P) { 301 if (P == null || P.isZERO()) { 302 throw new IllegalArgumentException(" P == null or P == 0"); 303 } 304 if (A == null || A.isZERO()) { 305 throw new IllegalArgumentException(" A == null or A == 0"); 306 // PartialFraction(A,P,al,pl,empty,empty) 307 } 308 //System.out.println("\nP_base_algeb_part = " + P); 309 GenPolynomialRing<C> pfac = P.ring; // K[x] 310 if (pfac.nvar > 1) { 311 //System.out.println("facs_base_irred: univ"); 312 throw new IllegalArgumentException("only for univariate polynomials"); 313 } 314 if (!pfac.coFac.isField()) { 315 //System.out.println("facs_base_irred: field"); 316 throw new IllegalArgumentException("only for field coefficients"); 317 } 318 List<C> cfactors = new ArrayList<C>(); 319 List<GenPolynomial<C>> cdenom = new ArrayList<GenPolynomial<C>>(); 320 List<AlgebraicNumber<C>> afactors = new ArrayList<AlgebraicNumber<C>>(); 321 List<GenPolynomial<AlgebraicNumber<C>>> adenom = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>(); 322 323 // P linear 324 if (P.degree(0) <= 1) { 325 cfactors.add(A.leadingBaseCoefficient()); 326 cdenom.add(P); 327 return new PartialFraction<C>(A, P, cfactors, cdenom, afactors, adenom); 328 } 329 List<GenPolynomial<C>> Pfac = baseFactorsSquarefree(P); 330 //System.out.println("\nPfac = " + Pfac); 331 332 List<GenPolynomial<C>> Afac = engine.basePartialFraction(A, Pfac); 333 334 GenPolynomial<C> A0 = Afac.remove(0); 335 if (!A0.isZERO()) { 336 throw new ArithmeticException(" A0 != 0: deg(A)>= deg(P)"); 337 } 338 339 // algebraic and linear factors 340 int i = 0; 341 for (GenPolynomial<C> pi : Pfac) { 342 GenPolynomial<C> ai = Afac.get(i++); 343 if (pi.degree(0) <= 1) { 344 cfactors.add(ai.leadingBaseCoefficient()); 345 cdenom.add(pi); 346 continue; 347 } 348 PartialFraction<C> pf = baseAlgebraicPartialFractionIrreducibleAbsolute(ai, pi); 349 //PartialFraction<C> pf = baseAlgebraicPartialFractionIrreducible(ai,pi); 350 cfactors.addAll(pf.cfactors); 351 cdenom.addAll(pf.cdenom); 352 afactors.addAll(pf.afactors); 353 adenom.addAll(pf.adenom); 354 } 355 return new PartialFraction<C>(A, P, cfactors, cdenom, afactors, adenom); 356 } 357 358 359 /** 360 * Univariate GenPolynomial algebraic partial fraction decomposition, via 361 * absolute factorization to linear factors. 362 * @param A univariate GenPolynomial, deg(A) < deg(P). 363 * @param P univariate irreducible GenPolynomial, gcd(A,P) == 1. 364 * @return partial fraction container. 365 */ 366 @SuppressWarnings("unchecked") 367 public PartialFraction<C> baseAlgebraicPartialFractionIrreducibleAbsolute(GenPolynomial<C> A, 368 GenPolynomial<C> P) { 369 if (P == null || P.isZERO()) { 370 throw new IllegalArgumentException(" P == null or P == 0"); 371 } 372 //System.out.println("\nP_base_algeb_part = " + P); 373 GenPolynomialRing<C> pfac = P.ring; // K[x] 374 if (pfac.nvar > 1) { 375 //System.out.println("facs_base_irred: univ"); 376 throw new IllegalArgumentException("only for univariate polynomials"); 377 } 378 if (!pfac.coFac.isField()) { 379 //System.out.println("facs_base_irred: field"); 380 throw new IllegalArgumentException("only for field coefficients"); 381 } 382 List<C> cfactors = new ArrayList<C>(); 383 List<GenPolynomial<C>> cdenom = new ArrayList<GenPolynomial<C>>(); 384 List<AlgebraicNumber<C>> afactors = new ArrayList<AlgebraicNumber<C>>(); 385 List<GenPolynomial<AlgebraicNumber<C>>> adenom = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>(); 386 387 // P linear 388 if (P.degree(0) <= 1) { 389 cfactors.add(A.leadingBaseCoefficient()); 390 cdenom.add(P); 391 return new PartialFraction<C>(A, P, cfactors, cdenom, afactors, adenom); 392 } 393 394 // non linear case 395 Factors<C> afacs = factorsAbsoluteIrreducible(P); 396 //System.out.println("linear algebraic factors = " + afacs); 397 //System.out.println("afactors = " + afacs.afactors); 398 //System.out.println("arfactors = " + afacs.arfactors); 399 //System.out.println("arfactors pol = " + afacs.arfactors.get(0).poly); 400 //System.out.println("arfactors2 = " + afacs.arfactors.get(0).afactors); 401 402 List<GenPolynomial<AlgebraicNumber<C>>> fact = afacs.getFactors(); 403 //System.out.println("factors = " + fact); 404 GenPolynomial<AlgebraicNumber<C>> Pa = afacs.apoly; 405 GenPolynomial<AlgebraicNumber<C>> Aa = PolyUtil.<C> convertToRecAlgebraicCoefficients(1, Pa.ring, A); 406 407 GreatestCommonDivisorAbstract<AlgebraicNumber<C>> aengine = GCDFactory.getProxy(afacs.afac); 408 //System.out.println("denom = " + Pa); 409 //System.out.println("number = " + Aa); 410 List<GenPolynomial<AlgebraicNumber<C>>> numbers = aengine.basePartialFraction(Aa, fact); 411 //System.out.println("part frac = " + numbers); 412 GenPolynomial<AlgebraicNumber<C>> A0 = numbers.remove(0); 413 if (!A0.isZERO()) { 414 throw new ArithmeticException(" A0 != 0: deg(A)>= deg(P)"); 415 } 416 int i = 0; 417 for (GenPolynomial<AlgebraicNumber<C>> fa : fact) { 418 GenPolynomial<AlgebraicNumber<C>> an = numbers.get(i++); 419 if (fa.degree(0) <= 1) { 420 afactors.add(an.leadingBaseCoefficient()); 421 adenom.add(fa); 422 continue; 423 } 424 System.out.println("fa = " + fa); 425 Factors<AlgebraicNumber<C>> faf = afacs.getFactor(fa); 426 System.out.println("faf = " + faf); 427 List<GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>>> fafact = faf.getFactors(); 428 GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> Aaa = PolyUtil 429 .<AlgebraicNumber<C>> convertToRecAlgebraicCoefficients(1, faf.apoly.ring, an); 430 431 GreatestCommonDivisorAbstract<AlgebraicNumber<AlgebraicNumber<C>>> aaengine = GCDFactory 432 .getImplementation(faf.afac); 433 434 List<GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>>> anumers = aaengine 435 .basePartialFraction(Aaa, fafact); 436 System.out.println("algeb part frac = " + anumers); 437 GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> A0a = anumers.remove(0); 438 if (!A0a.isZERO()) { 439 throw new ArithmeticException(" A0 != 0: deg(A)>= deg(P)"); 440 } 441 int k = 0; 442 for (GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> faa : fafact) { 443 GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> ana = anumers.get(k++); 444 System.out.println("faa = " + faa); 445 System.out.println("ana = " + ana); 446 if (faa.degree(0) > 1) { 447 throw new ArithmeticException(" faa not linear"); 448 } 449 GenPolynomial<AlgebraicNumber<C>> ana1 = (GenPolynomial<AlgebraicNumber<C>>) (GenPolynomial) ana; 450 GenPolynomial<AlgebraicNumber<C>> faa1 = (GenPolynomial<AlgebraicNumber<C>>) (GenPolynomial) faa; 451 452 afactors.add(ana1.leadingBaseCoefficient()); 453 adenom.add(faa1); 454 } 455 } 456 return new PartialFraction<C>(A, P, cfactors, cdenom, afactors, adenom); 457 } 458 459 460 /** 461 * GenPolynomial absolute factorization of a polynomial. 462 * @param P GenPolynomial. 463 * @return factors map container: [p_1 -> e_1, ..., p_k -> e_k] with P 464 * = prod_{i=1,...,k} p_i**e_i. <b>Note:</b> K(alpha) not yet 465 * minimal. 466 */ 467 public FactorsMap<C> factorsAbsolute(GenPolynomial<C> P) { 468 if (P == null) { 469 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 470 } 471 SortedMap<GenPolynomial<C>, Long> factors = new TreeMap<GenPolynomial<C>, Long>(); 472 if (P.isZERO()) { 473 return new FactorsMap<C>(P, factors); 474 } 475 //System.out.println("\nP_mult = " + P); 476 GenPolynomialRing<C> pfac = P.ring; // K[x] 477 if (pfac.nvar <= 1) { 478 return baseFactorsAbsolute(P); 479 } 480 if (!pfac.coFac.isField()) { 481 throw new IllegalArgumentException("only for field coefficients"); 482 } 483 if (P.degree() <= 1) { 484 factors.put(P, 1L); 485 return new FactorsMap<C>(P, factors); 486 } 487 // factor over K (=C) 488 SortedMap<GenPolynomial<C>, Long> facs = factors(P); 489 if (debug && !isFactorization(P, facs)) { 490 throw new ArithmeticException("isFactorization = false"); 491 } 492 logger.info("all K factors = {}", facs); // Q[X] 493 SortedMap<Factors<C>, Long> afactors = new TreeMap<Factors<C>, Long>(); 494 // factor over K(alpha) 495 for (Map.Entry<GenPolynomial<C>, Long> me : facs.entrySet()) { 496 GenPolynomial<C> p = me.getKey(); 497 Long e = me.getValue(); //facs.get(p); 498 if (p.degree() <= 1) { 499 factors.put(p, e); 500 } else { 501 Factors<C> afacs = factorsAbsoluteIrreducible(p); 502 if (afacs.afac == null) { // absolute irreducible 503 factors.put(p, e); 504 } else { 505 afactors.put(afacs, e); 506 } 507 } 508 } 509 //System.out.println("K(alpha) factors multi = " + factors); 510 return new FactorsMap<C>(P, factors, afactors); 511 } 512 513 514 /** 515 * GenPolynomial absolute factorization of a squarefree polynomial. 516 * @param P squarefree and primitive GenPolynomial. 517 * @return factors list container: [p_1,...,p_k] with P = prod_{i=1, ..., k} 518 * p_i. <b>Note:</b> K(alpha) not yet minimal. 519 */ 520 // @Override 521 public FactorsList<C> factorsAbsoluteSquarefree(GenPolynomial<C> P) { 522 if (P == null) { 523 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 524 } 525 List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>(); 526 if (P.isZERO()) { 527 return new FactorsList<C>(P, factors); 528 } 529 //System.out.println("\nP = " + P); 530 GenPolynomialRing<C> pfac = P.ring; // K[x] 531 if (pfac.nvar <= 1) { 532 return baseFactorsAbsoluteSquarefree(P); 533 } 534 if (!pfac.coFac.isField()) { 535 throw new IllegalArgumentException("only for field coefficients"); 536 } 537 if (P.degree() <= 1) { 538 factors.add(P); 539 return new FactorsList<C>(P, factors); 540 } 541 // factor over K (=C) 542 List<GenPolynomial<C>> facs = factorsSquarefree(P); 543 if (debug && !isFactorization(P, facs)) { 544 throw new ArithmeticException("isFactorization = false"); 545 } 546 logger.info("all K factors = {}", facs); // Q[X] 547 List<Factors<C>> afactors = new ArrayList<Factors<C>>(); 548 // factor over K(alpha) 549 for (GenPolynomial<C> p : facs) { 550 if (p.degree() <= 1) { 551 factors.add(p); 552 } else { 553 Factors<C> afacs = factorsAbsoluteIrreducible(p); 554 if (debug) { 555 logger.info("K(alpha) factors = {}", afacs); // K(alpha)[X] 556 } 557 if (afacs.afac == null) { // absolute irreducible 558 factors.add(p); 559 } else { 560 afactors.add(afacs); 561 } 562 } 563 } 564 //System.out.println("K(alpha) factors = " + factors); 565 return new FactorsList<C>(P, factors, afactors); 566 } 567 568 569 /** 570 * GenPolynomial absolute factorization of a irreducible polynomial. 571 * @param P irreducible! GenPolynomial. 572 * @return factors container: [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i 573 * in K(alpha)[x] for suitable alpha and p_i irreducible over L[x], 574 * where K \subset K(alpha) \subset L is an algebraically closed 575 * field over K. <b>Note:</b> K(alpha) not yet minimal. 576 */ 577 public Factors<C> factorsAbsoluteIrreducible(GenPolynomial<C> P) { 578 if (P == null) { 579 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 580 } 581 if (P.isZERO()) { 582 return new Factors<C>(P); 583 } 584 GenPolynomialRing<C> pfac = P.ring; // K[x] 585 if (pfac.nvar <= 1) { 586 return baseFactorsAbsoluteIrreducible(P); 587 } 588 if (!pfac.coFac.isField()) { 589 throw new IllegalArgumentException("only for field coefficients"); 590 } 591 //List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>(); 592 if (P.degree() <= 1) { 593 return new Factors<C>(P); 594 } 595 // find field extension K(alpha) 596 GenPolynomial<C> up = P; 597 RingFactory<C> cf = pfac.coFac; 598 long cr = cf.characteristic().longValueExact(); // char might be larger 599 if (cr == 0L) { 600 cr = Long.MAX_VALUE; 601 } 602 long rp = 0L; 603 for (int i = 0; i < (pfac.nvar - 1); i++) { 604 rp = 0L; 605 GenPolynomialRing<C> nfac = pfac.contract(1); 606 String[] vn = new String[] { pfac.getVars()[pfac.nvar - 1] }; 607 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(nfac, 1, 608 pfac.tord, vn); 609 GenPolynomial<GenPolynomial<C>> upr = PolyUtil.<C> recursive(rfac, up); 610 //System.out.println("upr = " + upr); 611 GenPolynomial<C> ep; 612 do { 613 if (rp >= cr) { 614 throw new ArithmeticException("elements of prime field exhausted: " + cr); 615 } 616 C r = cf.fromInteger(rp); //cf.random(rp); 617 //System.out.println("r = " + r); 618 ep = PolyUtil.<C> evaluateMainRecursive(nfac, upr, r); 619 //System.out.println("ep = " + ep); 620 rp++; 621 } while (!isSquarefree(ep) /*todo: || ep.degree() <= 1*/); // max deg 622 up = ep; 623 pfac = nfac; 624 } 625 up = up.monic(); 626 if (debug) { 627 logger.info("P({}) = {}", rp, up); 628 //System.out.println("up = " + up); 629 } 630 if (debug && !isSquarefree(up)) { 631 throw new ArithmeticException("not irreducible up = " + up); 632 } 633 if (up.degree(0) <= 1) { 634 return new Factors<C>(P); 635 } 636 // find irreducible factor of up 637 List<GenPolynomial<C>> UF = baseFactorsSquarefree(up); 638 //System.out.println("UF = " + UF); 639 FactorsList<C> aUF = baseFactorsAbsoluteSquarefree(up); 640 //System.out.println("aUF = " + aUF); 641 AlgebraicNumberRing<C> arfac = aUF.findExtensionField(); 642 //System.out.println("arfac = " + arfac); 643 644 long e = up.degree(0); 645 // search factor polynomial with smallest degree 646 for (int i = 0; i < UF.size(); i++) { 647 GenPolynomial<C> upi = UF.get(i); 648 long d = upi.degree(0); 649 if (1 <= d && d <= e) { 650 up = upi; 651 e = up.degree(0); 652 } 653 } 654 if (up.degree(0) <= 1) { 655 return new Factors<C>(P); 656 } 657 if (debug) { 658 logger.info("field extension by {}", up); 659 } 660 661 List<GenPolynomial<AlgebraicNumber<C>>> afactors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>(); 662 663 // setup field extension K(alpha) 664 //String[] vars = new String[] { "z_" + Math.abs(up.hashCode() % 1000) }; 665 String[] vars = pfac.newVars("z_"); 666 pfac = pfac.copy(); 667 //String[] ovars = 668 pfac.setVars(vars); // side effects! 669 //GenPolynomial<C> aup = pfac.copy(up); // hack to exchange the variables 670 //AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(aup,true); // since irreducible 671 AlgebraicNumberRing<C> afac = arfac; 672 int depth = afac.depth(); 673 //System.out.println("afac = " + afac); 674 GenPolynomialRing<AlgebraicNumber<C>> pafac = new GenPolynomialRing<AlgebraicNumber<C>>(afac, 675 P.ring.nvar, P.ring.tord, P.ring.getVars()); 676 //System.out.println("pafac = " + pafac); 677 // convert to K(alpha) 678 GenPolynomial<AlgebraicNumber<C>> Pa = PolyUtil.<C> convertToRecAlgebraicCoefficients(depth, pafac, 679 P); 680 //System.out.println("Pa = " + Pa); 681 // factor over K(alpha) 682 FactorAbstract<AlgebraicNumber<C>> engine = FactorFactory.<C> getImplementation(afac); 683 afactors = engine.factorsSquarefree(Pa); 684 if (debug) { 685 logger.info("K(alpha) factors multi = {}", afactors); 686 } 687 if (afactors.size() <= 1) { 688 return new Factors<C>(P); 689 } 690 // normalize first factor to monic 691 GenPolynomial<AlgebraicNumber<C>> p1 = afactors.get(0); 692 AlgebraicNumber<C> p1c = p1.leadingBaseCoefficient(); 693 if (!p1c.isONE()) { 694 GenPolynomial<AlgebraicNumber<C>> p2 = afactors.get(1); 695 afactors.remove(p1); 696 afactors.remove(p2); 697 p1 = p1.divide(p1c); 698 p2 = p2.multiply(p1c); 699 afactors.add(p1); 700 afactors.add(p2); 701 } 702 // recursion for splitting field 703 // find minimal field extension K(beta) \subset K(alpha) 704 return new Factors<C>(P, afac, Pa, afactors); 705 } 706 707 708 /** 709 * GenPolynomial is absolute factorization. 710 * @param facs factors container. 711 * @return true if P = prod_{i=1,...,r} p_i, else false. 712 */ 713 public boolean isAbsoluteFactorization(Factors<C> facs) { 714 if (facs == null) { 715 throw new IllegalArgumentException("facs may not be null"); 716 } 717 if (facs.afac == null) { 718 return true; 719 } 720 GenPolynomial<AlgebraicNumber<C>> fa = facs.apoly; 721 GenPolynomialRing<AlgebraicNumber<C>> pafac = fa.ring; 722 GenPolynomial<AlgebraicNumber<C>> t = pafac.getONE(); 723 for (GenPolynomial<AlgebraicNumber<C>> f : facs.afactors) { 724 t = t.multiply(f); 725 } 726 //return fa.equals(t) || fa.equals(t.negate()); 727 boolean b = fa.equals(t) || fa.equals(t.negate()); 728 if (b) { 729 return b; 730 } 731 if (facs.arfactors == null) { 732 return false; 733 } 734 for (Factors<AlgebraicNumber<C>> arp : facs.arfactors) { 735 t = t.multiply(arp.poly); 736 } 737 b = fa.equals(t) || fa.equals(t.negate()); 738 if (!b) { 739 System.out.println("\nFactors: " + facs); 740 System.out.println("fa = " + fa); 741 System.out.println("t = " + t); 742 } 743 return b; 744 } 745 746 747 /** 748 * GenPolynomial is absolute factorization. 749 * @param facs factors list container. 750 * @return true if P = prod_{i=1,...,r} p_i, else false. 751 */ 752 public boolean isAbsoluteFactorization(FactorsList<C> facs) { 753 if (facs == null) { 754 throw new IllegalArgumentException("facs may not be null"); 755 } 756 GenPolynomial<C> P = facs.poly; 757 GenPolynomial<C> t = P.ring.getONE(); 758 for (GenPolynomial<C> f : facs.factors) { 759 t = t.multiply(f); 760 } 761 if (P.equals(t) || P.equals(t.negate())) { 762 return true; 763 } 764 if (facs.afactors == null) { 765 return false; 766 } 767 for (Factors<C> fs : facs.afactors) { 768 if (!isAbsoluteFactorization(fs)) { 769 return false; 770 } 771 t = t.multiply(facs.poly); 772 } 773 //return P.equals(t) || P.equals(t.negate()); 774 boolean b = P.equals(t) || P.equals(t.negate()); 775 if (!b) { 776 System.out.println("\nFactorsList: " + facs); 777 System.out.println("P = " + P); 778 System.out.println("t = " + t); 779 } 780 return b; 781 } 782 783 784 /** 785 * GenPolynomial is absolute factorization. 786 * @param facs factors map container. 787 * @return true if P = prod_{i=1,...,k} p_i**e_i , else false. 788 */ 789 public boolean isAbsoluteFactorization(FactorsMap<C> facs) { 790 if (facs == null) { 791 throw new IllegalArgumentException("facs may not be null"); 792 } 793 GenPolynomial<C> P = facs.poly; 794 GenPolynomial<C> t = P.ring.getONE(); 795 for (Map.Entry<GenPolynomial<C>, Long> me : facs.factors.entrySet()) { 796 GenPolynomial<C> f = me.getKey(); 797 long e = me.getValue(); 798 GenPolynomial<C> g = f.power(e); 799 t = t.multiply(g); 800 } 801 if (P.equals(t) || P.equals(t.negate())) { 802 return true; 803 } 804 if (facs.afactors == null) { 805 return false; 806 } 807 for (Map.Entry<Factors<C>, Long> me : facs.afactors.entrySet()) { 808 Factors<C> fs = me.getKey(); 809 if (!isAbsoluteFactorization(fs)) { 810 return false; 811 } 812 long e = me.getValue(); 813 GenPolynomial<C> g = fs.poly.power(e); 814 t = t.multiply(g); 815 } 816 boolean b = P.equals(t) || P.equals(t.negate()); 817 if (!b) { 818 System.out.println("\nFactorsMap: " + facs); 819 System.out.println("P = " + P); 820 System.out.println("t = " + t); 821 } 822 return b; 823 } 824 825}