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 -&gt; e_1, ..., p_k -&gt; 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 -&gt; e_1, ..., p_k -&gt; 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 -&gt; e_1, ..., p_k -&gt; 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 -&gt; e_1, ..., p_k -&gt; 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 -&gt; e_1, ..., p_k -&gt; 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 -&gt; e_1, ..., p_k -&gt; 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 -&gt; e_1, ..., p_k -&gt; 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    }