Source code

001/*
002 * $Id: SquarefreeFieldCharP.java 4100 2012-08-12 19:42:07Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.Map;
009import java.util.SortedMap;
010import java.util.TreeMap;
011
012import org.apache.log4j.Logger;
013
014import edu.jas.poly.AlgebraicNumber;
015import edu.jas.poly.AlgebraicNumberRing;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.PolyUtil;
019import edu.jas.structure.GcdRingElem;
020import edu.jas.structure.Power;
021import edu.jas.structure.RingFactory;
022
023
024/**
025 * Squarefree decomposition for coefficient fields of characteristic p.
026 * @author Heinz Kredel
027 */
028
029public abstract class SquarefreeFieldCharP<C extends GcdRingElem<C>> extends SquarefreeAbstract<C> {
030
031
032    private static final Logger logger = Logger.getLogger(SquarefreeFieldCharP.class);
033
034
035    private final boolean debug = logger.isDebugEnabled();
036
037
038    /*
039     * Squarefree engine for characteristic p base coefficients.
040     */
041    //protected final SquarefreeAbstract<C> rengine;
042
043
044    /**
045     * Factory for finite field of characteristic p coefficients.
046     */
047    protected final RingFactory<C> coFac;
048
049
050    /**
051     * Factory for a algebraic extension of a finite field of characteristic p
052     * coefficients. If <code>coFac</code> is an algebraic extension, then
053     * <code>aCoFac</code> is equal to <code>coFac</code>, else
054     * <code>aCoFac</code> is <code>null</code>.
055     */
056    protected final AlgebraicNumberRing<C> aCoFac;
057
058
059    /**
060     * Factory for a transcendental extension of a finite field of
061     * characteristic p coefficients. If <code>coFac</code> is an transcendental
062     * extension, then <code>qCoFac</code> is equal to <code>coFac</code>, else
063     * <code>qCoFac</code> is <code>null</code>.
064     */
065    protected final QuotientRing<C> qCoFac;
066
067
068    /**
069     * Constructor.
070     */
071    @SuppressWarnings("unchecked")
072    public SquarefreeFieldCharP(RingFactory<C> fac) {
073        super(GCDFactory.<C> getProxy(fac));
074        if (!fac.isField()) {
075            //throw new IllegalArgumentException("fac must be a field");
076            logger.warn("fac should be a field: " + fac.toScript());
077        }
078        if (fac.characteristic().signum() == 0) {
079            throw new IllegalArgumentException("characterisic(fac) must be non-zero");
080        }
081        coFac = fac;
082        Object oFac = coFac;
083        if (oFac instanceof AlgebraicNumberRing) {
084            aCoFac = (AlgebraicNumberRing<C>) oFac; // <C> is not correct
085            //rengine = (SquarefreeAbstract) SquarefreeFactory.getImplementation(aCoFac.ring);
086            qCoFac = null;
087        } else {
088            aCoFac = null;
089            if (oFac instanceof QuotientRing) {
090                qCoFac = (QuotientRing<C>) oFac; // <C> is not correct
091                //rengine = (SquarefreeAbstract) SquarefreeFactory.getImplementation(qCoFac.ring);
092            } else {
093                qCoFac = null;
094                //rengine = null; //(SquarefreeAbstract) SquarefreeFactory.getImplementation(oFac);
095            }
096        }
097    }
098
099
100    /**
101     * Get the String representation.
102     * @see java.lang.Object#toString()
103     */
104    @Override
105    public String toString() {
106        return getClass().getName() + " with " + engine + " over " + coFac;
107    }
108
109
110    /**
111     * GenPolynomial polynomial greatest squarefree divisor.
112     * @param P GenPolynomial.
113     * @return squarefree(pp(P)).
114     */
115    @Override
116    public GenPolynomial<C> baseSquarefreePart(GenPolynomial<C> P) {
117        if (P == null || P.isZERO()) {
118            return P;
119        }
120        GenPolynomialRing<C> pfac = P.ring;
121        if (pfac.nvar > 1) {
122            throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
123        }
124        // just for the moment:
125        GenPolynomial<C> s = pfac.getONE();
126        SortedMap<GenPolynomial<C>, Long> factors = baseSquarefreeFactors(P);
127        logger.info("sqfPart,factors = " + factors);
128        for (GenPolynomial<C> sp : factors.keySet()) {
129            s = s.multiply(sp);
130        }
131        return s.monic();
132    }
133
134
135    /**
136     * GenPolynomial polynomial squarefree factorization.
137     * @param A GenPolynomial.
138     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
139     *         p_i^{e_i} and p_i squarefree.
140     */
141    @Override
142    public SortedMap<GenPolynomial<C>, Long> baseSquarefreeFactors(GenPolynomial<C> A) {
143        SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>();
144        if (A == null || A.isZERO()) {
145            return sfactors;
146        }
147        GenPolynomialRing<C> pfac = A.ring;
148        if (A.isConstant()) {
149            C coeff = A.leadingBaseCoefficient();
150            //System.out.println("coeff = " + coeff + " @ " + coeff.factory());
151            SortedMap<C, Long> rfactors = squarefreeFactors(coeff);
152            //System.out.println("rfactors,const = " + rfactors);
153            if (rfactors != null && rfactors.size() > 0) {
154                for (Map.Entry<C, Long> me : rfactors.entrySet()) {
155                    C c = me.getKey();
156                    if (!c.isONE()) {
157                        GenPolynomial<C> cr = pfac.getONE().multiply(c);
158                        Long rk = me.getValue(); // rfactors.get(c);
159                        sfactors.put(cr, rk);
160                    }
161                }
162            } else {
163                sfactors.put(A, 1L);
164            }
165            return sfactors;
166        }
167        if (pfac.nvar > 1) {
168            throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
169        }
170        C ldbcf = A.leadingBaseCoefficient();
171        if (!ldbcf.isONE()) {
172            A = A.divide(ldbcf);
173            SortedMap<C, Long> rfactors = squarefreeFactors(ldbcf);
174            //System.out.println("rfactors,ldbcf = " + rfactors);
175            if (rfactors != null && rfactors.size() > 0) {
176                for (Map.Entry<C, Long> me : rfactors.entrySet()) {
177                    C c = me.getKey();
178                    if (!c.isONE()) {
179                        GenPolynomial<C> cr = pfac.getONE().multiply(c);
180                        Long rk = me.getValue(); //rfactors.get(c);
181                        sfactors.put(cr, rk);
182                    }
183                }
184            } else {
185                GenPolynomial<C> f1 = pfac.getONE().multiply(ldbcf);
186                //System.out.println("gcda sqf f1 = " + f1);
187                sfactors.put(f1, 1L);
188            }
189            ldbcf = pfac.coFac.getONE();
190        }
191        GenPolynomial<C> T0 = A;
192        long e = 1L;
193        GenPolynomial<C> Tp;
194        GenPolynomial<C> T = null;
195        GenPolynomial<C> V = null;
196        long k = 0L;
197        long mp = 0L;
198        boolean init = true;
199        while (true) {
200            //System.out.println("T0 = " + T0);
201            if (init) {
202                if (T0.isConstant() || T0.isZERO()) {
203                    break;
204                }
205                Tp = PolyUtil.<C> baseDeriviative(T0);
206                T = engine.baseGcd(T0, Tp);
207                T = T.monic();
208                V = PolyUtil.<C> basePseudoDivide(T0, T);
209                //System.out.println("iT0 = " + T0);
210                //System.out.println("iTp = " + Tp);
211                //System.out.println("iT  = " + T);
212                //System.out.println("iV  = " + V);
213                //System.out.println("const(iV)  = " + V.isConstant());
214                k = 0L;
215                mp = 0L;
216                init = false;
217            }
218            if (V.isConstant()) {
219                mp = pfac.characteristic().longValue(); // assert != 0
220                //T0 = PolyUtil.<C> baseModRoot(T,mp);
221                T0 = baseRootCharacteristic(T);
222                logger.info("char root: T0 = " + T0 + ", T = " + T);
223                if (T0 == null) {
224                    //break;
225                    T0 = pfac.getZERO();
226                }
227                e = e * mp;
228                init = true;
229                continue;
230            }
231            k++;
232            if (mp != 0L && k % mp == 0L) {
233                T = PolyUtil.<C> basePseudoDivide(T, V);
234                System.out.println("k = " + k);
235                //System.out.println("T = " + T);
236                k++;
237            }
238            GenPolynomial<C> W = engine.baseGcd(T, V);
239            W = W.monic();
240            GenPolynomial<C> z = PolyUtil.<C> basePseudoDivide(V, W);
241            //System.out.println("W = " + W);
242            //System.out.println("z = " + z);
243            V = W;
244            T = PolyUtil.<C> basePseudoDivide(T, V);
245            //System.out.println("V = " + V);
246            //System.out.println("T = " + T);
247            if (z.degree(0) > 0) {
248                if (ldbcf.isONE() && !z.leadingBaseCoefficient().isONE()) {
249                    z = z.monic();
250                    logger.info("z,monic = " + z);
251                }
252                sfactors.put(z, (e * k));
253            }
254        }
255        //      look, a stupid error:
256        //         if ( !ldbcf.isONE() ) {
257        //             GenPolynomial<C> f1 = sfactors.firstKey();
258        //             long e1 = sfactors.remove(f1);
259        //             System.out.println("gcda sqf c = " + c);
260        //             f1 = f1.multiply(c);
261        //             //System.out.println("gcda sqf f1e = " + f1);
262        //             sfactors.put(f1,e1);
263        //         }
264        logger.info("exit char root: T0 = " + T0 + ", T = " + T);
265        return sfactors;
266    }
267
268
269    /**
270     * GenPolynomial recursive univariate polynomial greatest squarefree
271     * divisor.
272     * @param P recursive univariate GenPolynomial.
273     * @return squarefree(pp(P)).
274     */
275    @Override
276    public GenPolynomial<GenPolynomial<C>> recursiveUnivariateSquarefreePart(GenPolynomial<GenPolynomial<C>> P) {
277        if (P == null || P.isZERO()) {
278            return P;
279        }
280        GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
281        if (pfac.nvar > 1) {
282            throw new IllegalArgumentException(this.getClass().getName()
283                            + " only for multivariate polynomials");
284        }
285        // just for the moment:
286        GenPolynomial<GenPolynomial<C>> s = pfac.getONE();
287
288        SortedMap<GenPolynomial<GenPolynomial<C>>, Long> factors = recursiveUnivariateSquarefreeFactors(P);
289        if (logger.isInfoEnabled()) {
290            logger.info("sqfPart,factors = " + factors);
291        }
292        for (GenPolynomial<GenPolynomial<C>> sp : factors.keySet()) {
293            s = s.multiply(sp);
294        }
295        return PolyUtil.<C> monic(s);
296    }
297
298
299    /**
300     * GenPolynomial recursive univariate polynomial squarefree factorization.
301     * @param P recursive univariate GenPolynomial.
302     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
303     *         p_i^{e_i} and p_i squarefree.
304     */
305    @Override
306    public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveUnivariateSquarefreeFactors(
307                    GenPolynomial<GenPolynomial<C>> P) {
308        SortedMap<GenPolynomial<GenPolynomial<C>>, Long> sfactors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>();
309        if (P == null || P.isZERO()) {
310            return sfactors;
311        }
312        GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
313        if (pfac.nvar > 1) {
314            // recursiveContent not possible by return type
315            throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
316        }
317        // if base coefficient ring is a field, make monic
318        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac;
319        C ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient();
320        if (!ldbcf.isONE()) {
321            GenPolynomial<C> lc = cfac.getONE().multiply(ldbcf);
322            GenPolynomial<GenPolynomial<C>> pl = pfac.getONE().multiply(lc);
323            sfactors.put(pl, 1L);
324            C li = ldbcf.inverse();
325            //System.out.println("li = " + li);
326            P = P.multiply(cfac.getONE().multiply(li));
327            //System.out.println("P,monic = " + P);
328            ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient();
329            if (debug) {
330                logger.debug("new ldbcf: " + ldbcf);
331            }
332        }
333        // factors of content
334        GenPolynomial<C> Pc = engine.recursiveContent(P);
335        if (logger.isInfoEnabled()) {
336            logger.info("Pc = " + Pc);
337        }
338        Pc = Pc.monic();
339        if (!Pc.isONE()) {
340            P = PolyUtil.<C> coefficientPseudoDivide(P, Pc);
341        }
342        SortedMap<GenPolynomial<C>, Long> rsf = squarefreeFactors(Pc);
343        if (logger.isInfoEnabled()) {
344            logger.info("rsf = " + rsf);
345        }
346        // add factors of content
347        for (Map.Entry<GenPolynomial<C>, Long> me : rsf.entrySet()) {
348            GenPolynomial<C> c = me.getKey();
349            if (!c.isONE()) {
350                GenPolynomial<GenPolynomial<C>> cr = pfac.getONE().multiply(c);
351                Long rk = me.getValue(); //rsf.get(c);
352                sfactors.put(cr, rk);
353            }
354        }
355
356        // factors of recursive polynomial
357        GenPolynomial<GenPolynomial<C>> T0 = P;
358        long e = 1L;
359        GenPolynomial<GenPolynomial<C>> Tp;
360        GenPolynomial<GenPolynomial<C>> T = null;
361        GenPolynomial<GenPolynomial<C>> V = null;
362        long k = 0L;
363        long mp = 0L;
364        boolean init = true;
365        while (true) {
366            if (init) {
367                if (T0.isConstant() || T0.isZERO()) {
368                    break;
369                }
370                Tp = PolyUtil.<C> recursiveDeriviative(T0);
371                T = engine.recursiveUnivariateGcd(T0, Tp);
372                T = PolyUtil.<C> monic(T);
373                V = PolyUtil.<C> recursivePseudoDivide(T0, T);
374                //System.out.println("iT0 = " + T0);
375                //System.out.println("iTp = " + Tp);
376                //System.out.println("iT = " + T);
377                //System.out.println("iV = " + V);
378                k = 0L;
379                mp = 0L;
380                init = false;
381            }
382            if (V.isConstant()) {
383                mp = pfac.characteristic().longValue(); // assert != 0
384                //T0 = PolyUtil.<C> recursiveModRoot(T,mp);
385                T0 = recursiveUnivariateRootCharacteristic(T);
386                logger.info("char root: T0r = " + T0 + ", Tr = " + T);
387                if (T0 == null) {
388                    //break;
389                    T0 = pfac.getZERO();
390                }
391                e = e * mp;
392                init = true;
393                //continue;
394            }
395            k++;
396            if (mp != 0L && k % mp == 0L) {
397                T = PolyUtil.<C> recursivePseudoDivide(T, V);
398                System.out.println("k = " + k);
399                //System.out.println("T = " + T);
400                k++;
401            }
402            GenPolynomial<GenPolynomial<C>> W = engine.recursiveUnivariateGcd(T, V);
403            W = PolyUtil.<C> monic(W);
404            GenPolynomial<GenPolynomial<C>> z = PolyUtil.<C> recursivePseudoDivide(V, W);
405            //System.out.println("W = " + W);
406            //System.out.println("z = " + z);
407            V = W;
408            T = PolyUtil.<C> recursivePseudoDivide(T, V);
409            //System.out.println("V = " + V);
410            //System.out.println("T = " + T);
411            //was: if ( z.degree(0) > 0 ) {
412            if (!z.isONE() && !z.isZERO()) {
413                z = PolyUtil.<C> monic(z);
414                logger.info("z,put = " + z);
415                sfactors.put(z, (e * k));
416            }
417        }
418        logger.info("exit char root: T0 = " + T0 + ", T = " + T);
419        if (sfactors.size() == 0) {
420            sfactors.put(pfac.getONE(), 1L);
421        }
422        return sfactors;
423    }
424
425
426    /**
427     * GenPolynomial greatest squarefree divisor.
428     * @param P GenPolynomial.
429     * @return squarefree(pp(P)).
430     */
431    @Override
432    public GenPolynomial<C> squarefreePart(GenPolynomial<C> P) {
433        if (P == null) {
434            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
435        }
436        if (P.isZERO()) {
437            return P;
438        }
439        GenPolynomialRing<C> pfac = P.ring;
440        if (pfac.nvar <= 1) {
441            return baseSquarefreePart(P);
442        }
443        // just for the moment:
444        GenPolynomial<C> s = pfac.getONE();
445        SortedMap<GenPolynomial<C>, Long> factors = squarefreeFactors(P);
446        if (logger.isInfoEnabled()) {
447            logger.info("sqfPart,factors = " + factors);
448        }
449        for (GenPolynomial<C> sp : factors.keySet()) {
450            if (sp.isConstant()) {
451                continue;
452            }
453            s = s.multiply(sp);
454        }
455        return s.monic();
456    }
457
458
459    /**
460     * GenPolynomial squarefree factorization.
461     * @param P GenPolynomial.
462     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
463     *         p_i^{e_i} and p_i squarefree.
464     */
465    @Override
466    public SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P) {
467        if (P == null) {
468            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
469        }
470        GenPolynomialRing<C> pfac = P.ring;
471        if (pfac.nvar <= 1) {
472            return baseSquarefreeFactors(P);
473        }
474        SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>();
475        if (P.isZERO()) {
476            return sfactors;
477        }
478        GenPolynomialRing<C> cfac = pfac.contract(1);
479        GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, 1);
480
481        GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P);
482        SortedMap<GenPolynomial<GenPolynomial<C>>, Long> PP = recursiveUnivariateSquarefreeFactors(Pr);
483
484        for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> m : PP.entrySet()) {
485            Long i = m.getValue();
486            GenPolynomial<GenPolynomial<C>> Dr = m.getKey();
487            GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, Dr);
488            sfactors.put(D, i);
489        }
490        return sfactors;
491    }
492
493
494    /**
495     * Coefficient squarefree factorization.
496     * @param coeff coefficient.
497     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
498     *         p_i^{e_i} and p_i squarefree.
499     */
500    @Override
501    public SortedMap<C, Long> squarefreeFactors(C coeff) {
502        if (coeff == null) {
503            return null;
504        }
505        SortedMap<C, Long> factors = new TreeMap<C, Long>();
506        RingFactory<C> cfac = (RingFactory<C>) coeff.factory();
507        if (aCoFac != null) {
508            AlgebraicNumber<C> an = (AlgebraicNumber<C>) (Object) coeff;
509            if (cfac.isFinite()) {
510                SquarefreeFiniteFieldCharP<C> reng = (SquarefreeFiniteFieldCharP) SquarefreeFactory
511                                .getImplementation(cfac);
512                SortedMap<C, Long> rfactors = reng.rootCharacteristic(coeff); // ??
513                logger.info("rfactors,finite = " + rfactors);
514                factors.putAll(rfactors);
515                //return factors;
516            } else {
517                SquarefreeInfiniteAlgebraicFieldCharP<C> reng = (SquarefreeInfiniteAlgebraicFieldCharP) SquarefreeFactory
518                                .getImplementation(cfac);
519                SortedMap<AlgebraicNumber<C>, Long> rfactors = reng.squarefreeFactors(an);
520                logger.info("rfactors,infinite,algeb = " + rfactors);
521                for (Map.Entry<AlgebraicNumber<C>, Long> me : rfactors.entrySet()) {
522                    AlgebraicNumber<C> c = me.getKey();
523                    if (!c.isONE()) {
524                        C cr = (C) (Object) c;
525                        Long rk = me.getValue(); // rfactors.get(c);
526                        factors.put(cr, rk);
527                    }
528                }
529            }
530        } else if (qCoFac != null) {
531            Quotient<C> q = (Quotient<C>) (Object) coeff;
532            SquarefreeInfiniteFieldCharP<C> reng = (SquarefreeInfiniteFieldCharP) SquarefreeFactory
533                            .getImplementation(cfac);
534            SortedMap<Quotient<C>, Long> rfactors = reng.squarefreeFactors(q);
535            logger.info("rfactors,infinite = " + rfactors);
536            for (Map.Entry<Quotient<C>, Long> me : rfactors.entrySet()) {
537                Quotient<C> c = me.getKey();
538                if (!c.isONE()) {
539                    C cr = (C) (Object) c;
540                    Long rk = me.getValue(); //rfactors.get(c);
541                    factors.put(cr, rk);
542                }
543            }
544        } else if (cfac.isFinite()) {
545            SquarefreeFiniteFieldCharP<C> reng = (SquarefreeFiniteFieldCharP) SquarefreeFactory
546                            .getImplementation(cfac);
547            SortedMap<C, Long> rfactors = reng.rootCharacteristic(coeff); // ??
548            logger.info("rfactors,finite = " + rfactors);
549            factors.putAll(rfactors);
550            //return factors;
551        } else {
552            logger.warn("case " + cfac + " not implemented");
553        }
554        return factors;
555    }
556
557
558    /* --------- char-th roots --------------------- */
559
560
561    /**
562     * GenPolynomial char-th root univariate polynomial.
563     * @param P GenPolynomial.
564     * @return char-th_rootOf(P), or null if no char-th root.
565     */
566    public abstract GenPolynomial<C> baseRootCharacteristic(GenPolynomial<C> P);
567
568
569    /**
570     * GenPolynomial char-th root univariate polynomial with polynomial
571     * coefficients.
572     * @param P recursive univariate GenPolynomial.
573     * @return char-th_rootOf(P), or null if P is no char-th root.
574     */
575    public abstract GenPolynomial<GenPolynomial<C>> recursiveUnivariateRootCharacteristic(
576                    GenPolynomial<GenPolynomial<C>> P);
577
578
579    /**
580     * Polynomial is char-th root.
581     * @param P polynomial.
582     * @param F = [p_1 -&gt; e_1, ..., p_k -&gt; e_k].
583     * @return true if P = prod_{i=1,...,k} p_i**(e_i*p), else false.
584     */
585    public boolean isCharRoot(GenPolynomial<C> P, SortedMap<GenPolynomial<C>, Long> F) {
586        if (P == null || F == null) {
587            throw new IllegalArgumentException("P and F may not be null");
588        }
589        if (P.isZERO() && F.size() == 0) {
590            return true;
591        }
592        GenPolynomial<C> t = P.ring.getONE();
593        long p = P.ring.characteristic().longValue();
594        for (Map.Entry<GenPolynomial<C>, Long> me : F.entrySet()) {
595            GenPolynomial<C> f = me.getKey();
596            Long E = me.getValue(); //F.get(f);
597            long e = E.longValue();
598            GenPolynomial<C> g = Power.<GenPolynomial<C>> positivePower(f, e);
599            if (!f.isConstant()) {
600                g = Power.<GenPolynomial<C>> positivePower(g, p);
601            }
602            t = t.multiply(g);
603        }
604        boolean f = P.equals(t) || P.equals(t.negate());
605        if (!f) {
606            System.out.println("\nfactorization(map): " + f);
607            System.out.println("P = " + P);
608            System.out.println("t = " + t);
609            P = P.monic();
610            t = t.monic();
611            f = P.equals(t) || P.equals(t.negate());
612            if (f) {
613                return f;
614            }
615            System.out.println("\nfactorization(map): " + f);
616            System.out.println("P = " + P);
617            System.out.println("t = " + t);
618        }
619        return f;
620    }
621
622
623    /**
624     * Recursive polynomial is char-th root.
625     * @param P recursive polynomial.
626     * @param F = [p_1 -&gt; e_1, ..., p_k -&gt; e_k].
627     * @return true if P = prod_{i=1,...,k} p_i**(e_i*p), else false.
628     */
629    public boolean isRecursiveCharRoot(GenPolynomial<GenPolynomial<C>> P,
630                    SortedMap<GenPolynomial<GenPolynomial<C>>, Long> F) {
631        if (P == null || F == null) {
632            throw new IllegalArgumentException("P and F may not be null");
633        }
634        if (P.isZERO() && F.size() == 0) {
635            return true;
636        }
637        GenPolynomial<GenPolynomial<C>> t = P.ring.getONE();
638        long p = P.ring.characteristic().longValue();
639        for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> me : F.entrySet()) {
640            GenPolynomial<GenPolynomial<C>> f = me.getKey();
641            Long E = me.getValue(); //F.get(f);
642            long e = E.longValue();
643            GenPolynomial<GenPolynomial<C>> g = Power.<GenPolynomial<GenPolynomial<C>>> positivePower(f, e);
644            if (!f.isConstant()) {
645                g = Power.<GenPolynomial<GenPolynomial<C>>> positivePower(g, p);
646            }
647            t = t.multiply(g);
648        }
649        boolean f = P.equals(t) || P.equals(t.negate());
650        if (!f) {
651            System.out.println("\nfactorization(map): " + f);
652            System.out.println("P = " + P);
653            System.out.println("t = " + t);
654            P = P.monic();
655            t = t.monic();
656            f = P.equals(t) || P.equals(t.negate());
657            if (f) {
658                return f;
659            }
660            System.out.println("\nfactorization(map): " + f);
661            System.out.println("P = " + P);
662            System.out.println("t = " + t);
663        }
664        return f;
665    }
666
667
668    /**
669     * Recursive polynomial is char-th root.
670     * @param P recursive polynomial.
671     * @param r = recursive polynomial.
672     * @return true if P = r**p, else false.
673     */
674    public boolean isRecursiveCharRoot(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> r) {
675        if (P == null || r == null) {
676            throw new IllegalArgumentException("P and r may not be null");
677        }
678        if (P.isZERO() && r.isZERO()) {
679            return true;
680        }
681        long p = P.ring.characteristic().longValue();
682        GenPolynomial<GenPolynomial<C>> t = Power.<GenPolynomial<GenPolynomial<C>>> positivePower(r, p);
683
684        boolean f = P.equals(t) || P.equals(t.negate());
685        if (!f) {
686            System.out.println("\nisCharRoot: " + f);
687            System.out.println("P = " + P);
688            System.out.println("t = " + t);
689            P = P.monic();
690            t = t.monic();
691            f = P.equals(t) || P.equals(t.negate());
692            if (f) {
693                return f;
694            }
695            System.out.println("\nisCharRoot: " + f);
696            System.out.println("P = " + P);
697            System.out.println("t = " + t);
698        }
699        return f;
700    }
701
702}