Source code

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