001/*
002 * $Id: GreatestCommonDivisorAbstract.java 5872 2018-07-20 16:01:46Z kredel $
003 */
004
005package edu.jas.fd;
006
007
008import java.util.ArrayList;
009import java.util.Arrays;
010import java.util.List;
011
012import org.apache.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.gbufd.SolvableSyzygyAbstract;
016import edu.jas.gbufd.SolvableSyzygySeq;
017import edu.jas.poly.GenPolynomial;
018import edu.jas.poly.GenSolvablePolynomial;
019import edu.jas.poly.GenSolvablePolynomialRing;
020import edu.jas.poly.PolyUtil;
021import edu.jas.poly.RecSolvablePolynomial;
022import edu.jas.poly.RecSolvablePolynomialRing;
023import edu.jas.structure.GcdRingElem;
024import edu.jas.structure.RingFactory;
025import edu.jas.structure.StarRingElem;
026import edu.jas.ufd.GCDFactory;
027
028
029/**
030 * (Non-unique) factorization domain greatest common divisor common algorithms.
031 * @param <C> coefficient type
032 * @author Heinz Kredel
033 */
034
035public abstract class GreatestCommonDivisorAbstract<C extends GcdRingElem<C>>
036                implements GreatestCommonDivisor<C> {
037
038
039    private static final Logger logger = LogManager.getLogger(GreatestCommonDivisorAbstract.class);
040
041
042    private static final boolean debug = logger.isDebugEnabled();
043
044
045    /**
046     * Engine for syzygy computation.
047     */
048    final SolvableSyzygyAbstract<C> syz;
049
050
051    /**
052     * Coefficient ring.
053     */
054    final RingFactory<C> coFac;
055
056
057    /*
058     * Engine for commutative gcd computation.
059     */
060    //edu.jas.ufd.GreatestCommonDivisorAbstract<C> cgcd;
061
062
063    /**
064     * Constructor.
065     * @param cf coefficient ring.
066     */
067    public GreatestCommonDivisorAbstract(RingFactory<C> cf) {
068        this(cf, new SolvableSyzygySeq<C>(cf));
069    }
070
071
072    /**
073     * Constructor.
074     * @param cf coefficient ring.
075     * @param s algorithm for SolvableSyzygy computation.
076     */
077    public GreatestCommonDivisorAbstract(RingFactory<C> cf, SolvableSyzygyAbstract<C> s) {
078        coFac = cf;
079        syz = s;
080        //cgcd = GCDFactory.<C> getImplementation(pfac.coFac);
081    }
082
083
084    /**
085     * Get the String representation.
086     * @see java.lang.Object#toString()
087     */
088    @Override
089    public String toString() {
090        return getClass().getName();
091    }
092
093
094    /**
095     * GenSolvablePolynomial base coefficient content.
096     * @param P GenSolvablePolynomial.
097     * @return cont(P) with pp(P)*cont(P) = P.
098     */
099    public C leftBaseContent(GenSolvablePolynomial<C> P) {
100        if (P == null) {
101            throw new IllegalArgumentException("P == null");
102        }
103        if (P.isZERO()) {
104            return P.ring.getZEROCoefficient();
105        }
106        if (P.ring.coFac.isField()) { // so to make monic
107            return P.leadingBaseCoefficient();
108        }
109        C d = null;
110        for (C c : P.getMap().values()) {
111            if (d == null) {
112                d = c;
113            } else {
114                d = d.leftGcd(c);
115            }
116            if (d.isONE()) {
117                return d;
118            }
119        }
120        if (d.signum() < 0) {
121            d = d.negate();
122        }
123        return d;
124    }
125
126
127    /**
128     * GenSolvablePolynomial right base coefficient content.
129     * @param P GenSolvablePolynomial.
130     * @return cont(P) with cont(P)*pp(P) = P.
131     */
132    public C rightBaseContent(GenSolvablePolynomial<C> P) {
133        if (P == null) {
134            throw new IllegalArgumentException("P == null");
135        }
136        if (P.isZERO()) {
137            return P.ring.getZEROCoefficient();
138        }
139        if (P.ring.coFac.isField()) { // so to make monic
140            return P.leadingBaseCoefficient(); // todo check move to right
141        }
142        C d = null;
143        for (C c : P.getMap().values()) {
144            if (d == null) {
145                d = c;
146            } else {
147                d = d.rightGcd(c); // DONE does now exist
148            }
149            if (d.isONE()) {
150                return d;
151            }
152        }
153        if (d.signum() < 0) {
154            d = d.negate();
155        }
156        return d;
157    }
158
159
160    /**
161     * GenSolvablePolynomial base coefficient primitive part.
162     * @param P GenSolvablePolynomial.
163     * @return pp(P) with pp(P)*cont(P) = P.
164     */
165    public GenSolvablePolynomial<C> leftBasePrimitivePart(GenSolvablePolynomial<C> P) {
166        if (P == null) {
167            throw new IllegalArgumentException("P == null");
168        }
169        if (P.isZERO()) {
170            return P;
171        }
172        C d = leftBaseContent(P);
173        if (d.isONE()) {
174            return P;
175        }
176        if (P.ring.coFac.isField()) { // make monic
177            return P.multiplyLeft(d.inverse()); // avoid the divisions
178            //return P.multiply( d.inverse() ); // avoid the divisions
179        }
180        //GenSolvablePolynomial<C> pp = (GenSolvablePolynomial<C>) P.rightDivideCoeff(d); // rightDivide TODO/done
181        GenSolvablePolynomial<C> pp = (GenSolvablePolynomial<C>) P.leftDivideCoeff(d); // TODO
182        if (debug) {
183            GenSolvablePolynomial<C> p = pp.multiplyLeft(d);
184            if (!p.equals(P)) {
185                throw new ArithmeticException("pp(p)*cont(p) != p: ");
186            }
187        }
188        return pp;
189    }
190
191
192    /**
193     * GenSolvablePolynomial right base coefficient primitive part.
194     * @param P GenSolvablePolynomial.
195     * @return pp(P) with cont(P)*pp(P) = P.
196     */
197    public GenSolvablePolynomial<C> rightBasePrimitivePart(GenSolvablePolynomial<C> P) {
198        if (P == null) {
199            throw new IllegalArgumentException("P == null");
200        }
201        if (P.isZERO()) {
202            return P;
203        }
204        C d = rightBaseContent(P);
205        if (d.isONE()) {
206            return P;
207        }
208        if (P.ring.coFac.isField()) { // make monic
209            return P.multiplyLeft(d.inverse()); // avoid the divisions
210        }
211        GenSolvablePolynomial<C> pp = (GenSolvablePolynomial<C>) P.leftDivideCoeff(d); // leftDivide TODO/done
212        if (debug) {
213            GenSolvablePolynomial<C> p = pp.multiplyLeft(d);
214            if (!p.equals(P)) {
215                throw new ArithmeticException("pp(p)*cont(p) != p: ");
216            }
217        }
218        return pp;
219    }
220
221
222    /**
223     * Univariate GenSolvablePolynomial greatest common divisor. Uses sparse
224     * pseudoRemainder for remainder.
225     * @param P univariate GenSolvablePolynomial.
226     * @param S univariate GenSolvablePolynomial.
227     * @return gcd(P,S) with P = P'*gcd(P,S) and S = S'*gcd(P,S).
228     */
229    public abstract GenSolvablePolynomial<C> leftBaseGcd(GenSolvablePolynomial<C> P,
230                    GenSolvablePolynomial<C> S);
231
232
233    /**
234     * Univariate GenSolvablePolynomial right greatest common divisor. Uses
235     * sparse pseudoRemainder for remainder.
236     * @param P univariate GenSolvablePolynomial.
237     * @param S univariate GenSolvablePolynomial.
238     * @return gcd(P,S) with P = gcd(P,S)*P' and S = gcd(P,S)*S'.
239     */
240    public abstract GenSolvablePolynomial<C> rightBaseGcd(GenSolvablePolynomial<C> P,
241                    GenSolvablePolynomial<C> S);
242
243
244    /**
245     * GenSolvablePolynomial commuting recursive content.
246     * @param P recursive GenSolvablePolynomial with commuting main and
247     *            coefficient variables.
248     * @return cont(P) with cont(P)*pp(P) = pp(P)*cont(P).
249     */
250    public GenSolvablePolynomial<C> recursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) {
251        if (P == null) {
252            throw new IllegalArgumentException("P == null");
253        }
254        if (P instanceof RecSolvablePolynomial) {
255            RecSolvablePolynomialRing<C> rfac = (RecSolvablePolynomialRing<C>) P.ring;
256            if (!rfac.coeffTable.isEmpty()) {
257                throw new IllegalArgumentException("P is a RecSolvablePolynomial, use recursiveContent()");
258            }
259        }
260        if (P.isZERO()) {
261            return (GenSolvablePolynomial<C>) P.ring.getZEROCoefficient();
262        }
263        if (P.isONE()) {
264            return (GenSolvablePolynomial<C>) P.ring.getONECoefficient();
265        }
266        if (P.leadingBaseCoefficient().isONE()) {
267            return (GenSolvablePolynomial<C>) P.ring.getONECoefficient();
268        }
269        //GenSolvablePolynomial<GenPolynomial<C>> p = P;
270        GenSolvablePolynomial<C> d = null;
271        for (GenPolynomial<C> cp : P.getMap().values()) {
272            GenSolvablePolynomial<C> c = (GenSolvablePolynomial<C>) cp;
273            if (d == null) {
274                d = c;
275            } else {
276                ///d = leftGcd(d, c); // go to recursion
277                d = rightGcd(d, c); // go to recursion
278            }
279            if (d.isONE()) {
280                return d;
281            }
282        }
283        return (GenSolvablePolynomial<C>) d.abs();
284    }
285
286
287    /**
288     * GenSolvablePolynomial right recursive content.
289     * @param P recursive GenSolvablePolynomial.
290     * @return cont(P) with pp(P)*cont(P) = P.
291     */
292    public GenSolvablePolynomial<C> rightRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) {
293        if (P == null) {
294            throw new IllegalArgumentException("P != null");
295        }
296        if (P.isZERO()) {
297            return (GenSolvablePolynomial<C>) P.ring.getZEROCoefficient();
298        }
299        if (P.leadingBaseCoefficient().isONE()) {
300            return (GenSolvablePolynomial<C>) P.ring.getONECoefficient();
301        }
302        GenSolvablePolynomial<C> d = null, cs = null, x;
303        GenSolvablePolynomial<GenPolynomial<C>> Pr = P.rightRecursivePolynomial();
304        logger.info("RI-recCont: P = " + P + ", right(P) = " + Pr);
305        for (GenPolynomial<C> c : Pr.getMap().values()) {
306            cs = (GenSolvablePolynomial<C>) c;
307            if (d == null) {
308                d = cs;
309            } else {
310                x = d;
311                d = leftGcd(d, cs); // go to recursion, P = P'*gcd(P,S)
312                ///d = rightGcd(d, cs); // go to recursion,  P = gcd(P,S)*P'
313                logger.info("RI-recCont: d = " + x + ", cs = " + cs + ", d = " + d);
314            }
315            if (d.isONE()) {
316                return d;
317            }
318        }
319        return (GenSolvablePolynomial<C>) d.abs();
320    }
321
322
323    /**
324     * GenSolvablePolynomial right recursive primitive part.
325     * @param P recursive GenSolvablePolynomial.
326     * @return pp(P) with pp(P)*cont(P) = P.
327     */
328    public GenSolvablePolynomial<GenPolynomial<C>> rightRecursivePrimitivePart(
329                    GenSolvablePolynomial<GenPolynomial<C>> P) {
330        if (P == null) {
331            throw new IllegalArgumentException("P == null");
332        }
333        if (P.isZERO()) {
334            return P;
335        }
336        GenSolvablePolynomial<C> d = rightRecursiveContent(P);
337        if (d.isONE()) {
338            return P;
339        }
340        GenSolvablePolynomial<GenPolynomial<C>> pp;
341        pp = FDUtil.<C> recursiveLeftDivide(P, d); //RightEval
342        if (debug) { // not checkable
343            if (!P.equals(pp.multiply(d))) {
344                System.out.println("RI-ppart, P         = " + P);
345                System.out.println("RI-ppart, cont(P)   = " + d);
346                System.out.println("RI-ppart, pp(P)     = " + pp);
347                System.out.println("RI-ppart, pp(P)c(P) = " + pp.multiply(d));
348                throw new RuntimeException("RI-primitivePart: P != pp(P)*cont(P)");
349            }
350        }
351        return pp;
352    }
353
354
355    /**
356     * GenSolvablePolynomial left recursive content.
357     * @param P recursive GenSolvablePolynomial.
358     * @return cont(P) with cont(P)*pp(P) = P.
359     */
360    public GenSolvablePolynomial<C> leftRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) {
361        if (P == null) {
362            throw new IllegalArgumentException("P != null");
363        }
364        if (P.isZERO()) {
365            return (GenSolvablePolynomial<C>) P.ring.getZEROCoefficient();
366        }
367        if (P.leadingBaseCoefficient().isONE()) {
368            return (GenSolvablePolynomial<C>) P.ring.getONECoefficient();
369        }
370        GenSolvablePolynomial<C> d = null, cs = null;
371        GenSolvablePolynomial<GenPolynomial<C>> Pr = P; //FDUtil.<C> rightRecursivePolynomial(P);
372        logger.info("recCont: P = " + P + ", right(P) = " + Pr);
373        for (GenPolynomial<C> c : Pr.getMap().values()) {
374            cs = (GenSolvablePolynomial<C>) c;
375            if (d == null) {
376                d = cs;
377            } else {
378                d = rightGcd(d, cs); // go to recursion
379                ///d = leftGcd(d, cs); // go to recursion
380                logger.info("recCont: cs = " + cs + ", d = " + d);
381            }
382            if (d.isONE()) {
383                return d;
384            }
385        }
386        return (GenSolvablePolynomial<C>) d.abs();
387    }
388
389
390    /**
391     * GenSolvablePolynomial left recursive primitive part.
392     * @param P recursive GenSolvablePolynomial.
393     * @return pp(P) with cont(P)*pp(P) = P.
394     */
395    public GenSolvablePolynomial<GenPolynomial<C>> leftRecursivePrimitivePart(
396                    GenSolvablePolynomial<GenPolynomial<C>> P) {
397        if (P == null) {
398            throw new IllegalArgumentException("P == null");
399        }
400        if (P.isZERO()) {
401            return P;
402        }
403        GenSolvablePolynomial<C> d = leftRecursiveContent(P);
404        if (d.isONE()) {
405            return P;
406        }
407        GenSolvablePolynomial<GenPolynomial<C>> pp;
408        pp = FDUtil.<C> recursiveRightDivide(P, d);
409        if (debug) { // not checkable
410            if (!P.equals(pp.multiplyLeft(d))) {
411                System.out.println("ppart, P         = " + P);
412                System.out.println("ppart, cont(P)   = " + d);
413                System.out.println("ppart, pp(P)     = " + pp);
414                System.out.println("ppart, pp(P)c(P) = " + pp.multiplyLeft(d));
415                throw new RuntimeException("primitivePart: P != cont(P)*pp(P)");
416            }
417        }
418        return pp;
419    }
420
421
422    /**
423     * GenSolvablePolynomial base recursive content.
424     * @param P recursive GenSolvablePolynomial.
425     * @return baseCont(P) with pp(P)*cont(P) = P.
426     */
427    public C baseRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) {
428        if (P == null) {
429            throw new IllegalArgumentException("P == null");
430        }
431        if (P.isZERO()) {
432            GenSolvablePolynomialRing<C> cf = (GenSolvablePolynomialRing<C>) P.ring.coFac;
433            return cf.coFac.getZERO();
434        }
435        C d = null;
436        for (GenPolynomial<C> cp : P.getMap().values()) {
437            GenSolvablePolynomial<C> c = (GenSolvablePolynomial<C>) cp;
438            C cc = leftBaseContent(c);
439            if (d == null) {
440                d = cc;
441            } else {
442                d = gcd(d, cc);
443            }
444            if (d.isONE()) {
445                return d;
446            }
447        }
448        return d.abs();
449    }
450
451
452    /**
453     * GenSolvablePolynomial base recursive primitive part.
454     * @param P recursive GenSolvablePolynomial.
455     * @return basePP(P) with pp(P)*cont(P) = P.
456     */
457    public GenSolvablePolynomial<GenPolynomial<C>> baseRecursivePrimitivePart(
458                    GenSolvablePolynomial<GenPolynomial<C>> P) {
459        if (P == null) {
460            throw new IllegalArgumentException("P == null");
461        }
462        if (P.isZERO()) {
463            return P;
464        }
465        C d = baseRecursiveContent(P);
466        if (d.isONE()) {
467            return P;
468        }
469        GenSolvablePolynomial<GenPolynomial<C>> pp = (GenSolvablePolynomial<GenPolynomial<C>>) PolyUtil
470                        .<C> baseRecursiveDivide(P, d);
471        return pp;
472    }
473
474
475    /**
476     * GenSolvablePolynomial left recursive greatest common divisor. Uses
477     * pseudoRemainder for remainder.
478     * @param P recursive GenSolvablePolynomial.
479     * @param S recursive GenSolvablePolynomial.
480     * @return gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where
481     *         deg_main(p) = deg_main(s) == 0.
482     */
483    @SuppressWarnings("unchecked")
484    public GenSolvablePolynomial<GenPolynomial<C>> leftRecursiveGcd(GenSolvablePolynomial<GenPolynomial<C>> P,
485                    GenSolvablePolynomial<GenPolynomial<C>> S) {
486        if (S == null || S.isZERO()) {
487            return P;
488        }
489        if (P == null || P.isZERO()) {
490            return S;
491        }
492        if (P.ring.nvar == 1) {
493            return leftRecursiveUnivariateGcd(P, S);
494        }
495        // distributed polynomials gcd
496        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = P.ring;
497        GenSolvablePolynomialRing<C> dfac;
498        if (rfac instanceof RecSolvablePolynomialRing) {
499            RecSolvablePolynomialRing<C> rf = (RecSolvablePolynomialRing<C>) rfac;
500            dfac = RecSolvablePolynomialRing.<C> distribute(rf);
501        } else {
502            GenSolvablePolynomialRing<C> df = (GenSolvablePolynomialRing) rfac;
503            dfac = df.distribute();
504        }
505        GenSolvablePolynomial<C> Pd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, P);
506        GenSolvablePolynomial<C> Sd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, S);
507        GenSolvablePolynomial<C> Dd = leftGcd(Pd, Sd);
508        // convert to recursive
509        GenSolvablePolynomial<GenPolynomial<C>> C = (GenSolvablePolynomial<GenPolynomial<C>>) PolyUtil
510                        .<C> recursive(rfac, Dd);
511        return C;
512    }
513
514
515    /**
516     * GenSolvablePolynomial right recursive greatest common divisor. Uses
517     * pseudoRemainder for remainder.
518     * @param P recursive GenSolvablePolynomial.
519     * @param S recursive GenSolvablePolynomial.
520     * @return gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where
521     *         deg_main(p) = deg_main(s) == 0.
522     */
523    @SuppressWarnings("unchecked")
524    public GenSolvablePolynomial<GenPolynomial<C>> rightRecursiveGcd(
525                    GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) {
526        if (S == null || S.isZERO()) {
527            return P;
528        }
529        if (P == null || P.isZERO()) {
530            return S;
531        }
532        if (P.ring.nvar == 1) {
533            return rightRecursiveUnivariateGcd(P, S);
534        }
535        // distributed polynomials gcd
536        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = P.ring;
537        GenSolvablePolynomialRing<C> dfac;
538        if (rfac instanceof RecSolvablePolynomialRing) {
539            RecSolvablePolynomialRing<C> rf = (RecSolvablePolynomialRing<C>) rfac;
540            dfac = RecSolvablePolynomialRing.<C> distribute(rf);
541        } else {
542            GenSolvablePolynomialRing<C> df = (GenSolvablePolynomialRing) rfac;
543            dfac = df.distribute();
544        }
545        GenSolvablePolynomial<C> Pd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, P);
546        GenSolvablePolynomial<C> Sd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, S);
547        GenSolvablePolynomial<C> Dd = rightGcd(Pd, Sd);
548        // convert to recursive
549        GenSolvablePolynomial<GenPolynomial<C>> C = (GenSolvablePolynomial<GenPolynomial<C>>) PolyUtil
550                        .<C> recursive(rfac, Dd);
551        return C;
552    }
553
554
555    /**
556     * Univariate GenSolvablePolynomial recursive greatest common divisor. Uses
557     * pseudoRemainder for remainder.
558     * @param P univariate recursive GenSolvablePolynomial.
559     * @param S univariate recursive GenSolvablePolynomial.
560     * @return gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where
561     *         deg_main(p) = deg_main(s) == 0.
562     */
563    public abstract GenSolvablePolynomial<GenPolynomial<C>> leftRecursiveUnivariateGcd(
564                    GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S);
565
566
567    /**
568     * Univariate GenSolvablePolynomial right recursive greatest common divisor.
569     * Uses pseudoRemainder for remainder.
570     * @param P univariate recursive GenSolvablePolynomial.
571     * @param S univariate recursive GenSolvablePolynomial.
572     * @return gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where
573     *         deg_main(p) = deg_main(s) == 0.
574     */
575    public abstract GenSolvablePolynomial<GenPolynomial<C>> rightRecursiveUnivariateGcd(
576                    GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S);
577
578
579    /**
580     * GenSolvablePolynomial right content.
581     * @param P GenSolvablePolynomial.
582     * @return cont(P) with pp(P)*cont(P) = P.
583     */
584    public GenSolvablePolynomial<C> rightContent(GenSolvablePolynomial<C> P) {
585        if (P == null) {
586            throw new IllegalArgumentException("P == null");
587        }
588        GenSolvablePolynomialRing<C> pfac = P.ring;
589        if (pfac.nvar <= 1) {
590            // baseContent not possible by return type
591            throw new IllegalArgumentException("use baseContent() for univariate polynomials");
592        }
593        GenSolvablePolynomialRing<GenPolynomial<C>> rfac // = (RecSolvablePolynomialRing<C>) 
594                        = pfac.recursive(1);
595
596        GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac,
597                        P);
598        GenSolvablePolynomial<C> D = rightRecursiveContent(Pr);
599        return D;
600    }
601
602
603    /**
604     * GenSolvablePolynomial right primitive part.
605     * @param P GenSolvablePolynomial.
606     * @return pp(P) with pp(P)*cont(P) = P.
607     */
608    public GenSolvablePolynomial<C> rightPrimitivePart(GenSolvablePolynomial<C> P) {
609        if (P == null) {
610            throw new IllegalArgumentException("P == null");
611        }
612        if (P.isZERO()) {
613            return P;
614        }
615        GenSolvablePolynomialRing<C> pfac = P.ring;
616        if (pfac.nvar <= 1) {
617            return rightBasePrimitivePart(P);
618        }
619        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = /*(RecSolvablePolynomialRing<C>)*/pfac
620                        .recursive(1);
621
622        GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac,
623                        P);
624        GenSolvablePolynomial<GenPolynomial<C>> PP = rightRecursivePrimitivePart(Pr);
625
626        GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, PP);
627        return D;
628    }
629
630
631    /**
632     * GenSolvablePolynomial left content.
633     * @param P GenSolvablePolynomial.
634     * @return cont(P) with cont(P)*pp(P) = P.
635     */
636    public GenSolvablePolynomial<C> leftContent(GenSolvablePolynomial<C> P) {
637        if (P == null) {
638            throw new IllegalArgumentException("P == null");
639        }
640        GenSolvablePolynomialRing<C> pfac = P.ring;
641        if (pfac.nvar <= 1) {
642            // baseContent not possible by return type
643            throw new IllegalArgumentException("use baseContent() for univariate polynomials");
644        }
645        GenSolvablePolynomialRing<GenPolynomial<C>> rfac // = (RecSolvablePolynomialRing<C>) 
646                        = pfac.recursive(1);
647
648        GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac,
649                        P);
650        GenSolvablePolynomial<C> D = leftRecursiveContent(Pr);
651        return D;
652    }
653
654
655    /**
656     * GenSolvablePolynomial left primitive part.
657     * @param P GenSolvablePolynomial.
658     * @return pp(P) with cont(P)*pp(P) = P.
659     */
660    public GenSolvablePolynomial<C> leftPrimitivePart(GenSolvablePolynomial<C> P) {
661        if (P == null) {
662            throw new IllegalArgumentException("P == null");
663        }
664        if (P.isZERO()) {
665            return P;
666        }
667        GenSolvablePolynomialRing<C> pfac = P.ring;
668        if (pfac.nvar <= 1) {
669            return leftBasePrimitivePart(P);
670        }
671        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = /*(RecSolvablePolynomialRing<C>)*/pfac
672                        .recursive(1);
673
674        GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac,
675                        P);
676        GenSolvablePolynomial<GenPolynomial<C>> PP = leftRecursivePrimitivePart(Pr);
677
678        GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, PP);
679        return D;
680    }
681
682
683    /**
684     * GenSolvablePolynomial division. Indirection to GenSolvablePolynomial
685     * method.
686     * @param a GenSolvablePolynomial.
687     * @param b coefficient.
688     * @return a' = a/b with a = a'*b.
689     */
690    public GenSolvablePolynomial<C> divide(GenSolvablePolynomial<C> a, C b) {
691        if (b == null || b.isZERO()) {
692            throw new IllegalArgumentException("division by zero");
693
694        }
695        if (a == null || a.isZERO()) {
696            return a;
697        }
698        return (GenSolvablePolynomial<C>) a.divide(b);
699    }
700
701
702    /*
703     * GenSolvablePolynomial right division. Indirection to GenSolvablePolynomial
704     * method.
705     * @param a GenSolvablePolynomial.
706     * @param b coefficient.
707     * @return a' = a/b with a = b*a'.
708    public GenSolvablePolynomial<C> rightDivide(GenSolvablePolynomial<C> a, C b) {
709        if (b == null || b.isZERO()) {
710            throw new IllegalArgumentException("division by zero");
711    
712        }
713        if (a == null || a.isZERO()) {
714            return a;
715        }
716        return (GenSolvablePolynomial<C>) a.rightDivide(b);
717    }
718     */
719
720
721    /**
722     * Coefficient greatest common divisor. Indirection to coefficient method.
723     * @param a coefficient.
724     * @param b coefficient.
725     * @return gcd(a,b) with a = a'*gcd(a,b) and b = b'*gcd(a,b).
726     */
727    public C gcd(C a, C b) {
728        if (b == null || b.isZERO()) {
729            return a;
730        }
731        if (a == null || a.isZERO()) {
732            return b;
733        }
734        return a.gcd(b);
735    }
736
737
738    /**
739     * GenSolvablePolynomial greatest common divisor.
740     * @param P GenSolvablePolynomial.
741     * @param S GenSolvablePolynomial.
742     * @return gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where
743     *         deg_main(p) = deg_main(s) == 0.
744     */
745    public GenSolvablePolynomial<C> leftGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
746        if (S == null || S.isZERO()) {
747            return P;
748        }
749        if (P == null || P.isZERO()) {
750            return S;
751        }
752        if (P.isONE()) {
753            return P;
754        }
755        if (S.isONE()) {
756            return S;
757        }
758        GenSolvablePolynomialRing<C> pfac = P.ring;
759        if (pfac.nvar <= 1) {
760            GenSolvablePolynomial<C> T = leftBaseGcd(P, S);
761            return T;
762        }
763        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); //RecSolvablePolynomialRing<C>
764        GenSolvablePolynomial<GenPolynomial<C>> Pr, Sr, Dr;
765        Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, P);
766        Sr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, S);
767        Dr = leftRecursiveUnivariateGcd(Pr, Sr);
768        GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, Dr);
769        if (debug) { // not checkable
770            GenSolvablePolynomial<C> ps = FDUtil.<C> rightBaseSparsePseudoRemainder(P, D);
771            GenSolvablePolynomial<C> ss = FDUtil.<C> rightBaseSparsePseudoRemainder(S, D);
772            if (!ps.isZERO() || !ss.isZERO()) {
773                System.out.println("fullGcd, D  = " + D);
774                System.out.println("fullGcd, P  = " + P);
775                System.out.println("fullGcd, S  = " + S);
776                System.out.println("fullGcd, ps = " + ps);
777                System.out.println("fullGcd, ss = " + ss);
778                throw new RuntimeException("fullGcd: not divisible");
779            }
780            logger.info("fullGcd(P,S) okay: D = " + D + ", P = " + P + ", S = " + S);
781        }
782        return D;
783    }
784
785
786    /**
787     * GenSolvablePolynomial left least common multiple.
788     * @param P GenSolvablePolynomial.
789     * @param S GenSolvablePolynomial.
790     * @return lcm(P,S) with lcm(P,S) = P'*P = S'*S.
791     */
792    public GenSolvablePolynomial<C> leftLcm(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
793        GenSolvablePolynomial<C>[] oc = leftOreCond(P, S);
794        return oc[0].multiply(P);
795    }
796
797
798    /**
799     * GenSolvablePolynomial right greatest common divisor.
800     * @param P GenSolvablePolynomial.
801     * @param S GenSolvablePolynomial.
802     * @return gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where
803     *         deg_main(p) = deg_main(s) == 0.
804     */
805    public GenSolvablePolynomial<C> rightGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
806        if (S == null || S.isZERO()) {
807            return P;
808        }
809        if (P == null || P.isZERO()) {
810            return S;
811        }
812        if (P.isONE()) {
813            return P;
814        }
815        if (S.isONE()) {
816            return S;
817        }
818        GenSolvablePolynomialRing<C> pfac = P.ring;
819        if (pfac.nvar <= 1) {
820            GenSolvablePolynomial<C> T = rightBaseGcd(P, S);
821            return T;
822        }
823        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); //RecSolvablePolynomialRing<C>
824        GenSolvablePolynomial<GenPolynomial<C>> Pr, Sr, Dr;
825        Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, P);
826        Sr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, S);
827        Dr = rightRecursiveUnivariateGcd(Pr, Sr);
828        GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, Dr);
829        if (debug) { // not checkable
830            GenSolvablePolynomial<C> ps = FDUtil.<C> leftBaseSparsePseudoRemainder(P, D);
831            GenSolvablePolynomial<C> ss = FDUtil.<C> leftBaseSparsePseudoRemainder(S, D);
832            if (!ps.isZERO() || !ss.isZERO()) {
833                System.out.println("RI-fullGcd, D  = " + D);
834                System.out.println("RI-fullGcd, P  = " + P);
835                System.out.println("RI-fullGcd, S  = " + S);
836                System.out.println("RI-fullGcd, ps = " + ps);
837                System.out.println("RI-fullGcd, ss = " + ss);
838                throw new RuntimeException("RI-fullGcd: not divisible");
839            }
840            logger.info("RI-fullGcd(P,S) okay: D = " + D);
841        }
842        return D;
843    }
844
845
846    /**
847     * GenSolvablePolynomial right least common multiple.
848     * @param P GenSolvablePolynomial.
849     * @param S GenSolvablePolynomial.
850     * @return lcm(P,S) with lcm(P,S) = P*P' = S*S'.
851     */
852    public GenSolvablePolynomial<C> rightLcm(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
853        GenSolvablePolynomial<C>[] oc = rightOreCond(P, S);
854        return P.multiply(oc[0]);
855    }
856
857
858    /**
859     * List of GenSolvablePolynomials left greatest common divisor.
860     * @param A non empty list of GenSolvablePolynomials.
861     * @return gcd(A_i) with A_i = A'_i*gcd(A_i)*a_i, where deg_main(a_i) == 0.
862     */
863    public GenSolvablePolynomial<C> leftGcd(List<GenSolvablePolynomial<C>> A) {
864        if (A == null || A.isEmpty()) {
865            throw new IllegalArgumentException("A may not be empty");
866        }
867        GenSolvablePolynomial<C> g = A.get(0);
868        for (int i = 1; i < A.size(); i++) {
869            GenSolvablePolynomial<C> f = A.get(i);
870            g = leftGcd(g, f);
871        }
872        return g;
873    }
874
875
876    /**
877     * GenSolvablePolynomial co-prime list.
878     * @param A list of GenSolvablePolynomials.
879     * @return B with gcd(b,c) = 1 for all b != c in B and for all non-constant
880     *         a in A there exists b in B with b|a. B does not contain zero or
881     *         constant polynomials.
882     */
883    public List<GenSolvablePolynomial<C>> leftCoPrime(List<GenSolvablePolynomial<C>> A) {
884        if (A == null || A.isEmpty()) {
885            return A;
886        }
887        List<GenSolvablePolynomial<C>> B = new ArrayList<GenSolvablePolynomial<C>>(A.size());
888        // make a coprime to rest of list
889        GenSolvablePolynomial<C> a = A.get(0);
890        //System.out.println("a = " + a);
891        if (!a.isZERO() && !a.isConstant()) {
892            for (int i = 1; i < A.size(); i++) {
893                GenSolvablePolynomial<C> b = A.get(i);
894                GenSolvablePolynomial<C> g = leftGcd(a, b);
895                if (!g.isONE()) {
896                    a = FDUtil.<C> leftBasePseudoQuotient(a, g);
897                    b = FDUtil.<C> leftBasePseudoQuotient(b, g);
898                    GenSolvablePolynomial<C> gp = leftGcd(a, g); //.abs();
899                    while (!gp.isONE()) {
900                        a = FDUtil.<C> leftBasePseudoQuotient(a, gp);
901                        g = FDUtil.<C> leftBasePseudoQuotient(g, gp);
902                        B.add(g); // gcd(a,g) == 1
903                        g = gp;
904                        gp = leftGcd(a, gp);
905                    }
906                    if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
907                        B.add(g); // gcd(a,g) == 1
908                    }
909                }
910                if (!b.isZERO() && !b.isConstant()) {
911                    B.add(b); // gcd(a,b) == 1
912                }
913            }
914        } else {
915            B.addAll(A.subList(1, A.size()));
916        }
917        // make rest coprime
918        B = leftCoPrime(B);
919        //System.out.println("B = " + B);
920        if (!a.isZERO() && !a.isConstant() /*&& !B.contains(a)*/) {
921            a = (GenSolvablePolynomial<C>) a.abs();
922            B.add(a);
923        }
924        return B;
925    }
926
927
928    /**
929     * GenSolvablePolynomial left co-prime list.
930     * @param A list of GenSolvablePolynomials.
931     * @return B with gcd(b,c) = 1 for all b != c in B and for all non-constant
932     *         a in A there exists b in B with b|a. B does not contain zero or
933     *         constant polynomials.
934     */
935    public List<GenSolvablePolynomial<C>> leftCoPrimeRec(List<GenSolvablePolynomial<C>> A) {
936        if (A == null || A.isEmpty()) {
937            return A;
938        }
939        List<GenSolvablePolynomial<C>> B = new ArrayList<GenSolvablePolynomial<C>>();
940        // make a co-prime to rest of list
941        for (GenSolvablePolynomial<C> a : A) {
942            //System.out.println("a = " + a);
943            B = leftCoPrime(a, B);
944            //System.out.println("B = " + B);
945        }
946        return B;
947    }
948
949
950    /**
951     * GenSolvablePolynomial left co-prime list.
952     * @param a GenSolvablePolynomial.
953     * @param P co-prime list of GenSolvablePolynomials.
954     * @return B with gcd(b,c) = 1 for all b != c in B and for non-constant a
955     *         there exists b in P with b|a. B does not contain zero or constant
956     *         polynomials.
957     */
958    public List<GenSolvablePolynomial<C>> leftCoPrime(GenSolvablePolynomial<C> a,
959                    List<GenSolvablePolynomial<C>> P) {
960        if (a == null || a.isZERO() || a.isConstant()) {
961            return P;
962        }
963        List<GenSolvablePolynomial<C>> B = new ArrayList<GenSolvablePolynomial<C>>(P.size() + 1);
964        // make a coprime to elements of the list P
965        for (int i = 0; i < P.size(); i++) {
966            GenSolvablePolynomial<C> b = P.get(i);
967            GenSolvablePolynomial<C> g = leftGcd(a, b);
968            if (!g.isONE()) {
969                a = FDUtil.<C> leftBasePseudoQuotient(a, g);
970                b = FDUtil.<C> leftBasePseudoQuotient(b, g);
971                // make g co-prime to new a, g is co-prime to c != b in P, B
972                GenSolvablePolynomial<C> gp = leftGcd(a, g);
973                while (!gp.isONE()) {
974                    a = FDUtil.<C> leftBasePseudoQuotient(a, gp);
975                    g = FDUtil.<C> leftBasePseudoQuotient(g, gp);
976                    if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
977                        B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B
978                    }
979                    g = gp;
980                    gp = leftGcd(a, gp);
981                }
982                // make new g co-prime to new b
983                gp = leftGcd(b, g);
984                while (!gp.isONE()) {
985                    b = FDUtil.<C> leftBasePseudoQuotient(b, gp);
986                    g = FDUtil.<C> leftBasePseudoQuotient(g, gp);
987                    if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
988                        B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B
989                    }
990                    g = gp;
991                    gp = leftGcd(b, gp);
992                }
993                if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
994                    B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B
995                }
996            }
997            if (!b.isZERO() && !b.isConstant() /*&& !B.contains(b)*/) {
998                B.add(b); // gcd(a,b) == 1 and gcd(b,c) == 1 for c != b in P, B
999            }
1000        }
1001        if (!a.isZERO() && !a.isConstant() /*&& !B.contains(a)*/) {
1002            B.add(a);
1003        }
1004        return B;
1005    }
1006
1007
1008    /**
1009     * GenSolvablePolynomial test for co-prime list.
1010     * @param A list of GenSolvablePolynomials.
1011     * @return true if gcd(b,c) = 1 for all b != c in B, else false.
1012     */
1013    public boolean isLeftCoPrime(List<GenSolvablePolynomial<C>> A) {
1014        if (A == null || A.isEmpty()) {
1015            return true;
1016        }
1017        if (A.size() == 1) {
1018            return true;
1019        }
1020        for (int i = 0; i < A.size(); i++) {
1021            GenSolvablePolynomial<C> a = A.get(i);
1022            for (int j = i + 1; j < A.size(); j++) {
1023                GenSolvablePolynomial<C> b = A.get(j);
1024                GenSolvablePolynomial<C> g = leftGcd(a, b);
1025                if (!g.isONE()) {
1026                    System.out.println("not co-prime, a: " + a);
1027                    System.out.println("not co-prime, b: " + b);
1028                    System.out.println("not co-prime, g: " + g);
1029                    return false;
1030                }
1031            }
1032        }
1033        return true;
1034    }
1035
1036
1037    /**
1038     * GenSolvablePolynomial test for left co-prime list of given list.
1039     * @param A list of GenSolvablePolynomials.
1040     * @param P list of co-prime GenSolvablePolynomials.
1041     * @return true if isCoPrime(P) and for all a in A exists p in P with p | a,
1042     *         else false.
1043     */
1044    public boolean isLeftCoPrime(List<GenSolvablePolynomial<C>> P, List<GenSolvablePolynomial<C>> A) {
1045        if (!isLeftCoPrime(P)) {
1046            return false;
1047        }
1048        if (A == null || A.isEmpty()) {
1049            return true;
1050        }
1051        for (GenSolvablePolynomial<C> q : A) {
1052            if (q.isZERO() || q.isConstant()) {
1053                continue;
1054            }
1055            boolean divides = false;
1056            for (GenSolvablePolynomial<C> p : P) {
1057                GenSolvablePolynomial<C> a = FDUtil.<C> leftBaseSparsePseudoRemainder(q, p);
1058                if (a.isZERO()) { // p divides q
1059                    divides = true;
1060                    break;
1061                }
1062            }
1063            if (!divides) {
1064                System.out.println("no divisor for: " + q);
1065                return false;
1066            }
1067        }
1068        return true;
1069    }
1070
1071
1072    /**
1073     * Univariate GenSolvablePolynomial extended greatest common divisor. Uses
1074     * sparse pseudoRemainder for remainder.
1075     * @param P univariate GenSolvablePolynomial.
1076     * @param S univariate GenSolvablePolynomial.
1077     * @return [ gcd(P,S), a, b ] with a*P + b*S = gcd(P,S).
1078     */
1079    @SuppressWarnings({ "unchecked", "cast" })
1080    public GenSolvablePolynomial<C>[] baseExtendedGcd(GenSolvablePolynomial<C> P,
1081                    GenSolvablePolynomial<C> S) {
1082        //return P.egcd(S);
1083        GenSolvablePolynomial<C>[] hegcd = baseHalfExtendedGcd(P, S);
1084        GenSolvablePolynomial<C>[] ret = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[3];
1085        ret[0] = hegcd[0];
1086        ret[1] = hegcd[1];
1087        GenSolvablePolynomial<C> x = (GenSolvablePolynomial<C>) hegcd[0].subtract(hegcd[1].multiply(P));
1088        GenSolvablePolynomial<C>[] qr = FDUtil.<C> leftBasePseudoQuotientRemainder(x, S);
1089        // assert qr[1].isZERO() 
1090        ret[2] = qr[0];
1091        return ret;
1092    }
1093
1094
1095    /**
1096     * Univariate GenSolvablePolynomial half extended greatest comon divisor.
1097     * Uses sparse pseudoRemainder for remainder.
1098     * @param S GenSolvablePolynomial.
1099     * @return [ gcd(P,S), a ] with a*P + b*S = gcd(P,S).
1100     */
1101    @SuppressWarnings({ "unchecked", "cast" })
1102    public GenSolvablePolynomial<C>[] baseHalfExtendedGcd(GenSolvablePolynomial<C> P,
1103                    GenSolvablePolynomial<C> S) {
1104        if (P == null || S == null) {
1105            throw new IllegalArgumentException("null P or S not allowed");
1106        }
1107        GenSolvablePolynomial<C>[] ret = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2];
1108        ret[0] = null;
1109        ret[1] = null;
1110        if (S.isZERO()) {
1111            ret[0] = P;
1112            ret[1] = P.ring.getONE();
1113            return ret;
1114        }
1115        if (P.isZERO()) {
1116            ret[0] = S;
1117            ret[1] = S.ring.getZERO();
1118            return ret;
1119        }
1120        if (P.ring.nvar != 1) {
1121            throw new IllegalArgumentException("for univariate polynomials only " + P.ring);
1122        }
1123        GenSolvablePolynomial<C> q = P;
1124        GenSolvablePolynomial<C> r = S;
1125        GenSolvablePolynomial<C> c1 = P.ring.getONE().copy();
1126        GenSolvablePolynomial<C> d1 = P.ring.getZERO().copy();
1127        while (!r.isZERO()) {
1128            GenSolvablePolynomial<C>[] qr = FDUtil.<C> leftBasePseudoQuotientRemainder(q, r);
1129            //q.divideAndRemainder(r);
1130            q = qr[0];
1131            GenSolvablePolynomial<C> x = (GenSolvablePolynomial<C>) c1.subtract(q.multiply(d1));
1132            c1 = d1;
1133            d1 = x;
1134            q = r;
1135            r = qr[1];
1136        }
1137        // normalize ldcf(q) to 1, i.e. make monic
1138        C g = q.leadingBaseCoefficient();
1139        if (g.isUnit()) {
1140            C h = g.inverse();
1141            q = q.multiply(h);
1142            c1 = c1.multiply(h);
1143        }
1144        //assert ( ((c1.multiply(P)).remainder(S).equals(q) )); 
1145        ret[0] = q;
1146        ret[1] = c1;
1147        return ret;
1148    }
1149
1150
1151    /**
1152     * Univariate GenSolvablePolynomial greatest common divisor diophantine
1153     * version.
1154     * @param P univariate GenSolvablePolynomial.
1155     * @param S univariate GenSolvablePolynomial.
1156     * @param c univariate GenSolvablePolynomial.
1157     * @return [ a, b ] with a*P + b*S = c and deg(a) &lt; deg(S).
1158     */
1159    @SuppressWarnings({ "unchecked", "cast" })
1160    public GenSolvablePolynomial<C>[] baseGcdDiophant(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S,
1161                    GenSolvablePolynomial<C> c) {
1162        GenSolvablePolynomial<C>[] egcd = baseExtendedGcd(P, S);
1163        GenSolvablePolynomial<C> g = egcd[0];
1164        GenSolvablePolynomial<C>[] qr = FDUtil.<C> leftBasePseudoQuotientRemainder(c, g);
1165        if (!qr[1].isZERO()) {
1166            throw new ArithmeticException("not solvable, r = " + qr[1] + ", c = " + c + ", g = " + g);
1167        }
1168        GenSolvablePolynomial<C> q = qr[0];
1169        GenSolvablePolynomial<C> a = egcd[1].multiply(q);
1170        GenSolvablePolynomial<C> b = egcd[2].multiply(q);
1171        if (!a.isZERO() && a.degree(0) >= S.degree(0)) {
1172            qr = FDUtil.<C> leftBasePseudoQuotientRemainder(a, S);
1173            a = qr[1];
1174            b = (GenSolvablePolynomial<C>) b.sum(P.multiply(qr[0]));
1175        }
1176        GenSolvablePolynomial<C>[] ret = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2];
1177        ret[0] = a;
1178        ret[1] = b;
1179        if (debug) {
1180            GenSolvablePolynomial<C> y = (GenSolvablePolynomial<C>) ret[0].multiply(P)
1181                            .sum(ret[1].multiply(S));
1182            if (!y.equals(c)) {
1183                System.out.println("P  = " + P);
1184                System.out.println("S  = " + S);
1185                System.out.println("c  = " + c);
1186                System.out.println("a  = " + a);
1187                System.out.println("b  = " + b);
1188                System.out.println("y  = " + y);
1189                throw new ArithmeticException("not diophant, x = " + y.subtract(c));
1190            }
1191        }
1192        return ret;
1193    }
1194
1195
1196    /**
1197     * Coefficient left Ore condition. Generators for the left Ore condition of
1198     * two coefficients.
1199     * @param a coefficient.
1200     * @param b coefficient.
1201     * @return [oa, ob] = leftOreCond(a,b), with oa*a == ob*b.
1202     */
1203    @SuppressWarnings("unchecked")
1204    public C[] leftOreCond(C a, C b) {
1205        if (a == null || a.isZERO() || b == null || b.isZERO()) {
1206            throw new IllegalArgumentException("a and b must be non zero");
1207        }
1208        C[] oc = (C[]) new GcdRingElem[2];
1209        if (a instanceof GenSolvablePolynomial && b instanceof GenSolvablePolynomial) {
1210            GenSolvablePolynomial ap = (GenSolvablePolynomial) a;
1211            GenSolvablePolynomial bp = (GenSolvablePolynomial) b;
1212            GenSolvablePolynomial[] ocp = leftOreCond(ap, bp);
1213            oc[0] = (C) ocp[0];
1214            oc[1] = (C) ocp[1];
1215            return oc;
1216        }
1217        RingFactory<C> rf = coFac; // not usable: (RingFactory<C>) a.factory();
1218        if (a.equals(b)) { // required because of rationals gcd
1219            oc[0] = rf.getONE();
1220            oc[1] = rf.getONE();
1221            logger.info("Ore multiple: " + Arrays.toString(oc));
1222            return oc;
1223        }
1224        if (a.equals(b.negate())) { // required because of rationals gcd
1225            oc[0] = rf.getONE();
1226            oc[1] = rf.getONE().negate();
1227            logger.info("Ore multiple: " + Arrays.toString(oc));
1228            return oc;
1229        }
1230        if (rf.isCommutative()) {
1231            if (debug) {
1232                logger.info("left Ore condition on coefficients, commutative case: " + a + ", " + b);
1233            }
1234            C gcd = a.gcd(b);
1235            if (gcd.isONE()) {
1236                oc[0] = b;
1237                oc[1] = a;
1238                if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) {
1239                    oc[0] = oc[0].negate();
1240                    oc[1] = oc[1].negate();
1241                }
1242                logger.info("Ore multiple: " + Arrays.toString(oc));
1243                return oc;
1244            }
1245            C p = a.multiply(b);
1246            C lcm = p.divide(gcd).abs();
1247            oc[0] = lcm.divide(a);
1248            oc[1] = lcm.divide(b);
1249            if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) {
1250                oc[0] = oc[0].negate();
1251                oc[1] = oc[1].negate();
1252            }
1253            logger.info("Ore multiple: lcm=" + lcm + ", gcd=" + gcd + ", " + Arrays.toString(oc));
1254            return oc;
1255        }
1256        // now non-commutative
1257        if (rf.isField()) {
1258            logger.info("left Ore condition on coefficients, skew field " + rf + " case: " + a + ", " + b);
1259            //C gcd = a.gcd(b); // always one 
1260            //C lcm = rf.getONE();
1261            oc[0] = a.inverse(); //lcm.divide(a);
1262            oc[1] = b.inverse(); //lcm.divide(b);
1263            logger.info("Ore multiple: " + Arrays.toString(oc));
1264            return oc;
1265        }
1266        if (b instanceof StarRingElem) {
1267            logger.info("left Ore condition on coefficients, StarRing case: " + a + ", " + b);
1268            C bs = (C) ((StarRingElem) b).conjugate();
1269            oc[0] = bs.multiply(b); // bar(b) b a = s a 
1270            oc[1] = a.multiply(bs); // a bar(b) b = a s
1271            logger.info("Ore multiple: " + Arrays.toString(oc));
1272            return oc;
1273        }
1274        throw new UnsupportedOperationException(
1275                        "leftOreCond not implemented for " + rf.getClass() + ", rf = " + rf.toScript());
1276        //return oc;
1277    }
1278
1279
1280    /**
1281     * Left Ore condition. Generators for the left Ore condition of two solvable
1282     * polynomials.
1283     * @param a solvable polynomial
1284     * @param b solvable polynomial
1285     * @return [p,q] with p*a = q*b
1286     */
1287    @SuppressWarnings({ "unchecked", "cast" })
1288    public GenSolvablePolynomial<C>[] leftOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b) {
1289        if (a == null || a.isZERO() || b == null || b.isZERO()) {
1290            throw new IllegalArgumentException("a and b must be non zero");
1291        }
1292        GenSolvablePolynomialRing<C> pfac = a.ring;
1293        GenSolvablePolynomial<C>[] oc = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2];
1294        if (a.equals(b)) {
1295            oc[0] = pfac.getONE();
1296            oc[1] = pfac.getONE();
1297            return oc;
1298        }
1299        if (a.equals(b.negate())) {
1300            oc[0] = pfac.getONE();
1301            oc[1] = (GenSolvablePolynomial<C>) pfac.getONE().negate();
1302            return oc;
1303        }
1304        if (pfac.isCommutative()) {
1305            logger.info("left Ore condition, polynomial commutative case: " + a + ", " + b);
1306            edu.jas.ufd.GreatestCommonDivisorAbstract<C> cgcd = GCDFactory.<C> getImplementation(pfac.coFac);
1307            GenSolvablePolynomial<C> lcm = (GenSolvablePolynomial<C>) cgcd.lcm(a, b);
1308            //oc[0] = FDUtil.<C> basePseudoQuotient(lcm, a);
1309            //oc[1] = FDUtil.<C> basePseudoQuotient(lcm, b);
1310            oc[0] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, a);
1311            oc[1] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, b);
1312            logger.info("Ore multiple: " + lcm + ", " + Arrays.toString(oc));
1313            return oc;
1314        }
1315        oc = syz.leftOreCond(a, b);
1316        //logger.info("Ore multiple: " + oc[0].multiply(a) + ", " + Arrays.toString(oc));
1317        return oc;
1318    }
1319
1320
1321    /**
1322     * Coefficient rigth Ore condition. Generators for the right Ore condition
1323     * of two coefficients.
1324     * @param a coefficient.
1325     * @param b coefficient.
1326     * @return [oa, ob] = rightOreCond(a,b), with a*oa == b*ob.
1327     */
1328    @SuppressWarnings("unchecked")
1329    public C[] rightOreCond(C a, C b) {
1330        if (a == null || a.isZERO() || b == null || b.isZERO()) {
1331            throw new IllegalArgumentException("a and b must be non zero");
1332        }
1333        C[] oc = (C[]) new GcdRingElem[2];
1334        if (a instanceof GenSolvablePolynomial && b instanceof GenSolvablePolynomial) {
1335            GenSolvablePolynomial ap = (GenSolvablePolynomial) a;
1336            GenSolvablePolynomial bp = (GenSolvablePolynomial) b;
1337            GenSolvablePolynomial[] ocp = rightOreCond(ap, bp);
1338            oc[0] = (C) ocp[0];
1339            oc[1] = (C) ocp[1];
1340            return oc;
1341        }
1342        RingFactory<C> rf = coFac; // not usable: (RingFactory<C>) a.factory();
1343        if (a.equals(b)) { // required because of rationals gcd
1344            oc[0] = rf.getONE();
1345            oc[1] = rf.getONE();
1346            return oc;
1347        }
1348        if (a.equals(b.negate())) { // required because of rationals gcd
1349            oc[0] = rf.getONE();
1350            oc[1] = rf.getONE().negate();
1351            return oc;
1352        }
1353        if (rf.isCommutative()) {
1354            logger.info("right Ore condition on coefficients, commutative case: " + a + ", " + b);
1355            C gcd = a.gcd(b);
1356            if (gcd.isONE()) {
1357                oc[0] = b;
1358                oc[1] = a;
1359                if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) {
1360                    oc[0] = oc[0].negate();
1361                    oc[1] = oc[1].negate();
1362                }
1363                return oc;
1364            }
1365            C p = a.multiply(b);
1366            C lcm = p.divide(gcd).abs();
1367            oc[0] = lcm.divide(a);
1368            oc[1] = lcm.divide(b);
1369            if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) {
1370                oc[0] = oc[0].negate();
1371                oc[1] = oc[1].negate();
1372            }
1373            logger.info("Ore multiple: " + lcm + ", " + Arrays.toString(oc));
1374            return oc;
1375        }
1376        // now non-commutative
1377        if (rf.isField()) {
1378            logger.info("right Ore condition on coefficients, skew field " + rf + " case: " + a + ", " + b);
1379            //C gcd = a.gcd(b); // always one 
1380            //C lcm = rf.getONE();
1381            oc[0] = a.inverse(); //lcm.divide(a);
1382            oc[1] = b.inverse(); //lcm.divide(b);
1383            logger.info("Ore multiple: " + Arrays.toString(oc));
1384            return oc;
1385        }
1386        if (b instanceof StarRingElem) {
1387            logger.info("right Ore condition on coefficients, StarRing case: " + a + ", " + b);
1388            C bs = (C) ((StarRingElem) b).conjugate();
1389            oc[0] = b.multiply(bs); // a b bar(b) = a s
1390            oc[1] = bs.multiply(a); // b bar(b) a = s a 
1391            logger.info("Ore multiple: " + Arrays.toString(oc));
1392            return oc;
1393        }
1394        throw new UnsupportedOperationException(
1395                        "rightOreCond not implemented for " + rf.getClass() + ", rf = " + rf.toScript());
1396        //return oc;
1397    }
1398
1399
1400    /**
1401     * Right Ore condition. Generators for the right Ore condition of two
1402     * solvable polynomials.
1403     * @param a solvable polynomial
1404     * @param b solvable polynomial
1405     * @return [p,q] with a*p = b*q
1406     */
1407    @SuppressWarnings({ "unchecked", "cast" })
1408    public GenSolvablePolynomial<C>[] rightOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b) {
1409        if (a == null || a.isZERO() || b == null || b.isZERO()) {
1410            throw new IllegalArgumentException("a and b must be non zero");
1411        }
1412        GenSolvablePolynomialRing<C> pfac = a.ring;
1413        GenSolvablePolynomial<C>[] oc = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2];
1414        if (a.equals(b)) {
1415            oc[0] = pfac.getONE();
1416            oc[1] = pfac.getONE();
1417            return oc;
1418        }
1419        if (a.equals(b.negate())) {
1420            oc[0] = pfac.getONE();
1421            oc[1] = (GenSolvablePolynomial<C>) pfac.getONE().negate();
1422            return oc;
1423        }
1424        if (pfac.isCommutative()) {
1425            logger.info("right Ore condition, polynomial commutative case: " + a + ", " + b);
1426            edu.jas.ufd.GreatestCommonDivisorAbstract<C> cgcd = GCDFactory.<C> getImplementation(pfac.coFac);
1427            GenSolvablePolynomial<C> lcm = (GenSolvablePolynomial<C>) cgcd.lcm(a, b);
1428            //oc[0] = FDUtil.<C> basePseudoQuotient(lcm, a);
1429            //oc[1] = FDUtil.<C> basePseudoQuotient(lcm, b);
1430            oc[0] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, a);
1431            oc[1] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, b);
1432            logger.info("Ore multiple: " + lcm + ", " + Arrays.toString(oc));
1433            return oc;
1434        }
1435        oc = syz.rightOreCond(a, b);
1436        //logger.info("Ore multiple: " + oc[0].multiply(a) + ", " + Arrays.toString(oc));
1437        return oc;
1438    }
1439
1440}