Source code

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