001/* 002 * $Id: FactorAbsolute.java 5997 2020-03-17 15:34:31Z kredel $ 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 if (logger.isInfoEnabled()) { 147 logger.info("all K factors = " + facs); // Q[X] 148 //System.out.println("\nall K factors = " + facs); // Q[X] 149 } 150 // factor over some K(alpha) 151 SortedMap<Factors<C>, Long> afactors = new TreeMap<Factors<C>, Long>(); 152 for (Map.Entry<GenPolynomial<C>, Long> me : facs.entrySet()) { 153 GenPolynomial<C> p = me.getKey(); 154 Long e = me.getValue(); //facs.get(p); 155 if (p.degree(0) <= 1) { 156 factors.put(p, e); 157 } else { 158 Factors<C> afacs = baseFactorsAbsoluteIrreducible(p); 159 //System.out.println("afacs = " + afacs); 160 afactors.put(afacs, e); 161 } 162 } 163 //System.out.println("K(alpha) factors = " + factors); 164 return new FactorsMap<C>(P, factors, afactors); 165 } 166 167 168 /** 169 * GenPolynomial absolute base factorization of a squarefree polynomial. 170 * @param P squarefree and primitive univariate GenPolynomial. 171 * @return factors list container: [p_1,...,p_k] with P = prod_{i=1, ..., k} 172 * p_i. <b>Note:</b> K(alpha) not yet minimal. 173 */ 174 // @Override 175 public FactorsList<C> baseFactorsAbsoluteSquarefree(GenPolynomial<C> P) { 176 if (P == null) { 177 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 178 } 179 List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>(); 180 if (P.isZERO()) { 181 return new FactorsList<C>(P, factors); 182 } 183 //System.out.println("\nP_base_sqf = " + P); 184 GenPolynomialRing<C> pfac = P.ring; // K[x] 185 if (pfac.nvar > 1) { 186 //System.out.println("facs_base_sqf: univ"); 187 throw new IllegalArgumentException("only for univariate polynomials"); 188 } 189 if (!pfac.coFac.isField()) { 190 //System.out.println("facs_base_sqf: field"); 191 throw new IllegalArgumentException("only for field coefficients"); 192 } 193 if (P.degree(0) <= 1) { 194 factors.add(P); 195 return new FactorsList<C>(P, factors); 196 } 197 // factor over K (=C) 198 List<GenPolynomial<C>> facs = baseFactorsSquarefree(P); 199 //System.out.println("facs_base_irred = " + facs); 200 if (debug && !isFactorization(P, facs)) { 201 throw new ArithmeticException("isFactorization = false"); 202 } 203 if (logger.isInfoEnabled()) { 204 logger.info("all K factors = " + facs); // Q[X] 205 //System.out.println("\nall K factors = " + facs); // Q[X] 206 } 207 // factor over K(alpha) 208 List<Factors<C>> afactors = new ArrayList<Factors<C>>(); 209 for (GenPolynomial<C> p : facs) { 210 //System.out.println("facs_base_sqf_p = " + p); 211 if (p.degree(0) <= 1) { 212 factors.add(p); 213 } else { 214 Factors<C> afacs = baseFactorsAbsoluteIrreducible(p); 215 //System.out.println("afacs_base_sqf = " + afacs); 216 if (logger.isInfoEnabled()) { 217 logger.info("K(alpha) factors = " + afacs); // K(alpha)[X] 218 } 219 afactors.add(afacs); 220 } 221 } 222 //System.out.println("K(alpha) factors = " + factors); 223 return new FactorsList<C>(P, factors, afactors); 224 } 225 226 227 /** 228 * GenPolynomial base absolute factorization of a irreducible polynomial. 229 * @param P irreducible! univariate GenPolynomial. 230 * @return factors container: [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i 231 * in K(alpha)[x] for suitable alpha and p_i irreducible over L[x], 232 * where K \subset K(alpha) \subset L is an algebraically closed 233 * field over K. <b>Note:</b> K(alpha) not yet minimal. 234 */ 235 public Factors<C> baseFactorsAbsoluteIrreducible(GenPolynomial<C> P) { 236 if (P == null) { 237 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 238 } 239 if (P.isZERO()) { 240 return new Factors<C>(P); 241 } 242 //System.out.println("\nP_base_irred = " + P); 243 GenPolynomialRing<C> pfac = P.ring; // K[x] 244 if (pfac.nvar > 1) { 245 //System.out.println("facs_base_irred: univ"); 246 throw new IllegalArgumentException("only for univariate polynomials"); 247 } 248 if (!pfac.coFac.isField()) { 249 //System.out.println("facs_base_irred: field"); 250 throw new IllegalArgumentException("only for field coefficients"); 251 } 252 if (P.degree(0) <= 1) { 253 return new Factors<C>(P); 254 } 255 // setup field extension K(alpha) where alpha = z_xx 256 //String[] vars = new String[] { "z_" + Math.abs(P.hashCode() % 1000) }; 257 String[] vars = pfac.newVars("z_"); 258 pfac = pfac.copy(); 259 vars = pfac.setVars(vars); 260 GenPolynomial<C> aP = pfac.copy(P); // hack to exchange the variables 261 AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(aP, true); // since irreducible 262 if (logger.isInfoEnabled()) { 263 logger.info("K(alpha) = " + afac); 264 logger.info("K(alpha) = " + afac.toScript()); 265 //System.out.println("K(alpha) = " + afac); 266 } 267 GenPolynomialRing<AlgebraicNumber<C>> pafac = new GenPolynomialRing<AlgebraicNumber<C>>(afac, 268 aP.ring.nvar, aP.ring.tord, /*old*/vars); 269 // convert to K(alpha) 270 GenPolynomial<AlgebraicNumber<C>> Pa = PolyUtil.<C> convertToAlgebraicCoefficients(pafac, P); 271 if (logger.isInfoEnabled()) { 272 logger.info("P over K(alpha) = " + Pa); 273 //logger.info("P over K(alpha) = " + Pa.toScript()); 274 //System.out.println("P in K(alpha) = " + Pa); 275 } 276 // factor over K(alpha) 277 FactorAbstract<AlgebraicNumber<C>> engine = FactorFactory.<C> getImplementation(afac); 278 //System.out.println("K(alpha) engine = " + engine); 279 List<GenPolynomial<AlgebraicNumber<C>>> factors = engine.baseFactorsSquarefree(Pa); 280 //System.out.println("factors = " + factors); 281 if (logger.isInfoEnabled()) { 282 logger.info("factors over K(alpha) = " + factors); 283 //System.out.println("factors over K(alpha) = " + factors); 284 } 285 List<GenPolynomial<AlgebraicNumber<C>>> faca = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>( 286 factors.size()); 287 List<Factors<AlgebraicNumber<C>>> facar = new ArrayList<Factors<AlgebraicNumber<C>>>(); 288 for (GenPolynomial<AlgebraicNumber<C>> fi : factors) { 289 if (fi.degree(0) <= 1) { 290 faca.add(fi); 291 } else { 292 //System.out.println("fi.deg > 1 = " + fi); 293 FactorAbsolute<AlgebraicNumber<C>> aengine = (FactorAbsolute<AlgebraicNumber<C>>) FactorFactory 294 .<C> getImplementation(afac); 295 Factors<AlgebraicNumber<C>> fif = aengine.baseFactorsAbsoluteIrreducible(fi); 296 //System.out.println("fif = " + fif); 297 facar.add(fif); 298 } 299 } 300 if (facar.size() == 0) { 301 facar = null; 302 } 303 // find minimal field extension K(beta) \subset K(alpha) 304 return new Factors<C>(P, afac, Pa, faca, facar); 305 } 306 307 308 /** 309 * Univariate GenPolynomial algebraic partial fraction decomposition, 310 * Absolute factorization for elementary integration algorithm to linear 311 * factors. 312 * @param A univariate GenPolynomial, deg(A) < deg(P). 313 * @param P univariate squarefree GenPolynomial, gcd(A,P) == 1. 314 * @return partial fraction container. 315 */ 316 public PartialFraction<C> baseAlgebraicPartialFraction(GenPolynomial<C> A, GenPolynomial<C> P) { 317 if (P == null || P.isZERO()) { 318 throw new IllegalArgumentException(" P == null or P == 0"); 319 } 320 if (A == null || A.isZERO()) { 321 throw new IllegalArgumentException(" A == null or A == 0"); 322 // PartialFraction(A,P,al,pl,empty,empty) 323 } 324 //System.out.println("\nP_base_algeb_part = " + P); 325 GenPolynomialRing<C> pfac = P.ring; // K[x] 326 if (pfac.nvar > 1) { 327 //System.out.println("facs_base_irred: univ"); 328 throw new IllegalArgumentException("only for univariate polynomials"); 329 } 330 if (!pfac.coFac.isField()) { 331 //System.out.println("facs_base_irred: field"); 332 throw new IllegalArgumentException("only for field coefficients"); 333 } 334 List<C> cfactors = new ArrayList<C>(); 335 List<GenPolynomial<C>> cdenom = new ArrayList<GenPolynomial<C>>(); 336 List<AlgebraicNumber<C>> afactors = new ArrayList<AlgebraicNumber<C>>(); 337 List<GenPolynomial<AlgebraicNumber<C>>> adenom = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>(); 338 339 // P linear 340 if (P.degree(0) <= 1) { 341 cfactors.add(A.leadingBaseCoefficient()); 342 cdenom.add(P); 343 return new PartialFraction<C>(A, P, cfactors, cdenom, afactors, adenom); 344 } 345 List<GenPolynomial<C>> Pfac = baseFactorsSquarefree(P); 346 //System.out.println("\nPfac = " + Pfac); 347 348 List<GenPolynomial<C>> Afac = engine.basePartialFraction(A, Pfac); 349 350 GenPolynomial<C> A0 = Afac.remove(0); 351 if (!A0.isZERO()) { 352 throw new ArithmeticException(" A0 != 0: deg(A)>= deg(P)"); 353 } 354 355 // algebraic and linear factors 356 int i = 0; 357 for (GenPolynomial<C> pi : Pfac) { 358 GenPolynomial<C> ai = Afac.get(i++); 359 if (pi.degree(0) <= 1) { 360 cfactors.add(ai.leadingBaseCoefficient()); 361 cdenom.add(pi); 362 continue; 363 } 364 PartialFraction<C> pf = baseAlgebraicPartialFractionIrreducibleAbsolute(ai, pi); 365 //PartialFraction<C> pf = baseAlgebraicPartialFractionIrreducible(ai,pi); 366 cfactors.addAll(pf.cfactors); 367 cdenom.addAll(pf.cdenom); 368 afactors.addAll(pf.afactors); 369 adenom.addAll(pf.adenom); 370 } 371 return new PartialFraction<C>(A, P, cfactors, cdenom, afactors, adenom); 372 } 373 374 375 /** 376 * Univariate GenPolynomial algebraic partial fraction decomposition, via 377 * absolute factorization to linear factors. 378 * @param A univariate GenPolynomial, deg(A) < deg(P). 379 * @param P univariate irreducible GenPolynomial, gcd(A,P) == 1. 380 * @return partial fraction container. 381 */ 382 @SuppressWarnings("unchecked") 383 public PartialFraction<C> baseAlgebraicPartialFractionIrreducibleAbsolute(GenPolynomial<C> A, 384 GenPolynomial<C> P) { 385 if (P == null || P.isZERO()) { 386 throw new IllegalArgumentException(" P == null or P == 0"); 387 } 388 //System.out.println("\nP_base_algeb_part = " + P); 389 GenPolynomialRing<C> pfac = P.ring; // K[x] 390 if (pfac.nvar > 1) { 391 //System.out.println("facs_base_irred: univ"); 392 throw new IllegalArgumentException("only for univariate polynomials"); 393 } 394 if (!pfac.coFac.isField()) { 395 //System.out.println("facs_base_irred: field"); 396 throw new IllegalArgumentException("only for field coefficients"); 397 } 398 List<C> cfactors = new ArrayList<C>(); 399 List<GenPolynomial<C>> cdenom = new ArrayList<GenPolynomial<C>>(); 400 List<AlgebraicNumber<C>> afactors = new ArrayList<AlgebraicNumber<C>>(); 401 List<GenPolynomial<AlgebraicNumber<C>>> adenom = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>(); 402 403 // P linear 404 if (P.degree(0) <= 1) { 405 cfactors.add(A.leadingBaseCoefficient()); 406 cdenom.add(P); 407 return new PartialFraction<C>(A, P, cfactors, cdenom, afactors, adenom); 408 } 409 410 // non linear case 411 Factors<C> afacs = factorsAbsoluteIrreducible(P); 412 //System.out.println("linear algebraic factors = " + afacs); 413 //System.out.println("afactors = " + afacs.afactors); 414 //System.out.println("arfactors = " + afacs.arfactors); 415 //System.out.println("arfactors pol = " + afacs.arfactors.get(0).poly); 416 //System.out.println("arfactors2 = " + afacs.arfactors.get(0).afactors); 417 418 List<GenPolynomial<AlgebraicNumber<C>>> fact = afacs.getFactors(); 419 //System.out.println("factors = " + fact); 420 GenPolynomial<AlgebraicNumber<C>> Pa = afacs.apoly; 421 GenPolynomial<AlgebraicNumber<C>> Aa = PolyUtil.<C> convertToRecAlgebraicCoefficients(1, Pa.ring, A); 422 423 GreatestCommonDivisorAbstract<AlgebraicNumber<C>> aengine = GCDFactory.getProxy(afacs.afac); 424 //System.out.println("denom = " + Pa); 425 //System.out.println("numer = " + Aa); 426 List<GenPolynomial<AlgebraicNumber<C>>> numers = aengine.basePartialFraction(Aa, fact); 427 //System.out.println("part frac = " + numers); 428 GenPolynomial<AlgebraicNumber<C>> A0 = numers.remove(0); 429 if (!A0.isZERO()) { 430 throw new ArithmeticException(" A0 != 0: deg(A)>= deg(P)"); 431 } 432 int i = 0; 433 for (GenPolynomial<AlgebraicNumber<C>> fa : fact) { 434 GenPolynomial<AlgebraicNumber<C>> an = numers.get(i++); 435 if (fa.degree(0) <= 1) { 436 afactors.add(an.leadingBaseCoefficient()); 437 adenom.add(fa); 438 continue; 439 } 440 System.out.println("fa = " + fa); 441 Factors<AlgebraicNumber<C>> faf = afacs.getFactor(fa); 442 System.out.println("faf = " + faf); 443 List<GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>>> fafact = faf.getFactors(); 444 GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> Aaa = PolyUtil 445 .<AlgebraicNumber<C>> convertToRecAlgebraicCoefficients(1, faf.apoly.ring, an); 446 447 GreatestCommonDivisorAbstract<AlgebraicNumber<AlgebraicNumber<C>>> aaengine = GCDFactory 448 .getImplementation(faf.afac); 449 450 List<GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>>> anumers = aaengine 451 .basePartialFraction(Aaa, fafact); 452 System.out.println("algeb part frac = " + anumers); 453 GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> A0a = anumers.remove(0); 454 if (!A0a.isZERO()) { 455 throw new ArithmeticException(" A0 != 0: deg(A)>= deg(P)"); 456 } 457 int k = 0; 458 for (GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> faa : fafact) { 459 GenPolynomial<AlgebraicNumber<AlgebraicNumber<C>>> ana = anumers.get(k++); 460 System.out.println("faa = " + faa); 461 System.out.println("ana = " + ana); 462 if (faa.degree(0) > 1) { 463 throw new ArithmeticException(" faa not linear"); 464 } 465 GenPolynomial<AlgebraicNumber<C>> ana1 = (GenPolynomial<AlgebraicNumber<C>>) (GenPolynomial) ana; 466 GenPolynomial<AlgebraicNumber<C>> faa1 = (GenPolynomial<AlgebraicNumber<C>>) (GenPolynomial) faa; 467 468 afactors.add(ana1.leadingBaseCoefficient()); 469 adenom.add(faa1); 470 } 471 } 472 return new PartialFraction<C>(A, P, cfactors, cdenom, afactors, adenom); 473 } 474 475 476 /** 477 * GenPolynomial absolute factorization of a polynomial. 478 * @param P GenPolynomial. 479 * @return factors map container: [p_1 -> e_1, ..., p_k -> e_k] with P 480 * = prod_{i=1,...,k} p_i**e_i. <b>Note:</b> K(alpha) not yet 481 * minimal. 482 */ 483 public FactorsMap<C> factorsAbsolute(GenPolynomial<C> P) { 484 if (P == null) { 485 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 486 } 487 SortedMap<GenPolynomial<C>, Long> factors = new TreeMap<GenPolynomial<C>, Long>(); 488 if (P.isZERO()) { 489 return new FactorsMap<C>(P, factors); 490 } 491 //System.out.println("\nP_mult = " + P); 492 GenPolynomialRing<C> pfac = P.ring; // K[x] 493 if (pfac.nvar <= 1) { 494 return baseFactorsAbsolute(P); 495 } 496 if (!pfac.coFac.isField()) { 497 throw new IllegalArgumentException("only for field coefficients"); 498 } 499 if (P.degree() <= 1) { 500 factors.put(P, 1L); 501 return new FactorsMap<C>(P, factors); 502 } 503 // factor over K (=C) 504 SortedMap<GenPolynomial<C>, Long> facs = factors(P); 505 if (debug && !isFactorization(P, facs)) { 506 throw new ArithmeticException("isFactorization = false"); 507 } 508 if (logger.isInfoEnabled()) { 509 logger.info("all K factors = " + facs); // Q[X] 510 //System.out.println("\nall K factors = " + facs); // Q[X] 511 } 512 SortedMap<Factors<C>, Long> afactors = new TreeMap<Factors<C>, Long>(); 513 // factor over K(alpha) 514 for (Map.Entry<GenPolynomial<C>, Long> me : facs.entrySet()) { 515 GenPolynomial<C> p = me.getKey(); 516 Long e = me.getValue(); //facs.get(p); 517 if (p.degree() <= 1) { 518 factors.put(p, e); 519 } else { 520 Factors<C> afacs = factorsAbsoluteIrreducible(p); 521 if (afacs.afac == null) { // absolute irreducible 522 factors.put(p, e); 523 } else { 524 afactors.put(afacs, e); 525 } 526 } 527 } 528 //System.out.println("K(alpha) factors multi = " + factors); 529 return new FactorsMap<C>(P, factors, afactors); 530 } 531 532 533 /** 534 * GenPolynomial absolute factorization of a squarefree polynomial. 535 * @param P squarefree and primitive GenPolynomial. 536 * @return factors list container: [p_1,...,p_k] with P = prod_{i=1, ..., k} 537 * p_i. <b>Note:</b> K(alpha) not yet minimal. 538 */ 539 // @Override 540 public FactorsList<C> factorsAbsoluteSquarefree(GenPolynomial<C> P) { 541 if (P == null) { 542 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 543 } 544 List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>(); 545 if (P.isZERO()) { 546 return new FactorsList<C>(P, factors); 547 } 548 //System.out.println("\nP = " + P); 549 GenPolynomialRing<C> pfac = P.ring; // K[x] 550 if (pfac.nvar <= 1) { 551 return baseFactorsAbsoluteSquarefree(P); 552 } 553 if (!pfac.coFac.isField()) { 554 throw new IllegalArgumentException("only for field coefficients"); 555 } 556 if (P.degree() <= 1) { 557 factors.add(P); 558 return new FactorsList<C>(P, factors); 559 } 560 // factor over K (=C) 561 List<GenPolynomial<C>> facs = factorsSquarefree(P); 562 if (debug && !isFactorization(P, facs)) { 563 throw new ArithmeticException("isFactorization = false"); 564 } 565 if (logger.isInfoEnabled()) { 566 logger.info("all K factors = " + facs); // Q[X] 567 //System.out.println("\nall K factors = " + facs); // Q[X] 568 } 569 List<Factors<C>> afactors = new ArrayList<Factors<C>>(); 570 // factor over K(alpha) 571 for (GenPolynomial<C> p : facs) { 572 if (p.degree() <= 1) { 573 factors.add(p); 574 } else { 575 Factors<C> afacs = factorsAbsoluteIrreducible(p); 576 if (debug) { 577 logger.info("K(alpha) factors = " + afacs); // K(alpha)[X] 578 } 579 if (afacs.afac == null) { // absolute irreducible 580 factors.add(p); 581 } else { 582 afactors.add(afacs); 583 } 584 } 585 } 586 //System.out.println("K(alpha) factors = " + factors); 587 return new FactorsList<C>(P, factors, afactors); 588 } 589 590 591 /** 592 * GenPolynomial absolute factorization of a irreducible polynomial. 593 * @param P irreducible! GenPolynomial. 594 * @return factors container: [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i 595 * in K(alpha)[x] for suitable alpha and p_i irreducible over L[x], 596 * where K \subset K(alpha) \subset L is an algebraically closed 597 * field over K. <b>Note:</b> K(alpha) not yet minimal. 598 */ 599 public Factors<C> factorsAbsoluteIrreducible(GenPolynomial<C> P) { 600 if (P == null) { 601 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 602 } 603 if (P.isZERO()) { 604 return new Factors<C>(P); 605 } 606 GenPolynomialRing<C> pfac = P.ring; // K[x] 607 if (pfac.nvar <= 1) { 608 return baseFactorsAbsoluteIrreducible(P); 609 } 610 if (!pfac.coFac.isField()) { 611 throw new IllegalArgumentException("only for field coefficients"); 612 } 613 //List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>(); 614 if (P.degree() <= 1) { 615 return new Factors<C>(P); 616 } 617 // find field extension K(alpha) 618 GenPolynomial<C> up = P; 619 RingFactory<C> cf = pfac.coFac; 620 long cr = cf.characteristic().longValue(); // char might be larger 621 if (cr == 0L) { 622 cr = Long.MAX_VALUE; 623 } 624 long rp = 0L; 625 for (int i = 0; i < (pfac.nvar - 1); i++) { 626 rp = 0L; 627 GenPolynomialRing<C> nfac = pfac.contract(1); 628 String[] vn = new String[] { pfac.getVars()[pfac.nvar - 1] }; 629 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(nfac, 1, 630 pfac.tord, vn); 631 GenPolynomial<GenPolynomial<C>> upr = PolyUtil.<C> recursive(rfac, up); 632 //System.out.println("upr = " + upr); 633 GenPolynomial<C> ep; 634 do { 635 if (rp >= cr) { 636 throw new ArithmeticException("elements of prime field exhausted: " + cr); 637 } 638 C r = cf.fromInteger(rp); //cf.random(rp); 639 //System.out.println("r = " + r); 640 ep = PolyUtil.<C> evaluateMainRecursive(nfac, upr, r); 641 //System.out.println("ep = " + ep); 642 rp++; 643 } while (!isSquarefree(ep) /*todo: || ep.degree() <= 1*/); // max deg 644 up = ep; 645 pfac = nfac; 646 } 647 up = up.monic(); 648 if (debug) { 649 logger.info("P(" + rp + ") = " + up); 650 //System.out.println("up = " + up); 651 } 652 if (debug && !isSquarefree(up)) { 653 throw new ArithmeticException("not irreducible up = " + up); 654 } 655 if (up.degree(0) <= 1) { 656 return new Factors<C>(P); 657 } 658 // find irreducible factor of up 659 List<GenPolynomial<C>> UF = baseFactorsSquarefree(up); 660 //System.out.println("UF = " + UF); 661 FactorsList<C> aUF = baseFactorsAbsoluteSquarefree(up); 662 //System.out.println("aUF = " + aUF); 663 AlgebraicNumberRing<C> arfac = aUF.findExtensionField(); 664 //System.out.println("arfac = " + arfac); 665 666 long e = up.degree(0); 667 // search factor polynomial with smallest degree 668 for (int i = 0; i < UF.size(); i++) { 669 GenPolynomial<C> upi = UF.get(i); 670 long d = upi.degree(0); 671 if (1 <= d && d <= e) { 672 up = upi; 673 e = up.degree(0); 674 } 675 } 676 if (up.degree(0) <= 1) { 677 return new Factors<C>(P); 678 } 679 if (debug) { 680 logger.info("field extension by " + up); 681 } 682 683 List<GenPolynomial<AlgebraicNumber<C>>> afactors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>(); 684 685 // setup field extension K(alpha) 686 //String[] vars = new String[] { "z_" + Math.abs(up.hashCode() % 1000) }; 687 String[] vars = pfac.newVars("z_"); 688 pfac = pfac.copy(); 689 //String[] ovars = 690 pfac.setVars(vars); // side effects! 691 //GenPolynomial<C> aup = pfac.copy(up); // hack to exchange the variables 692 //AlgebraicNumberRing<C> afac = new AlgebraicNumberRing<C>(aup,true); // since irreducible 693 AlgebraicNumberRing<C> afac = arfac; 694 int depth = afac.depth(); 695 //System.out.println("afac = " + afac); 696 GenPolynomialRing<AlgebraicNumber<C>> pafac = new GenPolynomialRing<AlgebraicNumber<C>>(afac, 697 P.ring.nvar, P.ring.tord, P.ring.getVars()); 698 //System.out.println("pafac = " + pafac); 699 // convert to K(alpha) 700 GenPolynomial<AlgebraicNumber<C>> Pa = PolyUtil.<C> convertToRecAlgebraicCoefficients(depth, pafac, 701 P); 702 //System.out.println("Pa = " + Pa); 703 // factor over K(alpha) 704 FactorAbstract<AlgebraicNumber<C>> engine = FactorFactory.<C> getImplementation(afac); 705 afactors = engine.factorsSquarefree(Pa); 706 if (debug) { 707 logger.info("K(alpha) factors multi = " + afactors); 708 //System.out.println("K(alpha) factors = " + afactors); 709 } 710 if (afactors.size() <= 1) { 711 return new Factors<C>(P); 712 } 713 // normalize first factor to monic 714 GenPolynomial<AlgebraicNumber<C>> p1 = afactors.get(0); 715 AlgebraicNumber<C> p1c = p1.leadingBaseCoefficient(); 716 if (!p1c.isONE()) { 717 GenPolynomial<AlgebraicNumber<C>> p2 = afactors.get(1); 718 afactors.remove(p1); 719 afactors.remove(p2); 720 p1 = p1.divide(p1c); 721 p2 = p2.multiply(p1c); 722 afactors.add(p1); 723 afactors.add(p2); 724 } 725 // recursion for splitting field 726 // find minimal field extension K(beta) \subset K(alpha) 727 return new Factors<C>(P, afac, Pa, afactors); 728 } 729 730 731 /** 732 * GenPolynomial is absolute factorization. 733 * @param facs factors container. 734 * @return true if P = prod_{i=1,...,r} p_i, else false. 735 */ 736 public boolean isAbsoluteFactorization(Factors<C> facs) { 737 if (facs == null) { 738 throw new IllegalArgumentException("facs may not be null"); 739 } 740 if (facs.afac == null) { 741 return true; 742 } 743 GenPolynomial<AlgebraicNumber<C>> fa = facs.apoly; 744 GenPolynomialRing<AlgebraicNumber<C>> pafac = fa.ring; 745 GenPolynomial<AlgebraicNumber<C>> t = pafac.getONE(); 746 for (GenPolynomial<AlgebraicNumber<C>> f : facs.afactors) { 747 t = t.multiply(f); 748 } 749 //return fa.equals(t) || fa.equals(t.negate()); 750 boolean b = fa.equals(t) || fa.equals(t.negate()); 751 if (b) { 752 return b; 753 } 754 if (facs.arfactors == null) { 755 return false; 756 } 757 for (Factors<AlgebraicNumber<C>> arp : facs.arfactors) { 758 t = t.multiply(arp.poly); 759 } 760 b = fa.equals(t) || fa.equals(t.negate()); 761 if (!b) { 762 System.out.println("\nFactors: " + facs); 763 System.out.println("fa = " + fa); 764 System.out.println("t = " + t); 765 } 766 return b; 767 } 768 769 770 /** 771 * GenPolynomial is absolute factorization. 772 * @param facs factors list container. 773 * @return true if P = prod_{i=1,...,r} p_i, else false. 774 */ 775 public boolean isAbsoluteFactorization(FactorsList<C> facs) { 776 if (facs == null) { 777 throw new IllegalArgumentException("facs may not be null"); 778 } 779 GenPolynomial<C> P = facs.poly; 780 GenPolynomial<C> t = P.ring.getONE(); 781 for (GenPolynomial<C> f : facs.factors) { 782 t = t.multiply(f); 783 } 784 if (P.equals(t) || P.equals(t.negate())) { 785 return true; 786 } 787 if (facs.afactors == null) { 788 return false; 789 } 790 for (Factors<C> fs : facs.afactors) { 791 if (!isAbsoluteFactorization(fs)) { 792 return false; 793 } 794 t = t.multiply(facs.poly); 795 } 796 //return P.equals(t) || P.equals(t.negate()); 797 boolean b = P.equals(t) || P.equals(t.negate()); 798 if (!b) { 799 System.out.println("\nFactorsList: " + facs); 800 System.out.println("P = " + P); 801 System.out.println("t = " + t); 802 } 803 return b; 804 } 805 806 807 /** 808 * GenPolynomial is absolute factorization. 809 * @param facs factors map container. 810 * @return true if P = prod_{i=1,...,k} p_i**e_i , else false. 811 */ 812 public boolean isAbsoluteFactorization(FactorsMap<C> facs) { 813 if (facs == null) { 814 throw new IllegalArgumentException("facs may not be null"); 815 } 816 GenPolynomial<C> P = facs.poly; 817 GenPolynomial<C> t = P.ring.getONE(); 818 for (Map.Entry<GenPolynomial<C>, Long> me : facs.factors.entrySet()) { 819 GenPolynomial<C> f = me.getKey(); 820 long e = me.getValue(); 821 GenPolynomial<C> g = f.power(e); 822 t = t.multiply(g); 823 } 824 if (P.equals(t) || P.equals(t.negate())) { 825 return true; 826 } 827 if (facs.afactors == null) { 828 return false; 829 } 830 for (Map.Entry<Factors<C>, Long> me : facs.afactors.entrySet()) { 831 Factors<C> fs = me.getKey(); 832 if (!isAbsoluteFactorization(fs)) { 833 return false; 834 } 835 long e = me.getValue(); 836 GenPolynomial<C> g = fs.poly.power(e); 837 t = t.multiply(g); 838 } 839 boolean b = P.equals(t) || P.equals(t.negate()); 840 if (!b) { 841 System.out.println("\nFactorsMap: " + facs); 842 System.out.println("P = " + P); 843 System.out.println("t = " + t); 844 } 845 return b; 846 } 847 848}