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