Source code

001/*
002 * $Id: SquarefreeFieldCharP.java 6022 2020-11-24 10:56:01Z 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.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
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("characterisic(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 P = prod_{i=1,...,k}
142     *         p_i^{e_i} and p_i squarefree.
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            } else {
166                sfactors.put(A, 1L);
167            }
168            return sfactors;
169        }
170        if (pfac.nvar > 1) {
171            throw new IllegalArgumentException(
172                            this.getClass().getName() + " only for univariate polynomials");
173        }
174        C ldbcf = A.leadingBaseCoefficient();
175        if (!ldbcf.isONE()) {
176            A = A.divide(ldbcf);
177            SortedMap<C, Long> rfactors = squarefreeFactors(ldbcf);
178            //System.out.println("rfactors,ldbcf = " + rfactors);
179            if (rfactors != null && rfactors.size() > 0) {
180                for (Map.Entry<C, Long> me : rfactors.entrySet()) {
181                    C c = me.getKey();
182                    if (!c.isONE()) {
183                        GenPolynomial<C> cr = pfac.getONE().multiply(c);
184                        Long rk = me.getValue(); //rfactors.get(c);
185                        sfactors.put(cr, rk);
186                    }
187                }
188            } else {
189                GenPolynomial<C> f1 = pfac.getONE().multiply(ldbcf);
190                //System.out.println("gcda sqf f1 = " + f1);
191                sfactors.put(f1, 1L);
192            }
193            ldbcf = pfac.coFac.getONE();
194        }
195        // divide by trailing term
196        ExpVector et = A.trailingExpVector();
197        if (!et.isZERO()) {
198            GenPolynomial<C> tr = pfac.valueOf(et);
199            if (logger.isInfoEnabled()) {
200               logger.info("trailing term = " + tr);
201            }
202            A = PolyUtil.<C> basePseudoDivide(A, tr);
203            long ep = et.getVal(0); // univariate
204            et = et.subst(0,1);
205            tr = pfac.valueOf(et);
206            if (logger.isInfoEnabled()) {
207               logger.info("tr, ep = " + tr + ", " + ep);
208            }
209            sfactors.put(tr, ep);
210            if (A.length() == 1) {
211                return sfactors;
212            }
213        }
214        GenPolynomial<C> T0 = A;
215        long e = 1L;
216        GenPolynomial<C> Tp;
217        GenPolynomial<C> T = null;
218        GenPolynomial<C> V = null;
219        long k = 0L;
220        long mp = 0L;
221        boolean init = true;
222        while (true) {
223            //System.out.println("T0 = " + T0);
224            if (init) {
225                if (T0.isConstant() || T0.isZERO()) {
226                    break;
227                }
228                Tp = PolyUtil.<C> baseDeriviative(T0);
229                T = engine.baseGcd(T0, Tp);
230                T = T.monic();
231                V = PolyUtil.<C> basePseudoDivide(T0, T);
232                //System.out.println("iT0 = " + T0);
233                //System.out.println("iTp = " + Tp);
234                //System.out.println("iT  = " + T);
235                //System.out.println("iV  = " + V);
236                //System.out.println("const(iV)  = " + V.isConstant());
237                k = 0L;
238                mp = 0L;
239                init = false;
240            }
241            if (V.isConstant()) {
242                mp = pfac.characteristic().longValue(); // assert != 0
243                //T0 = PolyUtil.<C> baseModRoot(T,mp);
244                T0 = baseRootCharacteristic(T);
245                logger.info("char root: T0 = " + T0 + ", T = " + T);
246                if (T0 == null) {
247                    //break;
248                    T0 = pfac.getZERO();
249                }
250                e = e * mp;
251                init = true;
252                continue;
253            }
254            k++;
255            if (mp != 0L && k % mp == 0L) {
256                T = PolyUtil.<C> basePseudoDivide(T, V);
257                System.out.println("k = " + k);
258                //System.out.println("T = " + T);
259                k++;
260            }
261            GenPolynomial<C> W = engine.baseGcd(T, V);
262            W = W.monic();
263            GenPolynomial<C> z = PolyUtil.<C> basePseudoDivide(V, W);
264            //System.out.println("W = " + W);
265            //System.out.println("z = " + z);
266            V = W;
267            T = PolyUtil.<C> basePseudoDivide(T, V);
268            //System.out.println("V = " + V);
269            //System.out.println("T = " + T);
270            if (z.degree(0) > 0) {
271                if (ldbcf.isONE() && !z.leadingBaseCoefficient().isONE()) {
272                    z = z.monic();
273                    //logger.info("z,monic = " + z);
274                }
275                logger.info("z, k = " + z + ", " + k);
276                sfactors.put(z, (e * k));
277            }
278        }
279        logger.info("exit char root: T0 = " + T0 + ", T = " + T);
280        return sfactors;
281    }
282
283
284    /**
285     * GenPolynomial recursive univariate polynomial greatest squarefree
286     * divisor.
287     * @param P recursive univariate GenPolynomial.
288     * @return squarefree(pp(P)).
289     */
290    @Override
291    public GenPolynomial<GenPolynomial<C>> recursiveUnivariateSquarefreePart(
292                    GenPolynomial<GenPolynomial<C>> P) {
293        if (P == null || P.isZERO()) {
294            return P;
295        }
296        GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
297        if (pfac.nvar > 1) {
298            throw new IllegalArgumentException(
299                            this.getClass().getName() + " only for univariate polynomials");
300        }
301        GenPolynomial<GenPolynomial<C>> s = pfac.getONE();
302        SortedMap<GenPolynomial<GenPolynomial<C>>, Long> factors = recursiveUnivariateSquarefreeFactors(P);
303        if (logger.isWarnEnabled()) {
304            logger.info("sqfPart, better use sqfFactors, factors = " + factors);
305        }
306        for (GenPolynomial<GenPolynomial<C>> sp : factors.keySet()) {
307            s = s.multiply(sp);
308        }
309        s = PolyUtil.<C> monic(s);
310        return s;
311    }
312
313
314    /**
315     * GenPolynomial recursive univariate polynomial squarefree factorization.
316     * @param P recursive univariate GenPolynomial.
317     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
318     *         p_i^{e_i} and p_i squarefree.
319     */
320    @Override
321    public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveUnivariateSquarefreeFactors(
322                    GenPolynomial<GenPolynomial<C>> P) {
323        SortedMap<GenPolynomial<GenPolynomial<C>>, Long> sfactors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>();
324        if (P == null || P.isZERO()) {
325            return sfactors;
326        }
327        GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
328        if (pfac.nvar > 1) {
329            // recursiveContent not possible by return type
330            throw new IllegalArgumentException(
331                            this.getClass().getName() + " only for univariate polynomials");
332        }
333        // if base coefficient ring is a field, make monic
334        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac;
335        C ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient();
336        if (!ldbcf.isONE()) {
337            GenPolynomial<C> lc = cfac.getONE().multiply(ldbcf);
338            GenPolynomial<GenPolynomial<C>> pl = pfac.getONE().multiply(lc);
339            sfactors.put(pl, 1L);
340            C li = ldbcf.inverse();
341            //System.out.println("li = " + li);
342            P = P.multiply(cfac.getONE().multiply(li));
343            //System.out.println("P,monic = " + P);
344            ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient();
345            if (debug) {
346                logger.debug("new ldbcf: " + ldbcf);
347            }
348        }
349        // factors of content
350        GenPolynomial<C> Pc = engine.recursiveContent(P);
351        if (logger.isInfoEnabled()) {
352            logger.info("Pc = " + Pc);
353        }
354        Pc = Pc.monic();
355        if (!Pc.isONE()) {
356            P = PolyUtil.<C> coefficientPseudoDivide(P, Pc);
357        }
358        SortedMap<GenPolynomial<C>, Long> rsf = squarefreeFactors(Pc);
359        if (logger.isInfoEnabled()) {
360            logger.info("rsf = " + rsf);
361        }
362        // add factors of content
363        for (Map.Entry<GenPolynomial<C>, Long> me : rsf.entrySet()) {
364            GenPolynomial<C> c = me.getKey();
365            if (!c.isONE()) {
366                GenPolynomial<GenPolynomial<C>> cr = pfac.getONE().multiply(c);
367                Long rk = me.getValue(); //rsf.get(c);
368                sfactors.put(cr, rk);
369            }
370        }
371        // divide by trailing term
372        ExpVector et = P.trailingExpVector();
373        if (!et.isZERO()) {
374            GenPolynomial<GenPolynomial<C>> tr = pfac.valueOf(et);
375            if (logger.isInfoEnabled()) {
376                logger.info("trailing term = " + tr);
377            }
378            P = PolyUtil.<C> recursivePseudoDivide(P, tr);
379            long ep = et.getVal(0); // univariate
380            et = et.subst(0, 1);
381            tr = pfac.valueOf(et);
382            sfactors.put(tr, ep);
383        }
384
385        // factors of recursive polynomial
386        GenPolynomial<GenPolynomial<C>> T0 = P;
387        long e = 1L;
388        GenPolynomial<GenPolynomial<C>> Tp;
389        GenPolynomial<GenPolynomial<C>> T = null;
390        GenPolynomial<GenPolynomial<C>> V = null;
391        long k = 0L;
392        long mp = 0L;
393        boolean init = true;
394        while (true) {
395            if (init) {
396                if (T0.isConstant() || T0.isZERO()) {
397                    break;
398                }
399                Tp = PolyUtil.<C> recursiveDeriviative(T0);
400                //System.out.println("iT0 = " + T0);
401                //System.out.println("iTp = " + Tp);
402                T = engine.recursiveUnivariateGcd(T0, Tp);
403                T = PolyUtil.<C> monic(T);
404                V = PolyUtil.<C> recursivePseudoDivide(T0, T);
405                //System.out.println("iT = " + T);
406                //System.out.println("iV = " + V);
407                k = 0L;
408                mp = 0L;
409                init = false;
410            }
411            if (V.isConstant()) {
412                mp = pfac.characteristic().longValue(); // assert != 0
413                //T0 = PolyUtil.<C> recursiveModRoot(T,mp);
414                T0 = recursiveUnivariateRootCharacteristic(T);
415                logger.info("char root: T0r = " + T0 + ", Tr = " + T);
416                if (T0 == null) {
417                    //break;
418                    T0 = pfac.getZERO();
419                }
420                e = e * mp;
421                init = true;
422                //continue;
423            }
424            k++;
425            if (mp != 0L && k % mp == 0L) {
426                T = PolyUtil.<C> recursivePseudoDivide(T, V);
427                System.out.println("k = " + k);
428                //System.out.println("T = " + T);
429                k++;
430            }
431            GenPolynomial<GenPolynomial<C>> W = engine.recursiveUnivariateGcd(T, V);
432            W = PolyUtil.<C> monic(W);
433            GenPolynomial<GenPolynomial<C>> z = PolyUtil.<C> recursivePseudoDivide(V, W);
434            //System.out.println("W = " + W);
435            //System.out.println("z = " + z);
436            V = W;
437            T = PolyUtil.<C> recursivePseudoDivide(T, V);
438            //System.out.println("V = " + V);
439            //System.out.println("T = " + T);
440            //was: if ( z.degree(0) > 0 ) {
441            if (!z.isONE() && !z.isZERO()) {
442                z = PolyUtil.<C> monic(z);
443                logger.info("z,put = " + z);
444                sfactors.put(z, (e * k));
445            }
446        }
447        logger.info("exit char root: T0 = " + T0 + ", T = " + T);
448        if (sfactors.size() == 0) {
449            sfactors.put(pfac.getONE(), 1L);
450        }
451        return sfactors;
452    }
453
454
455    /**
456     * GenPolynomial greatest squarefree divisor.
457     * @param P GenPolynomial.
458     * @return squarefree(pp(P)).
459     */
460    @Override
461    public GenPolynomial<C> squarefreePart(GenPolynomial<C> P) {
462        if (P == null) {
463            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
464        }
465        if (P.isZERO()) {
466            return P;
467        }
468        GenPolynomialRing<C> pfac = P.ring;
469        if (pfac.nvar <= 1) {
470            return baseSquarefreePart(P);
471        }
472        GenPolynomial<C> s = pfac.getONE();
473        SortedMap<GenPolynomial<C>, Long> factors = squarefreeFactors(P);
474        if (logger.isWarnEnabled()) {
475            logger.info("sqfPart, better use sqfFactors, factors = " + factors);
476        }
477        for (GenPolynomial<C> sp : factors.keySet()) {
478            if (sp.isConstant()) {
479                continue;
480            }
481            s = s.multiply(sp);
482        }
483        return s.monic();
484    }
485
486
487    /**
488     * GenPolynomial squarefree factorization.
489     * @param P GenPolynomial.
490     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
491     *         p_i^{e_i} and p_i squarefree.
492     */
493    @Override
494    public SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P) {
495        if (P == null) {
496            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
497        }
498        GenPolynomialRing<C> pfac = P.ring;
499        if (pfac.nvar <= 1) {
500            return baseSquarefreeFactors(P);
501        }
502        SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>();
503        if (P.isZERO()) {
504            return sfactors;
505        }
506        if (P.isONE()) {
507            sfactors.put(P, 1L);
508            return sfactors;
509        }
510        GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1);
511        GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P);
512        SortedMap<GenPolynomial<GenPolynomial<C>>, Long> PP = recursiveUnivariateSquarefreeFactors(Pr);
513        for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> m : PP.entrySet()) {
514            Long i = m.getValue();
515            GenPolynomial<GenPolynomial<C>> Dr = m.getKey();
516            GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, Dr);
517            sfactors.put(D, i);
518        }
519        return sfactors;
520    }
521
522
523    /**
524     * Coefficient squarefree factorization.
525     * @param coeff coefficient.
526     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
527     *         p_i^{e_i} and p_i squarefree.
528     */
529    @SuppressWarnings("unchecked")
530    @Override
531    public SortedMap<C, Long> squarefreeFactors(C coeff) {
532        if (coeff == null) {
533            return null;
534        }
535        SortedMap<C, Long> factors = new TreeMap<C, Long>();
536        RingFactory<C> cfac = (RingFactory<C>) coeff.factory();
537        if (aCoFac != null) {
538            AlgebraicNumber<C> an = (AlgebraicNumber<C>) (Object) coeff;
539            if (cfac.isFinite()) {
540                SquarefreeFiniteFieldCharP<C> reng = (SquarefreeFiniteFieldCharP) SquarefreeFactory
541                                .getImplementation(cfac);
542                SortedMap<C, Long> rfactors = reng.rootCharacteristic(coeff); // ??
543                logger.info("rfactors,finite = " + rfactors);
544                factors.putAll(rfactors);
545                //return factors;
546            } else {
547                SquarefreeInfiniteAlgebraicFieldCharP<C> reng = (SquarefreeInfiniteAlgebraicFieldCharP) SquarefreeFactory
548                                .getImplementation(cfac);
549                SortedMap<AlgebraicNumber<C>, Long> rfactors = reng.squarefreeFactors(an);
550                logger.info("rfactors,infinite,algeb = " + rfactors);
551                for (Map.Entry<AlgebraicNumber<C>, Long> me : rfactors.entrySet()) {
552                    AlgebraicNumber<C> c = me.getKey();
553                    if (!c.isONE()) {
554                        C cr = (C) (Object) c;
555                        Long rk = me.getValue();
556                        factors.put(cr, rk);
557                    }
558                }
559            }
560        } else if (qCoFac != null) {
561            Quotient<C> q = (Quotient<C>) (Object) coeff;
562            SquarefreeInfiniteFieldCharP<C> reng = (SquarefreeInfiniteFieldCharP) SquarefreeFactory
563                            .getImplementation(cfac);
564            SortedMap<Quotient<C>, Long> rfactors = reng.squarefreeFactors(q);
565            logger.info("rfactors,infinite = " + rfactors);
566            for (Map.Entry<Quotient<C>, Long> me : rfactors.entrySet()) {
567                Quotient<C> c = me.getKey();
568                if (!c.isONE()) {
569                    C cr = (C) (Object) c;
570                    Long rk = me.getValue();
571                    factors.put(cr, rk);
572                }
573            }
574        } else if (cfac.isFinite()) {
575            SquarefreeFiniteFieldCharP<C> reng = (SquarefreeFiniteFieldCharP) SquarefreeFactory
576                            .getImplementation(cfac);
577            SortedMap<C, Long> rfactors = reng.rootCharacteristic(coeff); // ??
578            logger.info("rfactors,finite = " + rfactors);
579            factors.putAll(rfactors);
580            //return factors;
581        } else {
582            logger.warn("case " + cfac + " not implemented");
583        }
584        return factors;
585    }
586
587
588    /* --------- char-th roots --------------------- */
589
590
591    /**
592     * GenPolynomial char-th root univariate polynomial.
593     * @param P GenPolynomial.
594     * @return char-th_rootOf(P), or null if no char-th root.
595     */
596    public abstract GenPolynomial<C> baseRootCharacteristic(GenPolynomial<C> P);
597
598
599    /**
600     * GenPolynomial char-th root univariate polynomial with polynomial
601     * coefficients.
602     * @param P recursive univariate GenPolynomial.
603     * @return char-th_rootOf(P), or null if P is no char-th root.
604     */
605    public abstract GenPolynomial<GenPolynomial<C>> recursiveUnivariateRootCharacteristic(
606                    GenPolynomial<GenPolynomial<C>> P);
607
608
609    /**
610     * Polynomial is char-th root.
611     * @param P polynomial.
612     * @param F = [p_1 -&gt; e_1, ..., p_k -&gt; e_k].
613     * @return true if P = prod_{i=1,...,k} p_i**(e_i*p), else false.
614     */
615    public boolean isCharRoot(GenPolynomial<C> P, SortedMap<GenPolynomial<C>, Long> F) {
616        if (P == null || F == null) {
617            throw new IllegalArgumentException("P and F may not be null");
618        }
619        if (P.isZERO() && F.size() == 0) {
620            return true;
621        }
622        GenPolynomial<C> t = P.ring.getONE();
623        long p = P.ring.characteristic().longValue();
624        for (Map.Entry<GenPolynomial<C>, Long> me : F.entrySet()) {
625            GenPolynomial<C> f = me.getKey();
626            Long E = me.getValue();
627            long e = E.longValue();
628            GenPolynomial<C> g = f.power(e);
629            if (!f.isConstant()) {
630                g = g.power(p);
631            }
632            t = t.multiply(g);
633        }
634        boolean f = P.equals(t) || P.equals(t.negate());
635        if (!f) {
636            System.out.println("\nfactorization(map): " + f);
637            System.out.println("P = " + P);
638            System.out.println("t = " + t);
639            P = P.monic();
640            t = t.monic();
641            f = P.equals(t) || P.equals(t.negate());
642            if (f) {
643                return f;
644            }
645            System.out.println("\nfactorization(map): " + f);
646            System.out.println("P = " + P);
647            System.out.println("t = " + t);
648        }
649        return f;
650    }
651
652
653    /**
654     * Recursive polynomial is char-th root.
655     * @param P recursive polynomial.
656     * @param F = [p_1 -&gt; e_1, ..., p_k -&gt; e_k].
657     * @return true if P = prod_{i=1,...,k} p_i**(e_i*p), else false.
658     */
659    public boolean isRecursiveCharRoot(GenPolynomial<GenPolynomial<C>> P,
660                    SortedMap<GenPolynomial<GenPolynomial<C>>, Long> F) {
661        if (P == null || F == null) {
662            throw new IllegalArgumentException("P and F may not be null");
663        }
664        if (P.isZERO() && F.size() == 0) {
665            return true;
666        }
667        GenPolynomial<GenPolynomial<C>> t = P.ring.getONE();
668        long p = P.ring.characteristic().longValue();
669        for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> me : F.entrySet()) {
670            GenPolynomial<GenPolynomial<C>> f = me.getKey();
671            Long E = me.getValue();
672            long e = E.longValue();
673            GenPolynomial<GenPolynomial<C>> g = f.power(e);
674            if (!f.isConstant()) {
675                g = g.power(p);
676            }
677            t = t.multiply(g);
678        }
679        boolean f = P.equals(t) || P.equals(t.negate());
680        if (!f) {
681            System.out.println("\nfactorization(map): " + f);
682            System.out.println("P = " + P);
683            System.out.println("t = " + t);
684            P = P.monic();
685            t = t.monic();
686            f = P.equals(t) || P.equals(t.negate());
687            if (f) {
688                return f;
689            }
690            System.out.println("\nfactorization(map): " + f);
691            System.out.println("P = " + P);
692            System.out.println("t = " + t);
693        }
694        return f;
695    }
696
697
698    /**
699     * Recursive polynomial is char-th root.
700     * @param P recursive polynomial.
701     * @param r = recursive polynomial.
702     * @return true if P = r**p, else false.
703     */
704    public boolean isRecursiveCharRoot(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> r) {
705        if (P == null || r == null) {
706            throw new IllegalArgumentException("P and r may not be null");
707        }
708        if (P.isZERO() && r.isZERO()) {
709            return true;
710        }
711        long p = P.ring.characteristic().longValue();
712        GenPolynomial<GenPolynomial<C>> t = r.power(p);
713
714        boolean f = P.equals(t) || P.equals(t.negate());
715        if (!f) {
716            System.out.println("\nisCharRoot: " + f);
717            System.out.println("P = " + P);
718            System.out.println("t = " + t);
719            P = P.monic();
720            t = t.monic();
721            f = P.equals(t) || P.equals(t.negate());
722            if (f) {
723                return f;
724            }
725            System.out.println("\nisCharRoot: " + f);
726            System.out.println("P = " + P);
727            System.out.println("t = " + t);
728        }
729        return f;
730    }
731
732}