Source code

001/*
002 * $Id: SquarefreeFieldCharP.java 4965 2014-10-17 20:07:51Z 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        if (P.isONE()) {
479            sfactors.put(P, 1L);
480            return sfactors;
481        }
482        GenPolynomialRing<C> cfac = pfac.contract(1);
483        GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, 1);
484
485        GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P);
486        SortedMap<GenPolynomial<GenPolynomial<C>>, Long> PP = recursiveUnivariateSquarefreeFactors(Pr);
487
488        for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> m : PP.entrySet()) {
489            Long i = m.getValue();
490            GenPolynomial<GenPolynomial<C>> Dr = m.getKey();
491            GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, Dr);
492            sfactors.put(D, i);
493        }
494        return sfactors;
495    }
496
497
498    /**
499     * Coefficient squarefree factorization.
500     * @param coeff coefficient.
501     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
502     *         p_i^{e_i} and p_i squarefree.
503     */
504    @SuppressWarnings("cast")
505    @Override
506    public SortedMap<C, Long> squarefreeFactors(C coeff) {
507        if (coeff == null) {
508            return null;
509        }
510        SortedMap<C, Long> factors = new TreeMap<C, Long>();
511        RingFactory<C> cfac = (RingFactory<C>) coeff.factory();
512        if (aCoFac != null) {
513            AlgebraicNumber<C> an = (AlgebraicNumber<C>) (Object) coeff;
514            if (cfac.isFinite()) {
515                SquarefreeFiniteFieldCharP<C> reng = (SquarefreeFiniteFieldCharP) SquarefreeFactory
516                                .getImplementation(cfac);
517                SortedMap<C, Long> rfactors = reng.rootCharacteristic(coeff); // ??
518                logger.info("rfactors,finite = " + rfactors);
519                factors.putAll(rfactors);
520                //return factors;
521            } else {
522                SquarefreeInfiniteAlgebraicFieldCharP<C> reng = (SquarefreeInfiniteAlgebraicFieldCharP) SquarefreeFactory
523                                .getImplementation(cfac);
524                SortedMap<AlgebraicNumber<C>, Long> rfactors = reng.squarefreeFactors(an);
525                logger.info("rfactors,infinite,algeb = " + rfactors);
526                for (Map.Entry<AlgebraicNumber<C>, Long> me : rfactors.entrySet()) {
527                    AlgebraicNumber<C> c = me.getKey();
528                    if (!c.isONE()) {
529                        C cr = (C) (Object) c;
530                        Long rk = me.getValue(); // rfactors.get(c);
531                        factors.put(cr, rk);
532                    }
533                }
534            }
535        } else if (qCoFac != null) {
536            Quotient<C> q = (Quotient<C>) (Object) coeff;
537            SquarefreeInfiniteFieldCharP<C> reng = (SquarefreeInfiniteFieldCharP) SquarefreeFactory
538                            .getImplementation(cfac);
539            SortedMap<Quotient<C>, Long> rfactors = reng.squarefreeFactors(q);
540            logger.info("rfactors,infinite = " + rfactors);
541            for (Map.Entry<Quotient<C>, Long> me : rfactors.entrySet()) {
542                Quotient<C> c = me.getKey();
543                if (!c.isONE()) {
544                    C cr = (C) (Object) c;
545                    Long rk = me.getValue(); //rfactors.get(c);
546                    factors.put(cr, rk);
547                }
548            }
549        } else if (cfac.isFinite()) {
550            SquarefreeFiniteFieldCharP<C> reng = (SquarefreeFiniteFieldCharP) SquarefreeFactory
551                            .getImplementation(cfac);
552            SortedMap<C, Long> rfactors = reng.rootCharacteristic(coeff); // ??
553            logger.info("rfactors,finite = " + rfactors);
554            factors.putAll(rfactors);
555            //return factors;
556        } else {
557            logger.warn("case " + cfac + " not implemented");
558        }
559        return factors;
560    }
561
562
563    /* --------- char-th roots --------------------- */
564
565
566    /**
567     * GenPolynomial char-th root univariate polynomial.
568     * @param P GenPolynomial.
569     * @return char-th_rootOf(P), or null if no char-th root.
570     */
571    public abstract GenPolynomial<C> baseRootCharacteristic(GenPolynomial<C> P);
572
573
574    /**
575     * GenPolynomial char-th root univariate polynomial with polynomial
576     * coefficients.
577     * @param P recursive univariate GenPolynomial.
578     * @return char-th_rootOf(P), or null if P is no char-th root.
579     */
580    public abstract GenPolynomial<GenPolynomial<C>> recursiveUnivariateRootCharacteristic(
581                    GenPolynomial<GenPolynomial<C>> P);
582
583
584    /**
585     * Polynomial is char-th root.
586     * @param P polynomial.
587     * @param F = [p_1 -&gt; e_1, ..., p_k -&gt; e_k].
588     * @return true if P = prod_{i=1,...,k} p_i**(e_i*p), else false.
589     */
590    public boolean isCharRoot(GenPolynomial<C> P, SortedMap<GenPolynomial<C>, Long> F) {
591        if (P == null || F == null) {
592            throw new IllegalArgumentException("P and F may not be null");
593        }
594        if (P.isZERO() && F.size() == 0) {
595            return true;
596        }
597        GenPolynomial<C> t = P.ring.getONE();
598        long p = P.ring.characteristic().longValue();
599        for (Map.Entry<GenPolynomial<C>, Long> me : F.entrySet()) {
600            GenPolynomial<C> f = me.getKey();
601            Long E = me.getValue(); //F.get(f);
602            long e = E.longValue();
603            GenPolynomial<C> g = Power.<GenPolynomial<C>> positivePower(f, e);
604            if (!f.isConstant()) {
605                g = Power.<GenPolynomial<C>> positivePower(g, p);
606            }
607            t = t.multiply(g);
608        }
609        boolean f = P.equals(t) || P.equals(t.negate());
610        if (!f) {
611            System.out.println("\nfactorization(map): " + f);
612            System.out.println("P = " + P);
613            System.out.println("t = " + t);
614            P = P.monic();
615            t = t.monic();
616            f = P.equals(t) || P.equals(t.negate());
617            if (f) {
618                return f;
619            }
620            System.out.println("\nfactorization(map): " + f);
621            System.out.println("P = " + P);
622            System.out.println("t = " + t);
623        }
624        return f;
625    }
626
627
628    /**
629     * Recursive polynomial is char-th root.
630     * @param P recursive polynomial.
631     * @param F = [p_1 -&gt; e_1, ..., p_k -&gt; e_k].
632     * @return true if P = prod_{i=1,...,k} p_i**(e_i*p), else false.
633     */
634    public boolean isRecursiveCharRoot(GenPolynomial<GenPolynomial<C>> P,
635                    SortedMap<GenPolynomial<GenPolynomial<C>>, Long> F) {
636        if (P == null || F == null) {
637            throw new IllegalArgumentException("P and F may not be null");
638        }
639        if (P.isZERO() && F.size() == 0) {
640            return true;
641        }
642        GenPolynomial<GenPolynomial<C>> t = P.ring.getONE();
643        long p = P.ring.characteristic().longValue();
644        for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> me : F.entrySet()) {
645            GenPolynomial<GenPolynomial<C>> f = me.getKey();
646            Long E = me.getValue(); //F.get(f);
647            long e = E.longValue();
648            GenPolynomial<GenPolynomial<C>> g = Power.<GenPolynomial<GenPolynomial<C>>> positivePower(f, e);
649            if (!f.isConstant()) {
650                g = Power.<GenPolynomial<GenPolynomial<C>>> positivePower(g, p);
651            }
652            t = t.multiply(g);
653        }
654        boolean f = P.equals(t) || P.equals(t.negate());
655        if (!f) {
656            System.out.println("\nfactorization(map): " + f);
657            System.out.println("P = " + P);
658            System.out.println("t = " + t);
659            P = P.monic();
660            t = t.monic();
661            f = P.equals(t) || P.equals(t.negate());
662            if (f) {
663                return f;
664            }
665            System.out.println("\nfactorization(map): " + f);
666            System.out.println("P = " + P);
667            System.out.println("t = " + t);
668        }
669        return f;
670    }
671
672
673    /**
674     * Recursive polynomial is char-th root.
675     * @param P recursive polynomial.
676     * @param r = recursive polynomial.
677     * @return true if P = r**p, else false.
678     */
679    public boolean isRecursiveCharRoot(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> r) {
680        if (P == null || r == null) {
681            throw new IllegalArgumentException("P and r may not be null");
682        }
683        if (P.isZERO() && r.isZERO()) {
684            return true;
685        }
686        long p = P.ring.characteristic().longValue();
687        GenPolynomial<GenPolynomial<C>> t = Power.<GenPolynomial<GenPolynomial<C>>> positivePower(r, p);
688
689        boolean f = P.equals(t) || P.equals(t.negate());
690        if (!f) {
691            System.out.println("\nisCharRoot: " + f);
692            System.out.println("P = " + P);
693            System.out.println("t = " + t);
694            P = P.monic();
695            t = t.monic();
696            f = P.equals(t) || P.equals(t.negate());
697            if (f) {
698                return f;
699            }
700            System.out.println("\nisCharRoot: " + f);
701            System.out.println("P = " + P);
702            System.out.println("t = " + t);
703        }
704        return f;
705    }
706
707}