001/*
002 * $Id$
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.LogManager;
013import org.apache.logging.log4j.Logger;
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, mainly for Ore conditions.
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.multiply(d.inverse()); // avoid the divisions
210        }
211        GenSolvablePolynomial<C> pp = (GenSolvablePolynomial<C>) P.rightDivideCoeff(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 UnsupportedOperationException("RecSolvablePolynomial with non empty coeffTable");
258            }
259        }
260        if (P.isZERO()) {
261            return (GenSolvablePolynomial<C>) P.ring.getZEROCoefficient();
262        }
263        if (P.leadingBaseCoefficient().isONE()) {
264            return (GenSolvablePolynomial<C>) P.ring.getONECoefficient();
265        }
266        GenSolvablePolynomial<C> d = null;
267        for (GenPolynomial<C> cp : P.getMap().values()) {
268            GenSolvablePolynomial<C> c = (GenSolvablePolynomial<C>) cp;
269            if (d == null) {
270                d = c;
271            } else {
272                ///d = leftGcd(d, c); // go to recursion
273                d = rightGcd(d, c); // go to recursion
274            }
275            if (d.isONE()) {
276                return d;
277            }
278        }
279        return (GenSolvablePolynomial<C>) d.abs();
280    }
281
282
283    /**
284     * GenSolvablePolynomial left recursive content.
285     * @param P recursive GenSolvablePolynomial.
286     * @return cont(P) with cont(P)*pp(P) = P.
287     */
288    public GenSolvablePolynomial<C> leftRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) {
289        if (P == null) {
290            throw new IllegalArgumentException("P != null");
291        }
292        if (P.isZERO()) {
293            return (GenSolvablePolynomial<C>) P.ring.getZEROCoefficient();
294        }
295        if (P.leadingBaseCoefficient().isONE()) {
296            return (GenSolvablePolynomial<C>) P.ring.getONECoefficient();
297        }
298        GenSolvablePolynomial<C> d = null, cs = null;
299        GenSolvablePolynomial<GenPolynomial<C>> Pr = P; //FDUtil.<C> rightRecursivePolynomial(P);
300        logger.info("recCont: P = {}, left(P) = {}", P, Pr);
301        for (GenPolynomial<C> c : Pr.getMap().values()) {
302            cs = (GenSolvablePolynomial<C>) c;
303            if (d == null) {
304                d = cs;
305            } else {
306                d = leftGcd(d, cs); // go to recursion
307                logger.info("recCont: cs = {}, d = {}", cs, d);
308            }
309            if (d.isONE()) {
310                return d;
311            }
312        }
313        return (GenSolvablePolynomial<C>) d.abs();
314    }
315
316
317    /**
318     * GenSolvablePolynomial right recursive content.
319     * @param P recursive GenSolvablePolynomial.
320     * @return cont(P) with pp(P)*cont(P) = P.
321     */
322    public GenSolvablePolynomial<C> rightRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) {
323        if (P == null) {
324            throw new IllegalArgumentException("P != null");
325        }
326        if (P.isZERO()) {
327            return (GenSolvablePolynomial<C>) P.ring.getZEROCoefficient();
328        }
329        if (P.leadingBaseCoefficient().isONE()) {
330            return (GenSolvablePolynomial<C>) P.ring.getONECoefficient();
331        }
332        GenSolvablePolynomial<C> d = null, cs = null, x;
333        GenSolvablePolynomial<GenPolynomial<C>> Pr = P.rightRecursivePolynomial();
334        logger.warn("RI-recCont: P = {}, right(P) = {}", P, Pr);
335        for (GenPolynomial<C> c : Pr.getMap().values()) {
336            cs = (GenSolvablePolynomial<C>) c;
337            if (d == null) {
338                d = cs;
339            } else {
340                x = d;
341                d = leftGcd(d, cs); // go to recursion, P = P'*gcd(P,S)
342                ///d = rightGcd(d, cs); // go to recursion,  P = gcd(P,S)*P'
343                logger.info("RI-recCont: d = {}, cs = {}, d = {}", x, cs, d);
344            }
345            if (d.isONE()) {
346                return d;
347            }
348        }
349        return (GenSolvablePolynomial<C>) d.abs();// todo: eval right ?
350    }
351
352
353    /**
354     * GenSolvablePolynomial left recursive primitive part.
355     * @param P recursive GenSolvablePolynomial.
356     * @return pp(P) with cont(P)*pp(P) = P.
357     */
358    public GenSolvablePolynomial<GenPolynomial<C>> leftRecursivePrimitivePart(
359                    GenSolvablePolynomial<GenPolynomial<C>> P) {
360        if (P == null) {
361            throw new IllegalArgumentException("P == null");
362        }
363        if (P.isZERO()) {
364            return P;
365        }
366        GenSolvablePolynomial<C> d = leftRecursiveContent(P);
367        if (d.isONE()) {
368            return P;
369        }
370        GenSolvablePolynomial<GenPolynomial<C>> pp;
371        //pp = FDUtil.<C> recursiveRightDivide(P, d);
372        pp = FDUtil.<C> recursiveLeftDivide(P, d);
373        if (debug) { // not checkable
374            if (!P.equals(pp.multiplyLeft(d))) {
375                System.out.println("ppart, P         = " + P);
376                System.out.println("ppart, cont(P)   = " + d);
377                System.out.println("ppart, pp(P)     = " + pp);
378                System.out.println("ppart, pp(P)c(P) = " + pp.multiplyLeft(d));
379                throw new RuntimeException("primitivePart: P != cont(P)*pp(P)");
380            }
381        }
382        return pp;
383    }
384
385
386    /**
387     * GenSolvablePolynomial right recursive primitive part.
388     * @param P recursive GenSolvablePolynomial.
389     * @return pp(P) with pp(P)*cont(P) = P.
390     */
391    public GenSolvablePolynomial<GenPolynomial<C>> rightRecursivePrimitivePart(
392                    GenSolvablePolynomial<GenPolynomial<C>> P) {
393        if (P == null) {
394            throw new IllegalArgumentException("P == null");
395        }
396        if (P.isZERO()) {
397            return P;
398        }
399        GenSolvablePolynomial<C> d = rightRecursiveContent(P);
400        if (d.isONE()) {
401            return P;
402        }
403        GenSolvablePolynomial<GenPolynomial<C>> pp;
404        pp = FDUtil.<C> recursiveRightDivide(P, d); //RightEval
405        if (debug) { // not checkable
406            if (!P.equals(pp.multiply(d))) {
407                System.out.println("RI-ppart, P         = " + P);
408                System.out.println("RI-ppart, cont(P)   = " + d);
409                System.out.println("RI-ppart, pp(P)     = " + pp);
410                System.out.println("RI-ppart, pp(P)c(P) = " + pp.multiply(d));
411                throw new RuntimeException("RI-primitivePart: P != pp(P)*cont(P)");
412            }
413        }
414        return pp;
415    }
416
417
418    /**
419     * GenSolvablePolynomial base recursive content.
420     * @param P recursive GenSolvablePolynomial.
421     * @return baseCont(P) with pp(P)*cont(P) = P.
422     */
423    public C baseRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) {
424        if (P == null) {
425            throw new IllegalArgumentException("P == null");
426        }
427        if (P.isZERO()) {
428            GenSolvablePolynomialRing<C> cf = (GenSolvablePolynomialRing<C>) P.ring.coFac;
429            return cf.coFac.getZERO();
430        }
431        C d = null;
432        for (GenPolynomial<C> cp : P.getMap().values()) {
433            GenSolvablePolynomial<C> c = (GenSolvablePolynomial<C>) cp;
434            C cc = leftBaseContent(c);
435            if (d == null) {
436                d = cc;
437            } else {
438                d = gcd(d, cc);
439            }
440            if (d.isONE()) {
441                return d;
442            }
443        }
444        return d.abs();
445    }
446
447
448    /**
449     * GenSolvablePolynomial base recursive primitive part.
450     * @param P recursive GenSolvablePolynomial.
451     * @return basePP(P) with pp(P)*cont(P) = P.
452     */
453    public GenSolvablePolynomial<GenPolynomial<C>> baseRecursivePrimitivePart(
454                    GenSolvablePolynomial<GenPolynomial<C>> P) {
455        if (P == null) {
456            throw new IllegalArgumentException("P == null");
457        }
458        if (P.isZERO()) {
459            return P;
460        }
461        C d = baseRecursiveContent(P);
462        if (d.isONE()) {
463            return P;
464        }
465        GenSolvablePolynomial<GenPolynomial<C>> pp = (GenSolvablePolynomial<GenPolynomial<C>>) PolyUtil
466                        .<C> baseRecursiveDivide(P, d);
467        return pp;
468    }
469
470
471    /**
472     * GenSolvablePolynomial left recursive greatest common divisor. Uses
473     * pseudoRemainder for remainder.
474     * @param P recursive GenSolvablePolynomial.
475     * @param S recursive GenSolvablePolynomial.
476     * @return gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where
477     *         deg_main(p) = deg_main(s) == 0.
478     */
479    @SuppressWarnings("unchecked")
480    public GenSolvablePolynomial<GenPolynomial<C>> leftRecursiveGcd(GenSolvablePolynomial<GenPolynomial<C>> P,
481                    GenSolvablePolynomial<GenPolynomial<C>> S) {
482        if (S == null || S.isZERO()) {
483            return P;
484        }
485        if (P == null || P.isZERO()) {
486            return S;
487        }
488        if (P.ring.nvar == 1) {
489            return leftRecursiveUnivariateGcd(P, S);
490        }
491        // distributed polynomials gcd
492        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = P.ring;
493        GenSolvablePolynomialRing<C> dfac;
494        if (rfac instanceof RecSolvablePolynomialRing) {
495            RecSolvablePolynomialRing<C> rf = (RecSolvablePolynomialRing<C>) rfac;
496            dfac = RecSolvablePolynomialRing.<C> distribute(rf);
497        } else {
498            GenSolvablePolynomialRing<C> df = (GenSolvablePolynomialRing) rfac;
499            dfac = df.distribute();
500        }
501        GenSolvablePolynomial<C> Pd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, P);
502        GenSolvablePolynomial<C> Sd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, S);
503        // left gcd
504        GenSolvablePolynomial<C> Dd = leftGcd(Pd, Sd);
505        // convert back to recursive
506        GenSolvablePolynomial<GenPolynomial<C>> C = (GenSolvablePolynomial<GenPolynomial<C>>) PolyUtil
507                        .<C> recursive(rfac, Dd);
508        return C;
509    }
510
511
512    /**
513     * GenSolvablePolynomial right recursive greatest common divisor. Uses
514     * pseudoRemainder for remainder.
515     * @param P recursive GenSolvablePolynomial.
516     * @param S recursive GenSolvablePolynomial.
517     * @return gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where
518     *         deg_main(p) = deg_main(s) == 0.
519     */
520    @SuppressWarnings("unchecked")
521    public GenSolvablePolynomial<GenPolynomial<C>> rightRecursiveGcd(
522                    GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) {
523        if (S == null || S.isZERO()) {
524            return P;
525        }
526        if (P == null || P.isZERO()) {
527            return S;
528        }
529        if (P.ring.nvar == 1) {
530            return rightRecursiveUnivariateGcd(P, S);
531        }
532        // distributed polynomials gcd
533        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = P.ring;
534        GenSolvablePolynomialRing<C> dfac;
535        if (rfac instanceof RecSolvablePolynomialRing) {
536            RecSolvablePolynomialRing<C> rf = (RecSolvablePolynomialRing<C>) rfac;
537            dfac = RecSolvablePolynomialRing.<C> distribute(rf);
538        } else {
539            GenSolvablePolynomialRing<C> df = (GenSolvablePolynomialRing) rfac;
540            dfac = df.distribute();
541        }
542        GenSolvablePolynomial<C> Pd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, P);
543        GenSolvablePolynomial<C> Sd = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(dfac, S);
544        GenSolvablePolynomial<C> Dd = rightGcd(Pd, Sd);
545        // convert to recursive
546        GenSolvablePolynomial<GenPolynomial<C>> C = (GenSolvablePolynomial<GenPolynomial<C>>) PolyUtil
547                        .<C> recursive(rfac, Dd);
548        return C;
549    }
550
551
552    /**
553     * Univariate GenSolvablePolynomial recursive greatest common divisor. Uses
554     * pseudoRemainder for remainder.
555     * @param P univariate recursive GenSolvablePolynomial.
556     * @param S univariate recursive GenSolvablePolynomial.
557     * @return gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where
558     *         deg_main(p) = deg_main(s) == 0.
559     */
560    public abstract GenSolvablePolynomial<GenPolynomial<C>> leftRecursiveUnivariateGcd(
561                    GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S);
562
563
564    /**
565     * Univariate GenSolvablePolynomial right recursive greatest common divisor.
566     * Uses pseudoRemainder for remainder.
567     * @param P univariate recursive GenSolvablePolynomial.
568     * @param S univariate recursive GenSolvablePolynomial.
569     * @return gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where
570     *         deg_main(p) = deg_main(s) == 0.
571     */
572    public abstract GenSolvablePolynomial<GenPolynomial<C>> rightRecursiveUnivariateGcd(
573                    GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S);
574
575
576    /**
577     * GenSolvablePolynomial left content.
578     * @param P GenSolvablePolynomial.
579     * @return cont(P) with cont(P)*pp(P) = P.
580     */
581    public GenSolvablePolynomial<C> leftContent(GenSolvablePolynomial<C> P) {
582        if (P == null) {
583            throw new IllegalArgumentException("P == null");
584        }
585        GenSolvablePolynomialRing<C> pfac = P.ring;
586        if (pfac.nvar <= 1) {
587            // baseContent not possible by return type
588            throw new IllegalArgumentException("use baseContent() for univariate polynomials");
589        }
590        GenSolvablePolynomialRing<GenPolynomial<C>> rfac // = (RecSolvablePolynomialRing<C>) 
591                        = pfac.recursive(1);
592
593        GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac,
594                        P);
595        GenSolvablePolynomial<C> D = leftRecursiveContent(Pr);
596        return D;
597    }
598
599
600    /**
601     * GenSolvablePolynomial left primitive part.
602     * @param P GenSolvablePolynomial.
603     * @return pp(P) with cont(P)*pp(P) = P.
604     */
605    public GenSolvablePolynomial<C> leftPrimitivePart(GenSolvablePolynomial<C> P) {
606        if (P == null) {
607            throw new IllegalArgumentException("P == null");
608        }
609        if (P.isZERO()) {
610            return P;
611        }
612        GenSolvablePolynomialRing<C> pfac = P.ring;
613        if (pfac.nvar <= 1) {
614            return leftBasePrimitivePart(P);
615        }
616        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = /*(RecSolvablePolynomialRing<C>)*/pfac
617                        .recursive(1);
618
619        GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac,
620                        P);
621        GenSolvablePolynomial<GenPolynomial<C>> PP = leftRecursivePrimitivePart(Pr);
622
623        GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, PP);
624        return D;
625    }
626
627
628    /**
629     * GenSolvablePolynomial right content.
630     * @param P GenSolvablePolynomial.
631     * @return cont(P) with pp(P)*cont(P) = P.
632     */
633    public GenSolvablePolynomial<C> rightContent(GenSolvablePolynomial<C> P) {
634        if (P == null) {
635            throw new IllegalArgumentException("P == null");
636        }
637        GenSolvablePolynomialRing<C> pfac = P.ring;
638        if (pfac.nvar <= 1) {
639            // baseContent not possible by return type
640            throw new IllegalArgumentException("use baseContent() for univariate polynomials");
641        }
642        GenSolvablePolynomialRing<GenPolynomial<C>> rfac // = (RecSolvablePolynomialRing<C>) 
643                        = pfac.recursive(1);
644
645        GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac,
646                        P);
647        GenSolvablePolynomial<C> D = rightRecursiveContent(Pr);
648        return D;
649    }
650
651
652    /**
653     * GenSolvablePolynomial right primitive part.
654     * @param P GenSolvablePolynomial.
655     * @return pp(P) with pp(P)*cont(P) = P.
656     */
657    public GenSolvablePolynomial<C> rightPrimitivePart(GenSolvablePolynomial<C> P) {
658        if (P == null) {
659            throw new IllegalArgumentException("P == null");
660        }
661        if (P.isZERO()) {
662            return P;
663        }
664        GenSolvablePolynomialRing<C> pfac = P.ring;
665        if (pfac.nvar <= 1) {
666            return rightBasePrimitivePart(P);
667        }
668        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = /*(RecSolvablePolynomialRing<C>)*/pfac
669                        .recursive(1);
670
671        GenSolvablePolynomial<GenPolynomial<C>> Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac,
672                        P);
673        GenSolvablePolynomial<GenPolynomial<C>> PP = rightRecursivePrimitivePart(Pr);
674
675        GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, PP);
676        return D;
677    }
678
679
680    /**
681     * GenSolvablePolynomial division. Indirection to GenSolvablePolynomial
682     * method.
683     * @param a GenSolvablePolynomial.
684     * @param b coefficient.
685     * @return a' = a/b with a = a'*b.
686     */
687    public GenSolvablePolynomial<C> divide(GenSolvablePolynomial<C> a, C b) {
688        if (b == null || b.isZERO()) {
689            throw new IllegalArgumentException("division by zero");
690
691        }
692        if (a == null || a.isZERO()) {
693            return a;
694        }
695        return (GenSolvablePolynomial<C>) a.leftDivideCoeff(b);
696    }
697
698
699    /**
700     * GenSolvablePolynomial right division. Indirection to GenSolvablePolynomial
701     * method.
702     * @param a GenSolvablePolynomial.
703     * @param b coefficient.
704     * @return a' = a/b with a = b*a'.
705     */
706    public GenSolvablePolynomial<C> rightDivide(GenSolvablePolynomial<C> a, C b) {
707        if (b == null || b.isZERO()) {
708            throw new IllegalArgumentException("division by zero");
709    
710        }
711        if (a == null || a.isZERO()) {
712            return a;
713        }
714        return (GenSolvablePolynomial<C>) a.rightDivideCoeff(b);
715    }
716
717
718    /**
719     * Coefficient greatest common divisor. Indirection to coefficient method.
720     * @param a coefficient.
721     * @param b coefficient.
722     * @return gcd(a,b) with a = gcd(a,b)*a' and b = gcd(a,b)*b'.
723     */
724    public C gcd(C a, C b) {
725        if (b == null || b.isZERO()) {
726            return a;
727        }
728        if (a == null || a.isZERO()) {
729            return b;
730        }
731        return a.gcd(b);
732    }
733
734
735    /**
736     * Coefficient greatest common divisor. Indirection to coefficient method.
737     * @param a coefficient.
738     * @param b coefficient.
739     * @return gcd(a,b) with a = gcd(a,b)*a' and b = gcd(a,b)*b'.
740     */
741    public C leftGcd(C a, C b) {
742        return a.leftGcd(b);
743    }
744
745
746    /**
747     * GenSolvablePolynomial greatest common divisor.
748     * @param P GenSolvablePolynomial.
749     * @param S GenSolvablePolynomial.
750     * @return gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where
751     *         deg_main(p) = deg_main(s) == 0.
752     */
753    public GenSolvablePolynomial<C> leftGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
754        if (S == null || S.isZERO()) {
755            return P;
756        }
757        if (P == null || P.isZERO()) {
758            return S;
759        }
760        if (P.isONE()) {
761            return P;
762        }
763        if (S.isONE()) {
764            return S;
765        }
766        GenSolvablePolynomialRing<C> pfac = P.ring;
767        if (pfac.nvar <= 1) {
768            GenSolvablePolynomial<C> T = leftBaseGcd(P, S);
769            return T;
770        }
771        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); //RecSolvablePolynomialRing<C>
772        GenSolvablePolynomial<GenPolynomial<C>> Pr, Sr, Dr;
773        Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, P);
774        Sr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, S);
775        Dr = leftRecursiveUnivariateGcd(Pr, Sr);
776        GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, Dr);
777        if (debug) { // not checkable
778            GenSolvablePolynomial<C> ps = FDUtil.<C> rightBaseSparsePseudoRemainder(P, D);
779            GenSolvablePolynomial<C> ss = FDUtil.<C> rightBaseSparsePseudoRemainder(S, D);
780            if (!ps.isZERO() || !ss.isZERO()) {
781                System.out.println("fullGcd, D  = " + D);
782                System.out.println("fullGcd, P  = " + P);
783                System.out.println("fullGcd, S  = " + S);
784                System.out.println("fullGcd, ps = " + ps);
785                System.out.println("fullGcd, ss = " + ss);
786                throw new RuntimeException("fullGcd: not divisible");
787            }
788            logger.info("fullGcd(P,S) okay: D = {}, P = {}, S = {}", D, P, S);
789        }
790        return D;
791    }
792
793
794    /**
795     * GenSolvablePolynomial left least common multiple.
796     * @param P GenSolvablePolynomial.
797     * @param S GenSolvablePolynomial.
798     * @return lcm(P,S) with lcm(P,S) = P'*P = S'*S.
799     */
800    @SuppressWarnings("unchecked")
801    public GenSolvablePolynomial<C> leftLcm(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
802        GenSolvablePolynomial<C>[] oc = leftOreCond(P, S);
803        return oc[0].multiply(P);
804    }
805
806
807    /**
808     * Coefficient greatest common divisor. Indirection to coefficient method.
809     * @param a coefficient.
810     * @param b coefficient.
811     * @return gcd(a,b) with a = gcd(a,b)*a' and b = gcd(a,b)*b'.
812     */
813    public C rightGcd(C a, C b) {
814        if (b == null || b.isZERO()) {
815            return a;
816        }
817        if (a == null || a.isZERO()) {
818            return b;
819        }
820        return a.rightGcd(b); // TODO
821    }
822
823
824    /**
825     * GenSolvablePolynomial right greatest common divisor.
826     * @param P GenSolvablePolynomial.
827     * @param S GenSolvablePolynomial.
828     * @return gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where
829     *         deg_main(p) = deg_main(s) == 0.
830     */
831    @SuppressWarnings("unchecked")
832    public GenSolvablePolynomial<C> rightGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
833        if (S == null || S.isZERO()) {
834            return P;
835        }
836        if (P == null || P.isZERO()) {
837            return S;
838        }
839        if (P.isONE()) {
840            return P;
841        }
842        if (S.isONE()) {
843            return S;
844        }
845        GenSolvablePolynomialRing<C> pfac = P.ring;
846        if (pfac.nvar <= 1) {
847            GenSolvablePolynomial<C> T = rightBaseGcd(P, S);
848            return T;
849        }
850        GenSolvablePolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); //RecSolvablePolynomialRing<C>
851        GenSolvablePolynomial<GenPolynomial<C>> Pr, Sr, Dr;
852        Pr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, P);
853        Sr = (RecSolvablePolynomial<C>) PolyUtil.<C> recursive(rfac, S);
854        Dr = rightRecursiveUnivariateGcd(Pr, Sr);
855        GenSolvablePolynomial<C> D = (GenSolvablePolynomial<C>) PolyUtil.<C> distribute(pfac, Dr);
856        if (debug) { // not checkable
857            GenSolvablePolynomial<C> ps = FDUtil.<C> leftBaseSparsePseudoRemainder(P, D);
858            GenSolvablePolynomial<C> ss = FDUtil.<C> leftBaseSparsePseudoRemainder(S, D);
859            if (!ps.isZERO() || !ss.isZERO()) {
860                System.out.println("RI-fullGcd, D  = " + D);
861                System.out.println("RI-fullGcd, P  = " + P);
862                System.out.println("RI-fullGcd, S  = " + S);
863                System.out.println("RI-fullGcd, ps = " + ps);
864                System.out.println("RI-fullGcd, ss = " + ss);
865                throw new RuntimeException("RI-fullGcd: not divisible");
866            }
867            logger.info("RI-fullGcd(P,S) okay: D = {}", D);
868        }
869        return D;
870    }
871
872
873    /**
874     * GenSolvablePolynomial right least common multiple.
875     * @param P GenSolvablePolynomial.
876     * @param S GenSolvablePolynomial.
877     * @return lcm(P,S) with lcm(P,S) = P*P' = S*S'.
878     */
879    @SuppressWarnings("unchecked")
880    public GenSolvablePolynomial<C> rightLcm(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
881        GenSolvablePolynomial<C>[] oc = rightOreCond(P, S);
882        return P.multiply(oc[0]);
883    }
884
885
886    /**
887     * List of GenSolvablePolynomials left greatest common divisor.
888     * @param A non empty list of GenSolvablePolynomials.
889     * @return gcd(A_i) with A_i = A'_i*gcd(A_i)*a_i, where deg_main(a_i) == 0.
890     */
891    @SuppressWarnings("unchecked")
892    public GenSolvablePolynomial<C> leftGcd(List<GenSolvablePolynomial<C>> A) {
893        if (A == null || A.isEmpty()) {
894            throw new IllegalArgumentException("A may not be empty");
895        }
896        GenSolvablePolynomial<C> g = A.get(0);
897        for (int i = 1; i < A.size(); i++) {
898            GenSolvablePolynomial<C> f = A.get(i);
899            g = leftGcd(g, f);
900        }
901        return g;
902    }
903
904
905    /**
906     * GenSolvablePolynomial co-prime list.
907     * @param A list of GenSolvablePolynomials.
908     * @return B with gcd(b,c) = 1 for all b != c in B and for all non-constant
909     *         a in A there exists b in B with b|a. B does not contain zero or
910     *         constant polynomials.
911     */
912    public List<GenSolvablePolynomial<C>> leftCoPrime(List<GenSolvablePolynomial<C>> A) {
913        if (A == null || A.isEmpty()) {
914            return A;
915        }
916        List<GenSolvablePolynomial<C>> B = new ArrayList<GenSolvablePolynomial<C>>(A.size());
917        // make a coprime to rest of list
918        GenSolvablePolynomial<C> a = A.get(0);
919        //System.out.println("a = " + a);
920        if (!a.isZERO() && !a.isConstant()) {
921            for (int i = 1; i < A.size(); i++) {
922                GenSolvablePolynomial<C> b = A.get(i);
923                GenSolvablePolynomial<C> g = leftGcd(a, b);
924                if (!g.isONE()) {
925                    a = FDUtil.<C> leftBasePseudoQuotient(a, g);
926                    b = FDUtil.<C> leftBasePseudoQuotient(b, g);
927                    GenSolvablePolynomial<C> gp = leftGcd(a, g); //.abs();
928                    while (!gp.isONE()) {
929                        a = FDUtil.<C> leftBasePseudoQuotient(a, gp);
930                        g = FDUtil.<C> leftBasePseudoQuotient(g, gp);
931                        B.add(g); // gcd(a,g) == 1
932                        g = gp;
933                        gp = leftGcd(a, gp);
934                    }
935                    if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
936                        B.add(g); // gcd(a,g) == 1
937                    }
938                }
939                if (!b.isZERO() && !b.isConstant()) {
940                    B.add(b); // gcd(a,b) == 1
941                }
942            }
943        } else {
944            B.addAll(A.subList(1, A.size()));
945        }
946        // make rest coprime
947        B = leftCoPrime(B);
948        //System.out.println("B = " + B);
949        if (!a.isZERO() && !a.isConstant() /*&& !B.contains(a)*/) {
950            a = (GenSolvablePolynomial<C>) a.abs();
951            B.add(a);
952        }
953        return B;
954    }
955
956
957    /**
958     * GenSolvablePolynomial left co-prime list.
959     * @param A list of GenSolvablePolynomials.
960     * @return B with gcd(b,c) = 1 for all b != c in B and for all non-constant
961     *         a in A there exists b in B with b|a. B does not contain zero or
962     *         constant polynomials.
963     */
964    public List<GenSolvablePolynomial<C>> leftCoPrimeRec(List<GenSolvablePolynomial<C>> A) {
965        if (A == null || A.isEmpty()) {
966            return A;
967        }
968        List<GenSolvablePolynomial<C>> B = new ArrayList<GenSolvablePolynomial<C>>();
969        // make a co-prime to rest of list
970        for (GenSolvablePolynomial<C> a : A) {
971            //System.out.println("a = " + a);
972            B = leftCoPrime(a, B);
973            //System.out.println("B = " + B);
974        }
975        return B;
976    }
977
978
979    /**
980     * GenSolvablePolynomial left co-prime list.
981     * @param a GenSolvablePolynomial.
982     * @param P co-prime list of GenSolvablePolynomials.
983     * @return B with gcd(b,c) = 1 for all b != c in B and for non-constant a
984     *         there exists b in P with b|a. B does not contain zero or constant
985     *         polynomials.
986     */
987    public List<GenSolvablePolynomial<C>> leftCoPrime(GenSolvablePolynomial<C> a,
988                    List<GenSolvablePolynomial<C>> P) {
989        if (a == null || a.isZERO() || a.isConstant()) {
990            return P;
991        }
992        List<GenSolvablePolynomial<C>> B = new ArrayList<GenSolvablePolynomial<C>>(P.size() + 1);
993        // make a coprime to elements of the list P
994        for (int i = 0; i < P.size(); i++) {
995            GenSolvablePolynomial<C> b = P.get(i);
996            GenSolvablePolynomial<C> g = leftGcd(a, b);
997            if (!g.isONE()) {
998                a = FDUtil.<C> leftBasePseudoQuotient(a, g);
999                b = FDUtil.<C> leftBasePseudoQuotient(b, g);
1000                // make g co-prime to new a, g is co-prime to c != b in P, B
1001                GenSolvablePolynomial<C> gp = leftGcd(a, g);
1002                while (!gp.isONE()) {
1003                    a = FDUtil.<C> leftBasePseudoQuotient(a, gp);
1004                    g = FDUtil.<C> leftBasePseudoQuotient(g, gp);
1005                    if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
1006                        B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B
1007                    }
1008                    g = gp;
1009                    gp = leftGcd(a, gp);
1010                }
1011                // make new g co-prime to new b
1012                gp = leftGcd(b, g);
1013                while (!gp.isONE()) {
1014                    b = FDUtil.<C> leftBasePseudoQuotient(b, gp);
1015                    g = FDUtil.<C> leftBasePseudoQuotient(g, gp);
1016                    if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
1017                        B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B
1018                    }
1019                    g = gp;
1020                    gp = leftGcd(b, gp);
1021                }
1022                if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
1023                    B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B
1024                }
1025            }
1026            if (!b.isZERO() && !b.isConstant() /*&& !B.contains(b)*/) {
1027                B.add(b); // gcd(a,b) == 1 and gcd(b,c) == 1 for c != b in P, B
1028            }
1029        }
1030        if (!a.isZERO() && !a.isConstant() /*&& !B.contains(a)*/) {
1031            B.add(a);
1032        }
1033        return B;
1034    }
1035
1036
1037    /**
1038     * GenSolvablePolynomial test for co-prime list.
1039     * @param A list of GenSolvablePolynomials.
1040     * @return true if gcd(b,c) = 1 for all b != c in A, else false.
1041     */
1042    public boolean isLeftCoPrime(List<GenSolvablePolynomial<C>> A) {
1043        if (A == null || A.isEmpty()) {
1044            return true;
1045        }
1046        if (A.size() == 1) {
1047            return true;
1048        }
1049        for (int i = 0; i < A.size(); i++) {
1050            GenSolvablePolynomial<C> a = A.get(i);
1051            for (int j = i + 1; j < A.size(); j++) {
1052                GenSolvablePolynomial<C> b = A.get(j);
1053                GenSolvablePolynomial<C> g = leftGcd(a, b);
1054                if (!g.isONE()) {
1055                    System.out.println("not co-prime, a: " + a);
1056                    System.out.println("not co-prime, b: " + b);
1057                    System.out.println("not co-prime, g: " + g);
1058                    return false;
1059                }
1060            }
1061        }
1062        return true;
1063    }
1064
1065
1066    /**
1067     * GenSolvablePolynomial test for left co-prime list of given list.
1068     * @param P list of co-prime GenSolvablePolynomials.
1069     * @param A list of GenSolvablePolynomials.
1070     * @return true if isCoPrime(P) and for all a in A exists p in P with p | a,
1071     *         else false.
1072     */
1073    public boolean isLeftCoPrime(List<GenSolvablePolynomial<C>> P, List<GenSolvablePolynomial<C>> A) {
1074        if (!isLeftCoPrime(P)) {
1075            return false;
1076        }
1077        if (A == null || A.isEmpty()) {
1078            return true;
1079        }
1080        for (GenSolvablePolynomial<C> q : A) {
1081            if (q.isZERO() || q.isConstant()) {
1082                continue;
1083            }
1084            boolean divides = false;
1085            for (GenSolvablePolynomial<C> p : P) {
1086                GenSolvablePolynomial<C> a = FDUtil.<C> leftBaseSparsePseudoRemainder(q, p);
1087                if (a.isZERO()) { // p divides q
1088                    divides = true;
1089                    break;
1090                }
1091            }
1092            if (!divides) {
1093                System.out.println("no divisor for: " + q);
1094                return false;
1095            }
1096        }
1097        return true;
1098    }
1099
1100
1101    /**
1102     * Univariate GenSolvablePolynomial extended greatest common divisor. Uses
1103     * sparse pseudoRemainder for remainder.
1104     * @param P univariate GenSolvablePolynomial.
1105     * @param S univariate GenSolvablePolynomial.
1106     * @return [ gcd(P,S), a, b ] with a*P + b*S = gcd(P,S).
1107     */
1108    @SuppressWarnings("unchecked")
1109    public GenSolvablePolynomial<C>[] baseExtendedGcd(GenSolvablePolynomial<C> P,
1110                    GenSolvablePolynomial<C> S) {
1111        //return P.egcd(S);
1112        GenSolvablePolynomial<C>[] hegcd = baseHalfExtendedGcd(P, S);
1113        GenSolvablePolynomial<C>[] ret = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[3];
1114        ret[0] = hegcd[0];
1115        ret[1] = hegcd[1];
1116        if (ret[0].isZERO()) {
1117            ret[1] = P.ring.getZERO();
1118            ret[2] = P.ring.getZERO();
1119            return ret;
1120        }
1121        GenSolvablePolynomial<C> x = (GenSolvablePolynomial<C>) hegcd[0].subtract(hegcd[1].multiply(P));
1122        GenSolvablePolynomial<C>[] qr = FDUtil.<C> leftBasePseudoQuotientRemainder(x, S);
1123        // assert qr[1].isZERO() 
1124        if (!qr[1].isZERO()) {
1125            //GenSolvablePolynomial<C> y = (GenSolvablePolynomial<C>) qr[0].multiply(S).sum(qr[1]);
1126            //System.out.println("qr: " + Arrays.toString(qr));
1127            //System.out.println("x: " + x);
1128            //System.out.println("y: " + y);
1129            throw new RuntimeException("qr[1] != 0: " + Arrays.toString(qr));
1130        }
1131        ret[2] = qr[0];
1132        return ret;
1133    }
1134
1135
1136    /**
1137     * Univariate GenSolvablePolynomial half extended greatest common divisor.
1138     * Uses sparse pseudoRemainder for remainder.
1139     * @param S GenSolvablePolynomial.
1140     * @return [ gcd(P,S), a ] with a*P + b*S = gcd(P,S).
1141     */
1142    @SuppressWarnings("unchecked")
1143    public GenSolvablePolynomial<C>[] baseHalfExtendedGcd(GenSolvablePolynomial<C> P,
1144                    GenSolvablePolynomial<C> S) {
1145        if (P == null || S == null) {
1146            throw new IllegalArgumentException("null P or S not allowed");
1147        }
1148        GenSolvablePolynomial<C>[] ret = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2];
1149        ret[0] = null;
1150        ret[1] = null;
1151        if (S.isZERO()) {
1152            ret[0] = P;
1153            ret[1] = P.ring.getONE();
1154            return ret;
1155        }
1156        if (P.isZERO()) {
1157            ret[0] = S;
1158            ret[1] = S.ring.getZERO();
1159            return ret;
1160        }
1161        if (P.ring.nvar != 1) {
1162            throw new IllegalArgumentException("for univariate polynomials only " + P.ring);
1163        }
1164        GenSolvablePolynomial<C> q = P;
1165        GenSolvablePolynomial<C> r = S;
1166        GenSolvablePolynomial<C> c1 = P.ring.getONE().copy();
1167        GenSolvablePolynomial<C> d1 = P.ring.getZERO().copy();
1168        while (!r.isZERO()) {
1169            GenSolvablePolynomial<C>[] qr = FDUtil.<C> leftBasePseudoQuotientRemainder(q, r);
1170            //q.divideAndRemainder(r);
1171            q = qr[0];
1172            GenSolvablePolynomial<C> x = (GenSolvablePolynomial<C>) c1.subtract(q.multiply(d1));
1173            c1 = d1;
1174            d1 = x;
1175            q = r;
1176            r = qr[1];
1177        }
1178        // normalize ldcf(q) to 1, i.e. make monic
1179        C g = q.leadingBaseCoefficient();
1180        if (g.isUnit()) {
1181            C h = g.inverse();
1182            q = q.multiply(h);
1183            c1 = c1.multiply(h);
1184        }
1185        //assert ( ((c1.multiply(P)).remainder(S).equals(q) )); 
1186        ret[0] = q;
1187        ret[1] = c1;
1188        return ret;
1189    }
1190
1191
1192    /**
1193     * Univariate GenSolvablePolynomial greatest common divisor diophantine
1194     * version.
1195     * @param P univariate GenSolvablePolynomial.
1196     * @param S univariate GenSolvablePolynomial.
1197     * @param c univariate GenSolvablePolynomial.
1198     * @return [ a, b ] with a*P + b*S = c and deg(a) &lt; deg(S).
1199     */
1200    @SuppressWarnings("unchecked")
1201    public GenSolvablePolynomial<C>[] baseGcdDiophant(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S,
1202                    GenSolvablePolynomial<C> c) {
1203        GenSolvablePolynomial<C>[] egcd = baseExtendedGcd(P, S);
1204        GenSolvablePolynomial<C> g = egcd[0];
1205        GenSolvablePolynomial<C>[] qr = FDUtil.<C> leftBasePseudoQuotientRemainder(c, g);
1206        if (!qr[1].isZERO()) {
1207            throw new ArithmeticException("not solvable, r = " + qr[1] + ", c = " + c + ", g = " + g);
1208        }
1209        GenSolvablePolynomial<C> q = qr[0];
1210        GenSolvablePolynomial<C> a = egcd[1].multiply(q);
1211        GenSolvablePolynomial<C> b = egcd[2].multiply(q);
1212        if (!a.isZERO() && a.degree(0) >= S.degree(0)) {
1213            qr = FDUtil.<C> leftBasePseudoQuotientRemainder(a, S);
1214            a = qr[1];
1215            b = (GenSolvablePolynomial<C>) b.sum(P.multiply(qr[0]));
1216        }
1217        GenSolvablePolynomial<C>[] ret = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2];
1218        ret[0] = a;
1219        ret[1] = b;
1220        if (debug) {
1221            GenSolvablePolynomial<C> y = (GenSolvablePolynomial<C>) ret[0].multiply(P)
1222                            .sum(ret[1].multiply(S));
1223            if (!y.equals(c)) {
1224                System.out.println("P  = " + P);
1225                System.out.println("S  = " + S);
1226                System.out.println("c  = " + c);
1227                System.out.println("a  = " + a);
1228                System.out.println("b  = " + b);
1229                System.out.println("y  = " + y);
1230                throw new ArithmeticException("not diophant, x = " + y.subtract(c));
1231            }
1232        }
1233        return ret;
1234    }
1235
1236
1237    /**
1238     * Coefficient left Ore condition. Generators for the left Ore condition of
1239     * two coefficients.
1240     * @param a coefficient.
1241     * @param b coefficient.
1242     * @return [oa, ob] = leftOreCond(a,b), with oa*a == ob*b.
1243     */
1244    @SuppressWarnings("unchecked")
1245    public C[] leftOreCond(C a, C b) {
1246        if (a == null || a.isZERO() || b == null || b.isZERO()) {
1247            throw new IllegalArgumentException("a and b must be non zero");
1248        }
1249        C[] oc = (C[]) new GcdRingElem[2];
1250        if (a instanceof GenSolvablePolynomial && b instanceof GenSolvablePolynomial) {
1251            GenSolvablePolynomial ap = (GenSolvablePolynomial) a;
1252            GenSolvablePolynomial bp = (GenSolvablePolynomial) b;
1253            GenSolvablePolynomial[] ocp = leftOreCond(ap, bp);
1254            oc[0] = (C) ocp[0];
1255            oc[1] = (C) ocp[1];
1256            return oc;
1257        }
1258        RingFactory<C> rf = coFac; // not usable: (RingFactory<C>) a.factory();
1259        if (a.equals(b)) { // required because of rationals gcd
1260            oc[0] = rf.getONE();
1261            oc[1] = rf.getONE();
1262            logger.info("Ore multiple ==: {}", Arrays.toString(oc));
1263            return oc;
1264        }
1265        if (a.equals(b.negate())) { // required because of rationals gcd
1266            oc[0] = rf.getONE();
1267            oc[1] = rf.getONE().negate();
1268            logger.info("Ore multiple ==-: {}", Arrays.toString(oc));
1269            return oc;
1270        }
1271        if (rf.isCommutative()) {
1272            if (debug) {
1273                logger.info("left Ore condition on coefficients, commutative case: {}, {}", a, b);
1274            }
1275            C gcd = a.gcd(b);
1276            if (gcd.isONE()) {
1277                oc[0] = b;
1278                oc[1] = a;
1279                if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) {
1280                    oc[0] = oc[0].negate();
1281                    oc[1] = oc[1].negate();
1282                }
1283                logger.info("Ore multiple: {}", Arrays.toString(oc));
1284                return oc;
1285            }
1286            C p = a.multiply(b);
1287            C lcm = p.divide(gcd).abs();
1288            oc[0] = lcm.divide(a);
1289            oc[1] = lcm.divide(b);
1290            if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) {
1291                oc[0] = oc[0].negate();
1292                oc[1] = oc[1].negate();
1293            }
1294            logger.info("Ore multiple: lcm={}, gcd={}, {}", lcm, gcd, Arrays.toString(oc));
1295            return oc;
1296        }
1297        // now non-commutative
1298        if (rf.isField()) {
1299            logger.info("left Ore condition on coefficients, skew field {} case: {}, {}", rf, a, b);
1300            //C gcd = a.gcd(b); // always one 
1301            //C lcm = rf.getONE();
1302            oc[0] = a.inverse(); //lcm.divide(a);
1303            oc[1] = b.inverse(); //lcm.divide(b);
1304            logger.info("Ore multiple: {}", Arrays.toString(oc));
1305            return oc;
1306        }
1307        if (b instanceof StarRingElem) {
1308            logger.info("left Ore condition on coefficients, StarRing case: {}, {}", a, b);
1309            C bs = (C) ((StarRingElem) b).conjugate();
1310            oc[0] = bs.multiply(b); // bar(b) b a = s a 
1311            oc[1] = a.multiply(bs); // a bar(b) b = t b
1312            logger.info("Ore multiple: {}", Arrays.toString(oc));
1313            return oc;
1314        }
1315        throw new UnsupportedOperationException(
1316                        "leftOreCond not implemented for " + rf.getClass() + ", rf = " + rf.toScript());
1317        //return oc;
1318    }
1319
1320
1321    /**
1322     * Left Ore condition. Generators for the left Ore condition of two solvable
1323     * polynomials.
1324     * @param a solvable polynomial
1325     * @param b solvable polynomial
1326     * @return [p,q] with p*a = q*b
1327     */
1328    @SuppressWarnings("unchecked")
1329    public GenSolvablePolynomial<C>[] leftOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<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        GenSolvablePolynomialRing<C> pfac = a.ring;
1334        GenSolvablePolynomial<C>[] oc = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2];
1335        if (a.equals(b)) {
1336            oc[0] = pfac.getONE();
1337            oc[1] = pfac.getONE();
1338            return oc;
1339        }
1340        if (a.equals(b.negate())) {
1341            oc[0] = pfac.getONE();
1342            oc[1] = (GenSolvablePolynomial<C>) pfac.getONE().negate();
1343            return oc;
1344        }
1345        if (pfac.isCommutative()) {
1346            logger.info("left Ore condition, polynomial commutative case: {}, {}", a, b);
1347            edu.jas.ufd.GreatestCommonDivisorAbstract<C> cgcd = GCDFactory.<C> getImplementation(pfac.coFac);
1348            GenSolvablePolynomial<C> lcm = (GenSolvablePolynomial<C>) cgcd.lcm(a, b);
1349            //oc[0] = FDUtil.<C> basePseudoQuotient(lcm, a);
1350            //oc[1] = FDUtil.<C> basePseudoQuotient(lcm, b);
1351            oc[0] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, a);
1352            oc[1] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, b);
1353            logger.info("Ore multiple: {}, {}", lcm, Arrays.toString(oc));
1354            return oc;
1355        }
1356        oc = syz.leftOreCond(a, b);
1357        //logger.info("Ore multiple: {}, {}", oc[0].multiply(a), Arrays.toString(oc));
1358        return oc;
1359    }
1360
1361
1362    /**
1363     * Coefficient right Ore condition. Generators for the right Ore condition
1364     * of two coefficients.
1365     * @param a coefficient.
1366     * @param b coefficient.
1367     * @return [oa, ob] = rightOreCond(a,b), with a*oa == b*ob.
1368     */
1369    @SuppressWarnings("unchecked")
1370    public C[] rightOreCond(C a, C b) {
1371        if (a == null || a.isZERO() || b == null || b.isZERO()) {
1372            throw new IllegalArgumentException("a and b must be non zero");
1373        }
1374        C[] oc = (C[]) new GcdRingElem[2];
1375        if (a instanceof GenSolvablePolynomial && b instanceof GenSolvablePolynomial) {
1376            GenSolvablePolynomial ap = (GenSolvablePolynomial) a;
1377            GenSolvablePolynomial bp = (GenSolvablePolynomial) b;
1378            GenSolvablePolynomial[] ocp = rightOreCond(ap, bp);
1379            oc[0] = (C) ocp[0];
1380            oc[1] = (C) ocp[1];
1381            return oc;
1382        }
1383        RingFactory<C> rf = coFac; // not usable: (RingFactory<C>) a.factory();
1384        if (a.equals(b)) { // required because of rationals gcd
1385            oc[0] = rf.getONE();
1386            oc[1] = rf.getONE();
1387            return oc;
1388        }
1389        if (a.equals(b.negate())) { // required because of rationals gcd
1390            oc[0] = rf.getONE();
1391            oc[1] = rf.getONE().negate();
1392            return oc;
1393        }
1394        if (rf.isCommutative()) {
1395            logger.info("right Ore condition on coefficients, commutative case: {}, {}", a, b);
1396            C gcd = a.gcd(b);
1397            if (gcd.isONE()) {
1398                oc[0] = b;
1399                oc[1] = a;
1400                if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) {
1401                    oc[0] = oc[0].negate();
1402                    oc[1] = oc[1].negate();
1403                }
1404                return oc;
1405            }
1406            C p = a.multiply(b);
1407            C lcm = p.divide(gcd).abs();
1408            oc[0] = lcm.divide(a);
1409            oc[1] = lcm.divide(b);
1410            if (oc[0].compareTo(rf.getZERO()) < 0 && oc[1].compareTo(rf.getZERO()) < 0) {
1411                oc[0] = oc[0].negate();
1412                oc[1] = oc[1].negate();
1413            }
1414            logger.info("Ore multiple: {}, {}", lcm, Arrays.toString(oc));
1415            return oc;
1416        }
1417        // now non-commutative
1418        if (rf.isField()) {
1419            logger.info("right Ore condition on coefficients, skew field {} case: {}, {}", rf, a, b);
1420            //C gcd = a.gcd(b); // always one 
1421            //C lcm = rf.getONE();
1422            oc[0] = a.inverse(); //lcm.divide(a);
1423            oc[1] = b.inverse(); //lcm.divide(b);
1424            logger.info("Ore multiple: {}", Arrays.toString(oc));
1425            return oc;
1426        }
1427        if (b instanceof StarRingElem) {
1428            logger.info("right Ore condition on coefficients, StarRing case: {}, {}", a, b);
1429            C bs = (C) ((StarRingElem) b).conjugate();
1430            oc[0] = b.multiply(bs); // a b bar(b) = a s
1431            oc[1] = bs.multiply(a); // b bar(b) a = b t
1432            logger.info("Ore multiple: {}", Arrays.toString(oc));
1433            return oc;
1434        }
1435        throw new UnsupportedOperationException(
1436                        "rightOreCond not implemented for " + rf.getClass() + ", rf = {}" + rf.toScript());
1437        //return oc;
1438    }
1439
1440
1441    /**
1442     * Right Ore condition. Generators for the right Ore condition of two
1443     * solvable polynomials.
1444     * @param a solvable polynomial
1445     * @param b solvable polynomial
1446     * @return [p,q] with a*p = b*q
1447     */
1448    @SuppressWarnings("unchecked")
1449    public GenSolvablePolynomial<C>[] rightOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b) {
1450        if (a == null || a.isZERO() || b == null || b.isZERO()) {
1451            throw new IllegalArgumentException("a and b must be non zero");
1452        }
1453        GenSolvablePolynomialRing<C> pfac = a.ring;
1454        GenSolvablePolynomial<C>[] oc = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[2];
1455        if (a.equals(b)) {
1456            oc[0] = pfac.getONE();
1457            oc[1] = pfac.getONE();
1458            return oc;
1459        }
1460        if (a.equals(b.negate())) {
1461            oc[0] = pfac.getONE();
1462            oc[1] = (GenSolvablePolynomial<C>) pfac.getONE().negate();
1463            return oc;
1464        }
1465        if (pfac.isCommutative()) {
1466            logger.info("right Ore condition, polynomial commutative case: {}, {}", a, b);
1467            edu.jas.ufd.GreatestCommonDivisorAbstract<C> cgcd = GCDFactory.<C> getImplementation(pfac.coFac);
1468            GenSolvablePolynomial<C> lcm = (GenSolvablePolynomial<C>) cgcd.lcm(a, b);
1469            //oc[0] = FDUtil.<C> basePseudoQuotient(lcm, a);
1470            //oc[1] = FDUtil.<C> basePseudoQuotient(lcm, b);
1471            oc[0] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, a);
1472            oc[1] = (GenSolvablePolynomial<C>) PolyUtil.<C> basePseudoDivide(lcm, b);
1473            logger.info("Ore multiple: {}, {}", lcm, Arrays.toString(oc));
1474            return oc;
1475        }
1476        oc = syz.rightOreCond(a, b);
1477        //logger.info("Ore multiple: {}, {}", oc[0].multiply(a), Arrays.toString(oc));
1478        return oc;
1479    }
1480
1481
1482    /**
1483     * Is left Ore condition. Test left Ore condition of two solvable
1484     * polynomials.
1485     * @param a solvable polynomial
1486     * @param b solvable polynomial
1487     * @param p solvable polynomial
1488     * @param q solvable polynomial
1489     * @return true, if p*a = q*b, else false
1490     */
1491    public boolean isLeftOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b,
1492                    GenSolvablePolynomial<C> p, GenSolvablePolynomial<C> q) {
1493        return syz.isLeftOreCond(a, b, p, q);
1494    }
1495
1496
1497    /**
1498     * Is right Ore condition. Test right Ore condition of two solvable
1499     * polynomials.
1500     * @param a solvable polynomial
1501     * @param b solvable polynomial
1502     * @param p solvable polynomial
1503     * @param q solvable polynomial
1504     * @return true, if a*p = b*q, else false
1505     */
1506    public boolean isRightOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b,
1507                    GenSolvablePolynomial<C> p, GenSolvablePolynomial<C> q) {
1508        return syz.isRightOreCond(a, b, p, q);
1509    }
1510
1511
1512    /**
1513     * Left greatest common divisor and cofactors.
1514     * @param r solvable polynomial ring.
1515     * @param n first solvable polynomial.
1516     * @param d second solvable polynomial.
1517     * @return [ g=leftGcd(n,d), n/g, d/g ]
1518     */
1519    @SuppressWarnings("unchecked")
1520    public GenSolvablePolynomial<C>[] leftGcdCofactors(GenSolvablePolynomialRing<C> r,
1521                    GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) {
1522        logger.info("leftGCD_in: {}, {}", n, d);
1523        GenSolvablePolynomial<C>[] res = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[3];
1524        res[0] = leftGcd(n, d);
1525        //res[0] = PolyModUtil.<C> syzLeftGcd(r, n, d);
1526        res[1] = n;
1527        res[2] = d;
1528        if (res[0].isONE()) {
1529            return res;
1530        }
1531        logger.info("leftGCD_out: {}", res[0]);
1532        GenSolvablePolynomial<C>[] nqr;
1533        nqr = FDUtil.<C> rightBasePseudoQuotientRemainder(n, res[0]);
1534        if (!nqr[1].isZERO()) {
1535            res[0] = r.getONE();
1536            return res;
1537        }
1538        GenSolvablePolynomial<C>[] dqr;
1539        dqr = FDUtil.<C> rightBasePseudoQuotientRemainder(d, res[0]);
1540        if (!dqr[1].isZERO()) {
1541            res[0] = r.getONE();
1542            return res;
1543        }
1544        res[1] = nqr[0];
1545        res[2] = dqr[0];
1546        return res;
1547    }
1548
1549
1550    /**
1551     * Right greatest common divisor and cofactors.
1552     * @param r solvable polynomial ring.
1553     * @param n first solvable polynomial.
1554     * @param d second solvable polynomial.
1555     * @return [ g=rightGcd(n,d), n/g, d/g ]
1556     */
1557    @SuppressWarnings("unchecked")
1558    public GenSolvablePolynomial<C>[] rightGcdCofactors(GenSolvablePolynomialRing<C> r,
1559                    GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) {
1560        logger.info("rightGCD_in: {}, {}", n, d);
1561        GenSolvablePolynomial<C>[] res = (GenSolvablePolynomial<C>[]) new GenSolvablePolynomial[3];
1562        res[0] = rightGcd(n, d);
1563        //res[0] = PolyModUtil.<C> syzRightGcd(r, n, d);
1564        res[1] = n;
1565        res[2] = d;
1566        if (res[0].isONE()) {
1567            return res;
1568        }
1569        logger.info("rightGCD_out: {}", res[0]);
1570        GenSolvablePolynomial<C>[] nqr;
1571        nqr = FDUtil.<C> leftBasePseudoQuotientRemainder(n, res[0]);
1572        if (!nqr[1].isZERO()) {
1573            res[0] = r.getONE();
1574            return res;
1575        }
1576        GenSolvablePolynomial<C>[] dqr;
1577        dqr = FDUtil.<C> leftBasePseudoQuotientRemainder(d, res[0]);
1578        if (!dqr[1].isZERO()) {
1579            res[0] = r.getONE();
1580            return res;
1581        }
1582        res[1] = nqr[0];
1583        res[2] = dqr[0];
1584        return res;
1585    }
1586
1587}