Source code

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