001/*
002 * $Id$
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.Map;
011import java.util.SortedMap;
012import java.util.TreeMap;
013import java.util.Set;
014import java.util.HashSet;
015
016import org.apache.logging.log4j.LogManager;
017import org.apache.logging.log4j.Logger;
018
019import edu.jas.poly.GenPolynomial;
020import edu.jas.poly.GenPolynomialRing;
021import edu.jas.poly.PolyUtil;
022import edu.jas.structure.GcdRingElem;
023import edu.jas.structure.RingFactory;
024
025
026/**
027 * Abstract squarefree decomposition class.
028 * @author Heinz Kredel
029 */
030
031public abstract class SquarefreeAbstract<C extends GcdRingElem<C>> implements Squarefree<C> {
032
033
034    private static final Logger logger = LogManager.getLogger(SquarefreeAbstract.class);
035
036
037    /**
038     * GCD engine for respective base coefficients.
039     */
040    protected final GreatestCommonDivisorAbstract<C> engine;
041
042
043    /**
044     * Constructor.
045     */
046    public SquarefreeAbstract(GreatestCommonDivisorAbstract<C> engine) {
047        this.engine = engine;
048    }
049
050
051    /**
052     * GenPolynomial polynomial greatest squarefree divisor.
053     * @param P GenPolynomial.
054     * @return squarefree(pp(P)).
055     */
056    public abstract GenPolynomial<C> baseSquarefreePart(GenPolynomial<C> P);
057
058
059    /**
060     * GenPolynomial polynomial squarefree factorization.
061     * @param A GenPolynomial.
062     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with A = prod_{i=1,...,k}
063     *         p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j.
064     */
065    public abstract SortedMap<GenPolynomial<C>, Long> baseSquarefreeFactors(GenPolynomial<C> A);
066
067
068    /**
069     * GenPolynomial recursive polynomial greatest squarefree divisor.
070     * @param P recursive univariate GenPolynomial.
071     * @return squarefree(pp(P)).
072     */
073    public abstract GenPolynomial<GenPolynomial<C>> recursiveUnivariateSquarefreePart(
074                    GenPolynomial<GenPolynomial<C>> P);
075
076
077    /**
078     * GenPolynomial recursive univariate polynomial squarefree factorization.
079     * @param P recursive univariate GenPolynomial.
080     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
081     *         p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j.
082     */
083    public abstract SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveUnivariateSquarefreeFactors(
084                    GenPolynomial<GenPolynomial<C>> P);
085
086
087    /**
088     * GenPolynomial greatest squarefree divisor.
089     * @param P GenPolynomial.
090     * @return squarefree(P) a primitive respectively monic polynomial.
091     */
092    public abstract GenPolynomial<C> squarefreePart(GenPolynomial<C> P);
093
094
095    /**
096     * GenPolynomial test if is squarefree.
097     * @param P GenPolynomial.
098     * @return true if P is squarefree, else false.
099     */
100    public boolean isSquarefree(GenPolynomial<C> P) {
101        SortedMap<GenPolynomial<C>, Long> sm = squarefreeFactors(P);
102        Set<Long> ex = new HashSet<Long>( sm.values() );
103        //System.out.println("exponents: " + ex + ", sm = " + sm + ", P = " + P);
104        if (ex.size() != 1) {
105            return false;
106        }
107        if (ex.contains(Long.valueOf(1L))) {
108            return true;
109        }
110        return false;
111    }
112
113
114    /*public*/ boolean isSquarefreeAlternative(GenPolynomial<C> P) {
115        GenPolynomial<C> S = squarefreePart(P);
116        GenPolynomial<C> Ps = P;
117        if (P.ring.coFac.isField()) {
118            Ps = Ps.monic();
119        } else {
120            Ps = engine.basePrimitivePart(Ps);
121        }
122        boolean f = Ps.equals(S);
123        return f;
124    }
125
126
127    /**
128     * GenPolynomial list test if squarefree.
129     * @param L list of GenPolynomial.
130     * @return true if each P in L is squarefree, else false.
131     */
132    public boolean isSquarefree(List<GenPolynomial<C>> L) {
133        if (L == null || L.isEmpty()) {
134            return true;
135        }
136        for (GenPolynomial<C> P : L) {
137            if (!isSquarefree(P)) {
138                return false;
139            }
140        }
141        return true;
142    }
143
144
145    /**
146     * Recursive GenPolynomial test if is squarefree.
147     * @param P recursive univariate GenPolynomial.
148     * @return true if P is squarefree, else false.
149     */
150    public boolean isRecursiveSquarefree(GenPolynomial<GenPolynomial<C>> P) {
151        GenPolynomial<GenPolynomial<C>> S = recursiveUnivariateSquarefreePart(P);
152        boolean f = P.equals(S);
153        if (!f) {
154            logger.info("not Squarefree, S != P: {} != {}", P, S);
155        }
156        return f;
157    }
158
159
160    /**
161     * GenPolynomial squarefree factorization.
162     * @param P GenPolynomial.
163     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
164     *         p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j.
165     */
166    public abstract SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P);
167
168
169    /**
170     * GenPolynomial squarefree and co-prime list.
171     * @param A list of GenPolynomials.
172     * @return B with gcd(b,c) = 1 for all b != c in B and for all non-constant
173     *         a in A there exists b in B with b|a and each b in B is
174     *         squarefree. B does not contain zero or constant polynomials.
175     */
176    public List<GenPolynomial<C>> coPrimeSquarefree(List<GenPolynomial<C>> A) {
177        if (A == null || A.isEmpty()) {
178            return A;
179        }
180        List<GenPolynomial<C>> S = new ArrayList<GenPolynomial<C>>();
181        for (GenPolynomial<C> g : A) {
182            SortedMap<GenPolynomial<C>, Long> sm = squarefreeFactors(g);
183            S.addAll(sm.keySet());
184        }
185        List<GenPolynomial<C>> B = engine.coPrime(S);
186        return B;
187    }
188
189
190    /**
191     * GenPolynomial squarefree and co-prime list.
192     * @param a polynomial.
193     * @param P squarefree co-prime list of GenPolynomials.
194     * @return B with gcd(b,c) = 1 for all b != c in B and for non-constant a
195     *         there exists b in P with b|a. B does not contain zero or constant
196     *         polynomials.
197     */
198    public List<GenPolynomial<C>> coPrimeSquarefree(GenPolynomial<C> a, List<GenPolynomial<C>> P) {
199        if (a == null || a.isZERO() || a.isConstant()) {
200            return P;
201        }
202        SortedMap<GenPolynomial<C>, Long> sm = squarefreeFactors(a);
203        List<GenPolynomial<C>> B = P;
204        for (GenPolynomial<C> f : sm.keySet()) {
205            B = engine.coPrime(f, B);
206        }
207        return B;
208    }
209
210
211    /**
212     * Test if list of GenPolynomials is squarefree and co-prime.
213     * @param B list of GenPolynomials.
214     * @return true, if for all b != c in B gcd(b,c) = 1 and each b in B is
215     *         squarefree, else false.
216     */
217    public boolean isCoPrimeSquarefree(List<GenPolynomial<C>> B) {
218        if (B == null || B.isEmpty()) {
219            return true;
220        }
221        if (!engine.isCoPrime(B)) {
222            return false;
223        }
224        return isSquarefree(B);
225    }
226
227
228    /**
229     * Normalize factorization. p'_i &gt; 0 for i &gt; 1 and p'_1 != 1 if k &gt;
230     * 1.
231     * @param F = [p_1-&gt;e_1;, ..., p_k-&gt;e_k].
232     * @return F' = [p'_1-&gt;e_1, ..., p'_k-&gt;e_k].
233     */
234    public SortedMap<GenPolynomial<C>, Long> normalizeFactorization(SortedMap<GenPolynomial<C>, Long> F) {
235        if (F == null || F.size() <= 1) {
236            return F;
237        }
238        List<GenPolynomial<C>> Fp = new ArrayList<GenPolynomial<C>>(F.keySet());
239        GenPolynomial<C> f0 = Fp.get(0);
240        if (f0.ring.characteristic().signum() != 0) { // only ordered coefficients
241            return F;
242        }
243        long e0 = F.get(f0);
244        SortedMap<GenPolynomial<C>, Long> Sp = new TreeMap<GenPolynomial<C>, Long>();
245        for (int i = 1; i < Fp.size(); i++) {
246            GenPolynomial<C> fi = Fp.get(i);
247            long ei = F.get(fi);
248            if (fi.signum() < 0) {
249                //System.out.println("e0 = " + e0 + ", f0 = " + f0);
250                //System.out.println("ei = " + ei + ", fi = " + fi);
251                if (ei % 2 != 0 && e0 % 2 != 0) { // bug
252                    fi = fi.negate();
253                    f0 = f0.negate();
254                }
255            }
256            Sp.put(fi, ei);
257        }
258        if (!f0.isONE()) {
259            Sp.put(f0, e0);
260        }
261        return Sp;
262    }
263
264
265    /**
266     * GenPolynomial is (squarefree) factorization.
267     * @param P GenPolynomial.
268     * @param F = [p_1, ..., p_k].
269     * @return true if P = prod_{i=1,...,r} p_i, else false.
270     */
271    public boolean isFactorization(GenPolynomial<C> P, List<GenPolynomial<C>> F) {
272        if (P == null || F == null) {
273            throw new IllegalArgumentException("P and F may not be null");
274        }
275        if (P.isZERO() && F.size() == 0) {
276            return true;
277        }
278        GenPolynomial<C> t = P.ring.getONE();
279        for (GenPolynomial<C> f : F) {
280            t = t.multiply(f);
281        }
282        boolean f = P.equals(t) || P.equals(t.negate());
283        if (!f) {
284            logger.info("no factorization(list): F = {}, P = {}, t = {}", F, P, t);
285        }
286        return f;
287    }
288
289
290    /**
291     * Count number of factors in a (squarefree) factorization.
292     * @param F = [p_1 -&gt; e_1, ..., p_k -&gt; e_k].
293     * @return sum_{i=1,...,k} e_i.
294     */
295    public long factorCount(SortedMap<GenPolynomial<C>, Long> F) {
296        if (F == null || F.isEmpty()) {
297            return 0L;
298        }
299        long f = 0L;
300        for (Long e : F.values()) {
301            f += e;
302        }
303        return f;
304    }
305
306
307    /**
308     * GenPolynomial is (squarefree) factorization.
309     * @param P GenPolynomial.
310     * @param F = [p_1 -&gt; e_1, ..., p_k -&gt; e_k].
311     * @return true if P = prod_{i=1,...,k} p_i**e_i, else false.
312     */
313    public boolean isFactorization(GenPolynomial<C> P, SortedMap<GenPolynomial<C>, Long> F) {
314        if (P == null || F == null) {
315            throw new IllegalArgumentException("P and F may not be null");
316        }
317        if (P.isZERO() && F.size() == 0) {
318            return true;
319        }
320        GenPolynomial<C> t = P.ring.getONE();
321        for (Map.Entry<GenPolynomial<C>, Long> me : F.entrySet()) {
322            GenPolynomial<C> f = me.getKey();
323            Long E = me.getValue();
324            long e = E.longValue();
325            GenPolynomial<C> g = f.power(e);
326            t = t.multiply(g);
327        }
328        boolean f = P.equals(t) || P.equals(t.negate());
329        if (!f) {
330            P = P.monic();
331            t = t.monic();
332            f = P.equals(t) || P.equals(t.negate());
333            if (f) {
334                return f;
335            }
336            logger.info("no factorization(map): F = {}, P = {}, t = {}", F, P, t);
337            //RuntimeException e = new RuntimeException("fac-map");
338            //e.printStackTrace();
339            //throw e;
340        }
341        return f;
342    }
343
344
345    /**
346     * GenPolynomial is (squarefree) factorization.
347     * @param P GenPolynomial.
348     * @param F = [p_1 -&gt; e_1, ..., p_k -&gt; e_k].
349     * @return true if P = prod_{i=1,...,k} p_i**e_i, else false.
350     */
351    public boolean isRecursiveFactorization(GenPolynomial<GenPolynomial<C>> P,
352                    SortedMap<GenPolynomial<GenPolynomial<C>>, Long> F) {
353        if (P == null || F == null) {
354            throw new IllegalArgumentException("P and F may not be null");
355        }
356        if (P.isZERO() && F.size() == 0) {
357            return true;
358        }
359        GenPolynomial<GenPolynomial<C>> t = P.ring.getONE();
360        for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> me : F.entrySet()) {
361            GenPolynomial<GenPolynomial<C>> f = me.getKey();
362            Long E = me.getValue(); // F.get(f);
363            long e = E.longValue();
364            GenPolynomial<GenPolynomial<C>> g = f.power(e);
365            t = t.multiply(g);
366        }
367        boolean f = P.equals(t) || P.equals(t.negate());
368        if (!f) {
369            GenPolynomialRing<C> cf = (GenPolynomialRing<C>) P.ring.coFac;
370            GreatestCommonDivisorAbstract<C> engine = GCDFactory.getProxy(cf.coFac);
371            GenPolynomial<GenPolynomial<C>> Pp = engine.recursivePrimitivePart(P);
372            Pp = PolyUtil.<C> monic(Pp);
373            GenPolynomial<GenPolynomial<C>> tp = engine.recursivePrimitivePart(t);
374            tp = PolyUtil.<C> monic(tp);
375            f = Pp.equals(tp) || Pp.equals(tp.negate());
376            if (f) {
377                return f;
378            }
379            logger.info("no factorization(map): F  = {}, P  = {}, t  = {}, Pp = {}, tp = {}", F, P, t, Pp, tp);
380            //RuntimeException e = new RuntimeException("fac-map");
381            //e.printStackTrace();
382            //throw e;
383        }
384        return f;
385    }
386
387
388    /**
389     * GenPolynomial recursive polynomial greatest squarefree divisor.
390     * @param P recursive GenPolynomial.
391     * @return squarefree(pp(P)).
392     */
393    public GenPolynomial<GenPolynomial<C>> recursiveSquarefreePart(GenPolynomial<GenPolynomial<C>> P) {
394        if (P == null || P.isZERO()) {
395            return P;
396        }
397        if (P.ring.nvar <= 1) {
398            return recursiveUnivariateSquarefreePart(P);
399        }
400        // distributed polynomials squarefree part
401        GenPolynomialRing<GenPolynomial<C>> rfac = P.ring;
402        RingFactory<GenPolynomial<C>> rrfac = rfac.coFac;
403        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) rrfac;
404        GenPolynomialRing<C> dfac = cfac.extend(rfac.nvar);
405        GenPolynomial<C> Pd = PolyUtil.<C> distribute(dfac, P);
406        GenPolynomial<C> Dd = squarefreePart(Pd);
407        // convert to recursive
408        GenPolynomial<GenPolynomial<C>> C = PolyUtil.<C> recursive(rfac, Dd);
409        return C;
410    }
411
412
413    /**
414     * GenPolynomial recursive polynomial squarefree factorization.
415     * @param P recursive GenPolynomial.
416     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
417     *         p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j.
418     */
419    public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveSquarefreeFactors(
420                    GenPolynomial<GenPolynomial<C>> P) {
421        SortedMap<GenPolynomial<GenPolynomial<C>>, Long> factors;
422        factors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>();
423        if (P == null || P.isZERO()) {
424            return factors;
425        }
426        if (P.ring.nvar <= 1) {
427            return recursiveUnivariateSquarefreeFactors(P);
428        }
429        // distributed polynomials squarefree part
430        GenPolynomialRing<GenPolynomial<C>> rfac = P.ring;
431        RingFactory<GenPolynomial<C>> rrfac = rfac.coFac;
432        GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) rrfac;
433        GenPolynomialRing<C> dfac = cfac.extend(rfac.nvar);
434        GenPolynomial<C> Pd = PolyUtil.<C> distribute(dfac, P);
435        SortedMap<GenPolynomial<C>, Long> dfacs = squarefreeFactors(Pd);
436        // convert to recursive
437        for (Map.Entry<GenPolynomial<C>, Long> Dm : dfacs.entrySet()) {
438            GenPolynomial<C> Dd = Dm.getKey();
439            Long e = Dm.getValue();
440            GenPolynomial<GenPolynomial<C>> C = PolyUtil.<C> recursive(rfac, Dd);
441            factors.put(C, e);
442        }
443        return factors;
444    }
445
446
447    /**
448     * Univariate GenPolynomial partial fraction decomposition.
449     * @param A univariate GenPolynomial.
450     * @param D sorted map [d_1 -&gt; e_1, ..., d_k -&gt; e_k] with d_i
451     *            squarefree.
452     * @return [ [Ai0, Ai1,..., Aie_i], i=0,...,k ] with A/prod(D) = A0 + sum(
453     *         sum ( Aij/di^j ) ) with deg(Aij) &lt; deg(di).
454     */
455    public List<List<GenPolynomial<C>>> basePartialFraction(GenPolynomial<C> A,
456                    SortedMap<GenPolynomial<C>, Long> D) {
457        if (D == null || A == null) {
458            throw new IllegalArgumentException("null A or D not allowed");
459        }
460        List<List<GenPolynomial<C>>> pf = new ArrayList<List<GenPolynomial<C>>>(D.size() + 1);
461        if (D.size() == 0) {
462            return pf;
463        }
464        //List<GenPolynomial<C>> fi;
465        if (A.isZERO()) {
466            for (Map.Entry<GenPolynomial<C>, Long> me : D.entrySet()) {
467                long e = me.getValue();
468                int e1 = (int) e + 1;
469                List<GenPolynomial<C>> fi = new ArrayList<GenPolynomial<C>>(e1);
470                for (int i = 0; i < e1; i++) {
471                    fi.add(A);
472                }
473                pf.add(fi);
474            }
475            List<GenPolynomial<C>> fi = new ArrayList<GenPolynomial<C>>(1);
476            fi.add(A);
477            pf.add(0, fi);
478            return pf;
479        }
480        // A != 0, D != empty
481        List<GenPolynomial<C>> Dp = new ArrayList<GenPolynomial<C>>(D.size());
482        for (Map.Entry<GenPolynomial<C>, Long> me : D.entrySet()) {
483            GenPolynomial<C> d = me.getKey();
484            long e = me.getValue(); //D.get(d);
485            GenPolynomial<C> f = d.power(e);
486            Dp.add(f);
487        }
488        List<GenPolynomial<C>> F = engine.basePartialFraction(A, Dp);
489        //System.out.println("fraction list = " + F.size());
490        GenPolynomial<C> A0 = F.remove(0);
491        List<GenPolynomial<C>> fi = new ArrayList<GenPolynomial<C>>(1);
492        fi.add(A0);
493        pf.add(fi);
494        int i = 0;
495        for (Map.Entry<GenPolynomial<C>, Long> me : D.entrySet()) { // assume fixed sequence order
496            GenPolynomial<C> d = me.getKey();
497            long e = me.getValue();
498            int ei = (int) e;
499            GenPolynomial<C> gi = F.get(i); // assume fixed sequence order
500            List<GenPolynomial<C>> Fi = engine.basePartialFraction(gi, d, ei);
501            pf.add(Fi);
502            i++;
503        }
504        return pf;
505    }
506
507
508    /**
509     * Test for Univariate GenPolynomial partial fraction decomposition.
510     * @param A univariate GenPolynomial.
511     * @param D sorted map [d_1 -&gt; e_1, ..., d_k -&gt; e_k] with d_i
512     *            squarefree.
513     * @param F a list of lists [ [Ai0, Ai1,..., Aie_i], i=0,...,k ]
514     * @return true, if A/prod(D) = A0 + sum( sum ( Aij/di^j ) ), else false.
515     */
516    public boolean isBasePartialFraction(GenPolynomial<C> A, SortedMap<GenPolynomial<C>, Long> D,
517                    List<List<GenPolynomial<C>>> F) {
518        if (D == null || A == null || F == null) {
519            throw new IllegalArgumentException("null A, D or F not allowed");
520        }
521        if (D.isEmpty() && F.isEmpty()) {
522            return true;
523        }
524        if (D.isEmpty() || F.isEmpty()) {
525            return false;
526        }
527        List<GenPolynomial<C>> Dp = new ArrayList<GenPolynomial<C>>(D.size());
528        for (Map.Entry<GenPolynomial<C>, Long> me : D.entrySet()) {
529            GenPolynomial<C> d = me.getKey();
530            long e = me.getValue(); // D.get(d);
531            GenPolynomial<C> f = d.power(e);
532            Dp.add(f);
533        }
534        List<GenPolynomial<C>> fi = F.get(0);
535        if (fi.size() != 1) {
536            logger.info("size(fi) != 1 {}", fi);
537            return false;
538        }
539        boolean t;
540        GenPolynomial<C> A0 = fi.get(0);
541        //System.out.println("A0 = " + A0);
542        List<GenPolynomial<C>> Qp = new ArrayList<GenPolynomial<C>>(D.size() + 1);
543        Qp.add(A0);
544
545        //         List<GenPolynomial<C>> Fp = engine.basePartialFraction(A,Dp);
546        //         System.out.println("fraction list = " + F.size());
547        //         t = engine.isBasePartialFraction(A,Dp,Fp);
548        //         if ( ! t ) {
549        //             System.out.println("not recursion isPartFrac = " + Fp);
550        //             return false;
551        //         }
552        //         GenPolynomial<C> A0p = Fp.remove(0);
553        //         if ( ! A0.equals(A0p) ) {
554        //             System.out.println("A0 != A0p " + A0p);
555        //             return false;
556        //         }
557
558        int i = 0;
559        for (Map.Entry<GenPolynomial<C>, Long> me : D.entrySet()) { // assume fixed sequence order
560            GenPolynomial<C> d = me.getKey();
561            long e = me.getValue();
562            int ei = (int) e;
563            List<GenPolynomial<C>> Fi = F.get(i + 1); // assume fixed sequence order
564
565            //            GenPolynomial<C> pi = Fp.get(i);        // assume fixed sequence order
566            //             t = engine.isBasePartialFraction(pi,d,ei,Fi);
567            //             if ( ! t ) {
568            //                 System.out.println("not isPartFrac exp = " + pi + ", d = " + d + ", e = " + ei);
569            //                 System.out.println("not isPartFrac exp = " + Fi);
570            //                 return false;
571            //             }
572
573            GenPolynomial<C> qi = engine.basePartialFractionValue(d, ei, Fi);
574            Qp.add(qi);
575
576            //             t = qi.equals(pi);
577            //             if ( ! t ) {
578            //                 System.out.println("not isPartFrac exp = " + pi + ", d = " + d + ", e = " + ei + ", qi = " + qi);
579            //             }
580
581            i++;
582        }
583
584        t = engine.isBasePartialFraction(A, Dp, Qp);
585        if (!t) {
586            System.out.println("not final isPartFrac " + Qp);
587        }
588        return t;
589    }
590
591
592    /**
593     * Coefficients greatest squarefree divisor.
594     * @param P coefficient.
595     * @return squarefree part of P.
596     */
597    public C squarefreePart(C P) {
598        if (P == null) {
599            return null;
600        }
601        C s = null;
602        SortedMap<C, Long> factors = squarefreeFactors(P);
603        //if (logger.isWarnEnabled()) {
604        //    logger.warn("sqfPart, better use sqfFactors, factors = {}", factors);
605        //}
606        for (C sp : factors.keySet()) {
607            if (s == null) {
608                s = sp;
609            } else {
610                s = s.multiply(sp);
611            }
612        }
613        return s;
614    }
615
616
617    /**
618     * Coefficients squarefree factorization.
619     * @param P coefficient.
620     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
621     *         p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j.
622     */
623    public abstract SortedMap<C, Long> squarefreeFactors(C P);
624    /* not possible:
625    {
626        if (P == null) {
627            return null;
628        }
629        SortedMap<C, Long> factors = new TreeMap<C, Long>();
630        SquarefreeAbstract<C> reng = SquarefreeFactory.getImplementation((RingFactory<C>) P.factory());
631            System.out.println("fcp,reng = " + reng);
632            SortedMap<C, Long> rfactors = reng.squarefreeFactors(P);
633            for (C c : rfactors.keySet()) {
634                if (!c.isONE()) {
635                    C cr = (C) (Object) c;
636                    Long rk = rfactors.get(c);
637                    factors.put(cr, rk);
638                }
639            }
640    
641        return factors;
642    }
643    */
644
645}