001 /*
002 * $Id: FactorAbstract.java 3727 2011-08-07 18:00:09Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010 import java.util.SortedMap;
011 import java.util.SortedSet;
012 import java.util.TreeMap;
013 import java.util.TreeSet;
014
015 import org.apache.log4j.Logger;
016
017 import edu.jas.kern.TimeStatus;
018 import edu.jas.poly.GenPolynomial;
019 import edu.jas.poly.GenPolynomialRing;
020 import edu.jas.poly.PolyUtil;
021 import edu.jas.poly.ExpVector;
022 import edu.jas.structure.GcdRingElem;
023 import edu.jas.structure.RingFactory;
024 import edu.jas.util.KsubSet;
025
026
027 /**
028 * Abstract factorization algorithms class. This class contains implementations
029 * of all methods of the <code>Factorization</code> interface, except the method
030 * for factorization of a squarefree polynomial. The methods to obtain
031 * squarefree polynomials delegate the computation to the
032 * <code>GreatestCommonDivisor</code> classes and are included for convenience.
033 * @param <C> coefficient type
034 * @author Heinz Kredel
035 * @see edu.jas.ufd.FactorFactory
036 */
037
038 public abstract class FactorAbstract<C extends GcdRingElem<C>> implements Factorization<C> {
039
040
041 private static final Logger logger = Logger.getLogger(FactorAbstract.class);
042
043
044 private final boolean debug = logger.isDebugEnabled();
045
046
047 /**
048 * Gcd engine for base coefficients.
049 */
050 protected final GreatestCommonDivisorAbstract<C> engine;
051
052
053 /**
054 * Squarefree decompositon engine for base coefficients.
055 */
056 protected final SquarefreeAbstract<C> sengine;
057
058
059 /**
060 * No argument constructor.
061 */
062 protected FactorAbstract() {
063 throw new IllegalArgumentException("don't use this constructor");
064 }
065
066
067 /**
068 * Constructor.
069 * @param cfac coefficient ring factory.
070 */
071 public FactorAbstract(RingFactory<C> cfac) {
072 engine = GCDFactory.<C> getProxy(cfac);
073 //engine = GCDFactory.<C> getImplementation(cfac);
074 sengine = SquarefreeFactory.<C> getImplementation(cfac);
075 }
076
077
078 /**
079 * Get the String representation.
080 * @see java.lang.Object#toString()
081 */
082 @Override
083 public String toString() {
084 return getClass().getName();
085 }
086
087
088 /**
089 * GenPolynomial test if is irreducible.
090 * @param P GenPolynomial.
091 * @return true if P is irreducible, else false.
092 */
093 public boolean isIrreducible(GenPolynomial<C> P) {
094 if (!isSquarefree(P)) {
095 return false;
096 }
097 List<GenPolynomial<C>> F = factorsSquarefree(P);
098 if (F.size() == 1) {
099 return true;
100 } else if (F.size() > 2) {
101 return false;
102 } else { //F.size() == 2
103 boolean cnst = false;
104 for (GenPolynomial<C> p : F) {
105 if (p.isConstant()) {
106 cnst = true;
107 }
108 }
109 return cnst;
110 }
111 }
112
113
114 /**
115 * GenPolynomial test if a non trivial factorization exsists.
116 * @param P GenPolynomial.
117 * @return true if P is reducible, else false.
118 */
119 public boolean isReducible(GenPolynomial<C> P) {
120 return !isIrreducible(P);
121 }
122
123
124 /**
125 * GenPolynomial test if is squarefree.
126 * @param P GenPolynomial.
127 * @return true if P is squarefree, else false.
128 */
129 public boolean isSquarefree(GenPolynomial<C> P) {
130 return sengine.isSquarefree(P);
131 }
132
133
134 /**
135 * GenPolynomial factorization of a squarefree polynomial, using Kronecker substitution.
136 * @param P squarefree and primitive! (respectively monic) GenPolynomial.
137 * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i.
138 */
139 public List<GenPolynomial<C>> factorsSquarefree(GenPolynomial<C> P) {
140 if (P == null) {
141 throw new IllegalArgumentException(this.getClass().getName() + " P != null");
142 }
143 GenPolynomialRing<C> pfac = P.ring;
144 if (pfac.nvar == 1) {
145 return baseFactorsSquarefree(P);
146 }
147 List<GenPolynomial<C>> factors = new ArrayList<GenPolynomial<C>>();
148 if (P.isZERO()) {
149 return factors;
150 }
151 if (P.degreeVector().totalDeg() <= 1L) {
152 factors.add(P);
153 return factors;
154 }
155 long d = P.degree() + 1L;
156 GenPolynomial<C> kr = PolyUfdUtil.<C> substituteKronecker(P, d);
157 GenPolynomialRing<C> ufac = kr.ring;
158 ufac.setVars(ufac.newVars("zz")); // side effects
159 logger.info("deg(subs(P,d=" + d + ")) = " + kr.degree(0) + ", original degrees: " + P.degreeVector());
160 if (debug) {
161 logger.info("subs(P,d=" + d + ") = " + kr);
162 //System.out.println("subs(P,d=" + d + ") = " + kr);
163 }
164 if (kr.degree(0) > 100) {
165 logger.warn("Kronecker substitution has to high degree");
166 TimeStatus.checkTime("degree > 100");
167 }
168
169 // factor Kronecker polynomial
170 List<GenPolynomial<C>> ulist = new ArrayList<GenPolynomial<C>>();
171 // kr might not be squarefree so complete factor univariate
172 SortedMap<GenPolynomial<C>, Long> slist = baseFactors(kr);
173 if (debug && !isFactorization(kr, slist)) {
174 System.out.println("kr = " + kr);
175 System.out.println("slist = " + slist);
176 throw new ArithmeticException("no factorization");
177 }
178 for (GenPolynomial<C> g : slist.keySet()) {
179 long e = slist.get(g);
180 for (int i = 0; i < e; i++) { // is this really required? yes!
181 ulist.add(g);
182 }
183 }
184 //System.out.println("ulist = " + ulist);
185 if (ulist.size() == 1 && ulist.get(0).degree() == P.degree()) {
186 factors.add(P);
187 return factors;
188 }
189 //wrong: List<GenPolynomial<C>> klist = PolyUfdUtil.<C> backSubstituteKronecker(pfac, ulist, d);
190 //System.out.println("back(klist) = " + PolyUfdUtil.<C> backSubstituteKronecker(pfac, ulist, d));
191 if (logger.isInfoEnabled()) {
192 logger.info("ulist = " + ulist);
193 //System.out.println("ulist = " + ulist);
194 }
195 // combine trial factors
196 int dl = ulist.size() - 1; //(ulist.size() + 1) / 2;
197 //System.out.println("dl = " + dl);
198 int ti = 0;
199 GenPolynomial<C> u = P;
200 long deg = (u.degree() + 1L) / 2L; // max deg
201 ExpVector evl = u.leadingExpVector();
202 ExpVector evt = u.trailingExpVector();
203 //System.out.println("deg = " + deg);
204 for (int j = 1; j <= dl; j++) {
205 KsubSet<GenPolynomial<C>> ps = new KsubSet<GenPolynomial<C>>(ulist, j);
206 for (List<GenPolynomial<C>> flist : ps) {
207 //System.out.println("flist = " + flist);
208 GenPolynomial<C> utrial = ufac.getONE();
209 for (int k = 0; k < flist.size(); k++) {
210 utrial = utrial.multiply(flist.get(k));
211 }
212 GenPolynomial<C> trial = PolyUfdUtil.<C> backSubstituteKronecker(pfac, utrial, d);
213 ti++;
214 if (ti % 2000 == 0) {
215 System.out.print("ti(" + ti + ") ");
216 TimeStatus.checkTime(ti + " % 2000 == 0");
217 }
218 if ( !evl.multipleOf(trial.leadingExpVector()) ) {
219 continue;
220 }
221 if ( !evt.multipleOf(trial.trailingExpVector()) ) {
222 continue;
223 }
224 if (trial.degree() > deg || trial.isConstant()) {
225 continue;
226 }
227 trial = trial.monic();
228 if (ti % 15000 == 0) {
229 System.out.println("\ndl = " + dl + ", deg(u) = " + deg);
230 System.out.println("ulist = " + ulist);
231 System.out.println("kr = " + kr);
232 System.out.println("u = " + u);
233 System.out.println("trial = " + trial);
234 }
235 GenPolynomial<C> rem = PolyUtil.<C> basePseudoRemainder(u, trial);
236 //System.out.println(" rem = " + rem);
237 if (rem.isZERO()) {
238 logger.info("trial = " + trial);
239 //System.out.println("trial = " + trial);
240 factors.add(trial);
241 u = PolyUtil.<C> basePseudoDivide(u, trial); //u = u.divide( trial );
242 evl = u.leadingExpVector();
243 evt = u.trailingExpVector();
244 if (u.isConstant()) {
245 j = dl + 1;
246 break;
247 }
248 //if (ulist.removeAll(flist)) {
249 ulist = removeOnce(ulist, flist);
250 if (ulist != null) {
251 //System.out.println("new ulist = " + ulist);
252 dl = (ulist.size() + 1) / 2;
253 j = 0; // since j++
254 break;
255 //} else {
256 // logger.error("error removing flist from ulist = " + ulist);
257 }
258 }
259 }
260 }
261 if (!u.isONE() && !u.equals(P)) {
262 logger.info("rest u = " + u);
263 //System.out.println("rest u = " + u);
264 factors.add(u);
265 }
266 if (factors.size() == 0) {
267 logger.info("irred u = " + u);
268 //System.out.println("irred u = " + u);
269 factors.add(P);
270 }
271 return factors;
272 }
273
274
275 /**
276 * Remove one occurence of elements.
277 * @param a list of objects.
278 * @param b list of objects.
279 * @return remove every element of b from a, but only one occurence.
280 */
281 static <T> List<T> removeOnce(List<T> a, List<T> b) {
282 List<T> res = new ArrayList<T>();
283 res.addAll(a);
284 for (T e : b) {
285 boolean t = res.remove(e);
286 }
287 return res;
288 }
289
290
291 /**
292 * Univariate GenPolynomial factorization ignoring multiplicities.
293 * @param P GenPolynomial in one variable.
294 * @return [p_1, ..., p_k] with P = prod_{i=1,...,k} p_i**{e_i} for some
295 * e_i.
296 */
297 public List<GenPolynomial<C>> baseFactorsRadical(GenPolynomial<C> P) {
298 return new ArrayList<GenPolynomial<C>>(baseFactors(P).keySet());
299 }
300
301
302 /**
303 * Univariate GenPolynomial factorization.
304 * @param P GenPolynomial in one variable.
305 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k}
306 * p_i**e_i.
307 */
308 public SortedMap<GenPolynomial<C>, Long> baseFactors(GenPolynomial<C> P) {
309 if (P == null) {
310 throw new IllegalArgumentException(this.getClass().getName() + " P != null");
311 }
312 GenPolynomialRing<C> pfac = P.ring;
313 SortedMap<GenPolynomial<C>, Long> factors = new TreeMap<GenPolynomial<C>, Long>(pfac.getComparator());
314 if (P.isZERO()) {
315 return factors;
316 }
317 if (pfac.nvar > 1) {
318 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
319 }
320 if (P.isConstant()) {
321 factors.put(P, 1L);
322 return factors;
323 }
324 C c;
325 if (pfac.coFac.isField()) { //pfac.characteristic().signum() > 0
326 c = P.leadingBaseCoefficient();
327 } else {
328 c = engine.baseContent(P);
329 // move sign to the content
330 if (P.signum() < 0 && c.signum() > 0) {
331 c = c.negate();
332 //P = P.negate();
333 }
334 }
335 if (!c.isONE()) {
336 GenPolynomial<C> pc = pfac.getONE().multiply(c);
337 factors.put(pc, 1L);
338 P = P.divide(c); // make primitive or monic
339 }
340 if (logger.isInfoEnabled()) {
341 logger.info("base facs for P = " + P);
342 }
343 SortedMap<GenPolynomial<C>, Long> facs = sengine.baseSquarefreeFactors(P);
344 if (facs == null || facs.size() == 0) {
345 facs = new TreeMap<GenPolynomial<C>, Long>();
346 facs.put(P, 1L);
347 }
348 if (logger.isInfoEnabled()
349 && (facs.size() > 1 || (facs.size() == 1 && facs.get(facs.firstKey()) > 1))) {
350 logger.info("squarefree facs = " + facs);
351 //System.out.println("sfacs = " + facs);
352 //boolean tt = isFactorization(P,facs);
353 //System.out.println("sfacs tt = " + tt);
354 }
355 for (GenPolynomial<C> g : facs.keySet()) {
356 Long k = facs.get(g);
357 //System.out.println("g = " + g);
358 if (pfac.coFac.isField() && !g.leadingBaseCoefficient().isONE()) {
359 g = g.monic(); // how can this happen?
360 logger.warn("squarefree facs mon = " + g);
361 }
362 if (g.degree(0) <= 1) {
363 if (!g.isONE()) {
364 factors.put(g, k);
365 }
366 } else {
367 List<GenPolynomial<C>> sfacs = baseFactorsSquarefree(g);
368 if (debug) {
369 logger.info("factors of squarefree = " + sfacs);
370 //System.out.println("sfacs = " + sfacs);
371 }
372 for (GenPolynomial<C> h : sfacs) {
373 Long j = factors.get(h); // evtl. constants
374 if (j != null) {
375 k += j;
376 }
377 if (!h.isONE()) {
378 factors.put(h, k);
379 }
380 }
381 }
382 }
383 //System.out.println("factors = " + factors);
384 return factors;
385 }
386
387
388 /**
389 * Univariate GenPolynomial factorization of a squarefree polynomial.
390 * @param P squarefree and primitive! GenPolynomial in one variable.
391 * @return [p_1, ..., p_k] with P = prod_{i=1,...,k} p_i.
392 */
393 public abstract List<GenPolynomial<C>> baseFactorsSquarefree(GenPolynomial<C> P);
394
395
396 /**
397 * GenPolynomial factorization ignoring multiplicities.
398 * @param P GenPolynomial.
399 * @return [p_1, ..., p_k] with P = prod_{i=1,...,k} p_i**{e_i} for some
400 * e_i.
401 */
402 public List<GenPolynomial<C>> factorsRadical(GenPolynomial<C> P) {
403 return new ArrayList<GenPolynomial<C>>(factors(P).keySet());
404 }
405
406
407 /**
408 * GenPolynomial list factorization ignoring multiplicities.
409 * @param L list of GenPolynomials.
410 * @return [p_1, ..., p_k] with p = prod_{i=1,...,k} p_i**{e_i} for some e_i
411 * for all p in L.
412 */
413 public List<GenPolynomial<C>> factorsRadical(List<GenPolynomial<C>> L) {
414 SortedSet<GenPolynomial<C>> facs = new TreeSet<GenPolynomial<C>>();
415 for (GenPolynomial<C> p : L) {
416 List<GenPolynomial<C>> fs = factorsRadical(p);
417 facs.addAll(fs);
418 }
419 return new ArrayList<GenPolynomial<C>>(facs);
420 }
421
422
423 /**
424 * GenPolynomial factorization.
425 * @param P GenPolynomial.
426 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k}
427 * p_i**e_i.
428 */
429 public SortedMap<GenPolynomial<C>, Long> factors(GenPolynomial<C> P) {
430 if (P == null) {
431 throw new IllegalArgumentException(this.getClass().getName() + " P != null");
432 }
433 GenPolynomialRing<C> pfac = P.ring;
434 if (pfac.nvar == 1) {
435 return baseFactors(P);
436 }
437 SortedMap<GenPolynomial<C>, Long> factors = new TreeMap<GenPolynomial<C>, Long>(pfac.getComparator());
438 if (P.isZERO()) {
439 return factors;
440 }
441 if (P.isConstant()) {
442 factors.put(P, 1L);
443 return factors;
444 }
445 C c;
446 if (pfac.coFac.isField()) { // pfac.characteristic().signum() > 0
447 c = P.leadingBaseCoefficient();
448 } else {
449 c = engine.baseContent(P);
450 // move sign to the content
451 if (P.signum() < 0 && c.signum() > 0) {
452 c = c.negate();
453 //P = P.negate();
454 }
455 }
456 if (!c.isONE()) {
457 GenPolynomial<C> pc = pfac.getONE().multiply(c);
458 factors.put(pc, 1L);
459 P = P.divide(c); // make base primitive or base monic
460 }
461 if (logger.isInfoEnabled()) {
462 logger.info("squarefree mfacs P = " + P);
463 }
464 SortedMap<GenPolynomial<C>, Long> facs = sengine.squarefreeFactors(P);
465 if (facs == null || facs.size() == 0) {
466 facs = new TreeMap<GenPolynomial<C>, Long>();
467 facs.put(P, 1L);
468 throw new RuntimeException("this should not happen, facs is empty: " + facs);
469 }
470 if (logger.isInfoEnabled()) {
471 if (facs.size() > 1) {
472 logger.info("squarefree mfacs = " + facs);
473 } else if (facs.size() == 1 && facs.get(facs.firstKey()) > 1L) {
474 logger.info("squarefree #mfacs 1-n = " + facs);
475 } else {
476 logger.info("squarefree #mfacs 1-1 = " + facs);
477 }
478 }
479 for (GenPolynomial<C> g : facs.keySet()) {
480 if ( g.isONE() ) { // skip 1
481 continue;
482 }
483 Long d = facs.get(g);
484 List<GenPolynomial<C>> sfacs = factorsSquarefree(g);
485 if (logger.isInfoEnabled()) {
486 logger.info("factors of squarefree ^" + d + " = " + sfacs);
487 //System.out.println("sfacs = " + sfacs);
488 }
489 for (GenPolynomial<C> h : sfacs) {
490 long dd = d;
491 Long j = factors.get(h); // evtl. constants
492 if (j != null) {
493 dd += j;
494 }
495 factors.put(h, dd);
496 }
497 }
498 //System.out.println("factors = " + factors);
499 return factors;
500 }
501
502
503 /**
504 * GenPolynomial greatest squarefree divisor. Delegates computation to a
505 * GreatestCommonDivisor class.
506 * @param P GenPolynomial.
507 * @return squarefree(P).
508 */
509 public GenPolynomial<C> squarefreePart(GenPolynomial<C> P) {
510 return sengine.squarefreePart(P);
511 }
512
513
514 /**
515 * GenPolynomial primitive part. Delegates computation to a
516 * GreatestCommonDivisor class.
517 * @param P GenPolynomial.
518 * @return primitivePart(P).
519 */
520 public GenPolynomial<C> primitivePart(GenPolynomial<C> P) {
521 return engine.primitivePart(P);
522 }
523
524
525 /**
526 * GenPolynomial base primitive part. Delegates computation to a
527 * GreatestCommonDivisor class.
528 * @param P GenPolynomial.
529 * @return basePrimitivePart(P).
530 */
531 public GenPolynomial<C> basePrimitivePart(GenPolynomial<C> P) {
532 return engine.basePrimitivePart(P);
533 }
534
535
536 /**
537 * GenPolynomial squarefree factorization. Delegates computation to a
538 * GreatestCommonDivisor class.
539 * @param P GenPolynomial.
540 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k}
541 * p_i**e_i.
542 */
543 public SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P) {
544 return sengine.squarefreeFactors(P);
545 }
546
547
548 /**
549 * GenPolynomial is factorization.
550 * @param P GenPolynomial.
551 * @param F = [p_1,...,p_k].
552 * @return true if P = prod_{i=1,...,r} p_i, else false.
553 */
554 public boolean isFactorization(GenPolynomial<C> P, List<GenPolynomial<C>> F) {
555 return sengine.isFactorization(P, F);
556 // test irreducible
557 }
558
559
560 /**
561 * GenPolynomial is factorization.
562 * @param P GenPolynomial.
563 * @param F = [p_1 -> e_1, ..., p_k -> e_k].
564 * @return true if P = prod_{i=1,...,k} p_i**e_i , else false.
565 */
566 public boolean isFactorization(GenPolynomial<C> P, SortedMap<GenPolynomial<C>, Long> F) {
567 return sengine.isFactorization(P, F);
568 // test irreducible
569 }
570
571
572 /**
573 * Degree of a factorization.
574 * @param F a factors map [p_1 -> e_1, ..., p_k -> e_k].
575 * @return sum_{i=1,...,k} degree(p_i)*e_i.
576 */
577 public long factorsDegree(SortedMap<GenPolynomial<C>,Long> F) {
578 long d = 0;
579 for ( GenPolynomial<C> p : F.keySet() ) {
580 long e = F.get(p);
581 d += p.degree() * e;
582 }
583 return d;
584 }
585
586
587 /**
588 * GenPolynomial is factorization.
589 * @param P GenPolynomial.
590 * @param F = [p_1 -> e_1, ..., p_k -> e_k].
591 * @return true if P = prod_{i=1,...,k} p_i**e_i , else false.
592 */
593 public boolean isRecursiveFactorization(GenPolynomial<GenPolynomial<C>> P,
594 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> F) {
595 return sengine.isRecursiveFactorization(P, F);
596 // test irreducible
597 }
598
599
600 /**
601 * Recursive GenPolynomial factorization of a squarefree polynomial.
602 * @param P squarefree recursive GenPolynomial.
603 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.
604 */
605 public List<GenPolynomial<GenPolynomial<C>>> recursiveFactorsSquarefree(GenPolynomial<GenPolynomial<C>> P) {
606 if (P == null) {
607 throw new IllegalArgumentException(this.getClass().getName() + " P == null");
608 }
609 List<GenPolynomial<GenPolynomial<C>>> factors = new ArrayList<GenPolynomial<GenPolynomial<C>>>();
610 if (P.isZERO()) {
611 return factors;
612 }
613 if (P.isONE()) {
614 factors.add(P);
615 return factors;
616 }
617 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
618 GenPolynomialRing<C> qi = (GenPolynomialRing<C>) pfac.coFac;
619 GenPolynomialRing<C> ifac = qi.extend(pfac.getVars());
620 GenPolynomial<C> Pi = PolyUtil.<C> distribute(ifac, P);
621 //System.out.println("Pi = " + Pi);
622
623 C ldcf = Pi.leadingBaseCoefficient();
624 if (!ldcf.isONE() && ldcf.isUnit()) {
625 //System.out.println("ldcf = " + ldcf);
626 Pi = Pi.monic();
627 }
628
629 // factor in C[x_1,...,x_n,y_1,...,y_m]
630 List<GenPolynomial<C>> ifacts = factorsSquarefree(Pi);
631 if (logger.isInfoEnabled()) {
632 logger.info("ifacts = " + ifacts);
633 }
634 if (ifacts.size() <= 1) {
635 factors.add(P);
636 return factors;
637 }
638 if (!ldcf.isONE() && ldcf.isUnit()) {
639 GenPolynomial<C> r = ifacts.get(0);
640 ifacts.remove(r);
641 r = r.multiply(ldcf);
642 ifacts.add(0, r);
643 }
644 List<GenPolynomial<GenPolynomial<C>>> rfacts = PolyUtil.<C> recursive(pfac, ifacts);
645 //System.out.println("rfacts = " + rfacts);
646 if (logger.isDebugEnabled()) {
647 logger.info("recfacts = " + rfacts);
648 }
649 factors.addAll(rfacts);
650 return factors;
651 }
652
653
654 /**
655 * Recursive GenPolynomial factorization.
656 * @param P recursive GenPolynomial.
657 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k}
658 * p_i**e_i.
659 */
660 public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveFactors(GenPolynomial<GenPolynomial<C>> P) {
661 if (P == null) {
662 throw new IllegalArgumentException(this.getClass().getName() + " P != null");
663 }
664 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
665 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> factors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>(
666 pfac.getComparator());
667 if (P.isZERO()) {
668 return factors;
669 }
670 if (P.isONE()) {
671 factors.put(P, 1L);
672 return factors;
673 }
674 GenPolynomialRing<C> qi = (GenPolynomialRing<C>) pfac.coFac;
675 GenPolynomialRing<C> ifac = qi.extend(pfac.getVars());
676 GenPolynomial<C> Pi = PolyUtil.<C> distribute(ifac, P);
677 //System.out.println("Pi = " + Pi);
678
679 C ldcf = Pi.leadingBaseCoefficient();
680 if (!ldcf.isONE() && ldcf.isUnit()) {
681 //System.out.println("ldcf = " + ldcf);
682 Pi = Pi.monic();
683 }
684
685 // factor in C[x_1,...,x_n,y_1,...,y_m]
686 SortedMap<GenPolynomial<C>, Long> dfacts = factors(Pi);
687 if (logger.isInfoEnabled()) {
688 logger.info("dfacts = " + dfacts);
689 }
690 if (!ldcf.isONE() && ldcf.isUnit()) {
691 GenPolynomial<C> r = dfacts.firstKey();
692 Long E = dfacts.remove(r);
693 r = r.multiply(ldcf);
694 dfacts.put(r, E);
695 }
696 for (GenPolynomial<C> f : dfacts.keySet()) {
697 Long E = dfacts.get(f);
698 GenPolynomial<GenPolynomial<C>> rp = PolyUtil.<C> recursive(pfac, f);
699 factors.put(rp, E);
700 }
701 //System.out.println("rfacts = " + rfacts);
702 if (logger.isInfoEnabled()) {
703 logger.info("recursive factors = " + factors);
704 }
705 return factors;
706 }
707
708 }