Source code

001/*
002 * $Id: GreatestCommonDivisorLR.java 5872 2018-07-20 16:01:46Z kredel $
003 */
004
005package edu.jas.fd;
006
007
008import org.apache.logging.log4j.Logger;
009import org.apache.logging.log4j.LogManager; 
010
011import edu.jas.gbufd.SolvableSyzygyAbstract;
012import edu.jas.poly.GenPolynomial;
013import edu.jas.poly.GenSolvablePolynomial;
014import edu.jas.poly.GenSolvablePolynomialRing;
015import edu.jas.structure.GcdRingElem;
016import edu.jas.structure.RingFactory;
017
018
019/**
020 * (Non-unique) factorization domain greatest common divisor common algorithms
021 * with monic polynomial remainder sequence. Fake implementation always returns
022 * 1 for any gcds.
023 * @param <C> coefficient type
024 * @author Heinz Kredel
025 */
026
027public class GreatestCommonDivisorLR<C extends GcdRingElem<C>> extends GreatestCommonDivisorAbstract<C> {
028
029
030    private static final Logger logger = LogManager.getLogger(GreatestCommonDivisorLR.class);
031
032
033    private static final boolean debug = logger.isDebugEnabled();
034
035
036    /**
037     * Constructor.
038     * @param cf coefficient ring.
039     */
040    public GreatestCommonDivisorLR(RingFactory<C> cf) {
041        super(cf);
042    }
043
044
045    /**
046     * Constructor.
047     * @param cf coefficient ring.
048     * @param s algorithm for SolvableSyzygy computation.
049     */
050    public GreatestCommonDivisorLR(RingFactory<C> cf, SolvableSyzygyAbstract<C> s) {
051        super(cf, s);
052    }
053
054
055    /**
056     * Univariate GenSolvablePolynomial greatest common divisor. Uses
057     * pseudoRemainder for remainder.
058     * @param P univariate GenSolvablePolynomial.
059     * @param S univariate GenSolvablePolynomial.
060     * @return [P,S,coP,coS,left,right] with left * coP * right = P and left *
061     *         coS * right = S.
062     */
063    public GCDcoFactors<C> leftRightBaseGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
064        if (S == null || P == null) {
065            throw new IllegalArgumentException("null polynomials not allowed");
066        }
067        GenSolvablePolynomialRing<C> ring = P.ring;
068        if (ring.nvar > 1) {
069            throw new IllegalArgumentException("no univariate polynomial");
070        }
071        GCDcoFactors<C> ret;
072        if (P.isZERO() || S.isZERO()) {
073            ret = new GCDcoFactors<C>(this, P, S, P, S, ring.getONE(), ring.getONE());
074            return ret;
075        }
076        // compute on coefficients
077        C contP = leftBaseContent(P);
078        C contS = leftBaseContent(S);
079        C contPS = contP.leftGcd(contS);
080        if (contPS.signum() < 0) {
081            contPS = contPS.negate();
082        }
083        if (debug) {
084            //System.out.println("contP = " + contP + ", contS = " + contS + ", leftGcd(contP,contS) = " + contPS);
085            C r1 = contP.leftDivide(contPS);
086            boolean t = contPS.multiply(r1).equals(contP);
087            if (!t) {
088                System.out.println("r1: " + r1 + " * " + contPS + " != " + contP + ", r1*cP="
089                                + contPS.multiply(r1));
090            }
091            C r2 = contS.leftDivide(contPS);
092            t = contPS.multiply(r2).equals(contS);
093            if (!t) {
094                System.out.println("r2: " + r2 + " * " + contPS + " != " + contS + ", r2*cS="
095                                + contPS.multiply(r2));
096            }
097            //System.out.println("leftGcd(contP,contS) = " + contPS);
098        }
099        GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) P.leftDivideCoeff(contP);
100        GenSolvablePolynomial<C> s = (GenSolvablePolynomial<C>) S.leftDivideCoeff(contS);
101        if (debug) {
102            boolean t = p.multiplyLeft(contP).equals(P);
103            if (!t) {
104                System.out.println(
105                                "p: " + p + " * " + contP + " != " + P + ", p*cP=" + p.multiplyLeft(contP));
106            }
107            t = s.multiplyLeft(contS).equals(S);
108            if (!t) {
109                System.out.println(
110                                "s: " + s + " * " + contS + " != " + S + ", s*cS=" + s.multiplyLeft(contS));
111            }
112        }
113        // compute on main variable
114        if (p.isONE()) {
115            ret = new GCDcoFactors<C>(this, P, S, p, s, ring.valueOf(contPS), ring.getONE());
116            return ret;
117        }
118        if (s.isONE()) {
119            ret = new GCDcoFactors<C>(this, P, S, p, s, ring.valueOf(contPS), ring.getONE());
120            return ret;
121        }
122        boolean field = ring.coFac.isField();
123        GenSolvablePolynomial<C> r = p;
124        GenSolvablePolynomial<C> q = s;
125        GenSolvablePolynomial<C> x;
126        //System.out.println("baseGCD: q = " + q + ", r = " + r);
127        while (!r.isZERO()) {
128            x = FDUtil.<C> leftBaseSparsePseudoRemainder(q, r);
129            q = r;
130            if (field) {
131                r = x.monic();
132                //System.out.println("baseGCD: lc(q) = " + q.leadingBaseCoefficient() + ", lc(r) = " + r.leadingBaseCoefficient());
133            } else {
134                r = x;
135            }
136            //System.out.println("baseGCD: q = " + q + ", r = " + r);
137        }
138        q = leftBasePrimitivePart(q);
139        q = (GenSolvablePolynomial<C>) q.abs();
140        // not meaningful:
141        // adjust signum of contPS
142        //C qc = leftBaseContent(q);
143        //q = (GenSolvablePolynomial<C>) q.leftDivideCoeff(qc); 
144        //contPS = qc.multiply(contPS);
145        //System.out.println("leftGcd()*qc = " + contPS);
146        //q = rightBasePrimitivePart(q);
147        //System.out.println("baseGCD: q = " + q + ", r = " + r);
148        p = (GenSolvablePolynomial<C>) P.leftDivideCoeff(contPS); // not contP here
149        s = (GenSolvablePolynomial<C>) S.leftDivideCoeff(contPS); // not contS here
150        GenSolvablePolynomial<C> p1 = FDUtil.<C> leftBasePseudoQuotient(p, q); // TODO
151        GenSolvablePolynomial<C> s1 = FDUtil.<C> leftBasePseudoQuotient(s, q); // TODO 
152        //System.out.println("p1 = " + p1 + ", s1 = " + s1);
153        if (debug) {
154            boolean t = p1.multiply(q).equals(p);
155            if (!t) {
156                GenSolvablePolynomial<C> p1q = (GenSolvablePolynomial<C>) leftBasePrimitivePart(
157                                p1.multiply(q)).abs();
158                GenSolvablePolynomial<C> pp = (GenSolvablePolynomial<C>) leftBasePrimitivePart(p).abs();
159                if (!p1q.equals(pp)) {
160                    System.out.println("p1: " + p1 + " * " + q + " != " + p);
161                    System.out.println("pp(p1*q): " + p1q + " != " + pp);
162                }
163                p1q = p1.multiply(q);
164                pp = p;
165                C c1 = p1q.leadingBaseCoefficient();
166                C c2 = pp.leadingBaseCoefficient();
167                C[] oc = leftOreCond(c1, c2);
168                p1q = p1q.multiplyLeft(oc[0]);
169                pp = pp.multiplyLeft(oc[1]);
170                if (!p1q.equals(pp)) {
171                    System.out.println("p1q: " + p1q + " != " + pp);
172                }
173            }
174            t = s1.multiply(q).equals(s);
175            if (!t) {
176                GenSolvablePolynomial<C> s1q = (GenSolvablePolynomial<C>) leftBasePrimitivePart(
177                                s1.multiply(q)).abs();
178                GenSolvablePolynomial<C> sp = (GenSolvablePolynomial<C>) leftBasePrimitivePart(s).abs();
179                if (!s1q.equals(sp)) {
180                    System.out.println("s1: " + s1 + " * " + q + " != " + s);
181                    System.out.println("pp(s1*q): " + s1q + " != " + sp);
182                }
183                s1q = s1.multiply(q);
184                sp = s;
185                C c1 = s1q.leadingBaseCoefficient();
186                C c2 = sp.leadingBaseCoefficient();
187                C[] oc = leftOreCond(c1, c2);
188                s1q = s1q.multiplyLeft(oc[0]);
189                sp = sp.multiplyLeft(oc[1]);
190                if (!s1q.equals(sp)) {
191                    System.out.println("s1q: " + s1q + " != " + sp);
192                }
193            }
194            t = p.multiplyLeft(contPS).equals(P); // contPS q p1 == P
195            if (!t) {
196                System.out.println("p1P: " + contPS + " * " + p + " != " + P);
197            }
198            t = s.multiplyLeft(contPS).equals(S);
199            if (!t) {
200                System.out.println("s1S: " + contPS + " * " + s + " != " + S);
201            }
202            //System.out.println("isField: " + field);
203        }
204        ret = new GCDcoFactors<C>(this, P, S, p1, s1, ring.valueOf(contPS), q);
205        return ret;
206    }
207
208
209    /**
210     * Univariate GenSolvablePolynomial greatest common divisor. Uses
211     * pseudoRemainder for remainder.
212     * @param P univariate GenSolvablePolynomial.
213     * @param S univariate GenSolvablePolynomial.
214     * @return [P,S,coP,coS,left,right] with left * coP * right = P and left *
215     *         coS * right = S.
216     */
217    public GCDcoFactors<C> rightLeftBaseGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
218        if (S == null || P == null) {
219            throw new IllegalArgumentException("null polynomials not allowed");
220        }
221        GenSolvablePolynomialRing<C> ring = P.ring;
222        if (ring.nvar > 1) {
223            throw new IllegalArgumentException("no univariate polynomial");
224        }
225        GCDcoFactors<C> ret;
226        if (P.isZERO() || S.isZERO()) {
227            ret = new GCDcoFactors<C>(this, P, S, P, S, ring.getONE(), ring.getONE());
228            return ret;
229        }
230        // compute on coefficients
231        C contP = rightBaseContent(P);
232        C contS = rightBaseContent(S);
233        C contPS = contP.rightGcd(contS);
234        if (contPS.signum() < 0) {
235            contPS = contPS.negate();
236        }
237        if (debug) {
238            //System.out.println("contP = " + contP + ", contS = " + contS + ", rightGcd(contP,contS) = " + contPS);
239            C r1 = contP.rightDivide(contPS);
240            boolean t = r1.multiply(contPS).equals(contP);
241            if (!t) {
242                System.out.println("r1: " + r1 + " * " + contPS + " != " + contP + ", r1*cP="
243                                + r1.multiply(contPS));
244            }
245            C r2 = contS.rightDivide(contPS);
246            t = r2.multiply(contPS).equals(contS);
247            if (!t) {
248                System.out.println("r2: " + r2 + " * " + contPS + " != " + contS + ", r2*cS="
249                                + r2.multiply(contPS));
250            }
251            //System.out.println("rightGcd(contP,contS) = " + contPS);
252        }
253        GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) P.rightDivideCoeff(contP);
254        GenSolvablePolynomial<C> s = (GenSolvablePolynomial<C>) S.rightDivideCoeff(contS);
255        if (debug) {
256            boolean t = p.multiply(contP).equals(P);
257            if (!t) {
258                System.out.println("p: " + p + " * " + contP + " != " + P + ", p*cP=" + p.multiply(contP));
259            }
260            t = s.multiply(contS).equals(S);
261            if (!t) {
262                System.out.println("s: " + s + " * " + contS + " != " + S + ", s*cS=" + s.multiply(contS));
263            }
264        }
265        // compute on main variable
266        if (p.isONE()) {
267            ret = new GCDcoFactors<C>(this, P, S, p, s, ring.getONE(), ring.valueOf(contPS));
268            return ret;
269        }
270        if (s.isONE()) {
271            ret = new GCDcoFactors<C>(this, P, S, p, s, ring.getONE(), ring.valueOf(contPS));
272            return ret;
273        }
274        boolean field = ring.coFac.isField();
275        GenSolvablePolynomial<C> r = p;
276        GenSolvablePolynomial<C> q = s;
277        GenSolvablePolynomial<C> x;
278        //System.out.println("baseGCD: q = " + q + ", r = " + r);
279        while (!r.isZERO()) {
280            x = FDUtil.<C> rightBaseSparsePseudoRemainder(q, r);
281            q = r;
282            if (field) {
283                r = x.monic();
284                //System.out.println("baseGCD: lc(q) = " + q.leadingBaseCoefficient() + ", lc(r) = " + r.leadingBaseCoefficient());
285            } else {
286                r = x;
287            }
288            //System.out.println("baseGCD: r = " + r);
289        }
290        q = rightBasePrimitivePart(q);
291        q = (GenSolvablePolynomial<C>) q.abs();
292        //q = rightBasePrimitivePart(q);
293        //System.out.println("baseGCD: q = " + q + ", r = " + r);
294        p = (GenSolvablePolynomial<C>) P.rightDivideCoeff(contPS); // not contP here
295        s = (GenSolvablePolynomial<C>) S.rightDivideCoeff(contPS); // not contS here
296        GenSolvablePolynomial<C> p1 = FDUtil.<C> rightBasePseudoQuotient(p, q); // TODO
297        GenSolvablePolynomial<C> s1 = FDUtil.<C> rightBasePseudoQuotient(s, q); // TODO 
298        //System.out.println("p1 = " + p1 + ", s1 = " + s1);
299        if (debug) {
300            boolean t = q.multiply(p1).equals(p);
301            if (!t) {
302                GenSolvablePolynomial<C> p1q = p1.multiply(q);
303                GenSolvablePolynomial<C> pp = p;
304                C c1 = p1q.leadingBaseCoefficient();
305                C c2 = pp.leadingBaseCoefficient();
306                C[] oc = rightOreCond(c1, c2);
307                p1q = p1q.multiply(oc[0]);
308                pp = pp.multiply(oc[1]);
309                if (!p1q.equals(pp)) {
310                    System.out.println("p1q: " + p1q + " != " + pp);
311                }
312            }
313            t = q.multiply(s1).equals(s);
314            if (!t) {
315                GenSolvablePolynomial<C> s1q = q.multiply(s1);
316                GenSolvablePolynomial<C> sp = s;
317                C c1 = s1q.leadingBaseCoefficient();
318                C c2 = sp.leadingBaseCoefficient();
319                C[] oc = rightOreCond(c1, c2);
320                s1q = s1q.multiply(oc[0]);
321                sp = sp.multiply(oc[1]);
322                if (!s1q.equals(sp)) {
323                    System.out.println("s1q: " + s1q + " != " + sp);
324                }
325            }
326            t = p.multiply(contPS).equals(P); // contPS q p1 == P
327            if (!t) {
328                System.out.println("p1P: " + contPS + " * " + p + " != " + P);
329            }
330            t = s.multiply(contPS).equals(S);
331            if (!t) {
332                System.out.println("s1S: " + contPS + " * " + s + " != " + S);
333            }
334            //System.out.println("isField: " + field);
335        }
336        ret = new GCDcoFactors<C>(this, P, S, p1, s1, q, ring.valueOf(contPS));
337        return ret;
338    }
339
340
341    /**
342     * Univariate GenSolvablePolynomial greatest common divisor. Uses
343     * pseudoRemainder for remainder.
344     * @param P univariate GenSolvablePolynomial.
345     * @param S univariate GenSolvablePolynomial.
346     * @return l = gcd(P,S) with P = gcd(P,S)*P' and S = gcd(P,S)*S'.
347     */
348    @Override
349    public GenSolvablePolynomial<C> leftBaseGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
350        if (S == null || S.isZERO()) {
351            return P;
352        }
353        if (P == null || P.isZERO()) {
354            return S;
355        }
356        GenSolvablePolynomialRing<C> ring = P.ring;
357        if (ring.nvar > 1) {
358            throw new IllegalArgumentException(this.getClass().getName() + " no univariate polynomial");
359        }
360        // compute on coefficients
361        C contP = leftBaseContent(P);
362        C contS = leftBaseContent(S);
363        C contPS = contP.leftGcd(contS);
364        if (contPS.signum() < 0) {
365            contPS = contPS.negate();
366        }
367        if (debug) {
368            //System.out.println("contP = " + contP + ", contS = " + contS + ", leftGcd(contP,contS) = " + contPS);
369            C r1 = contP.leftDivide(contPS);
370            boolean t = contPS.multiply(r1).equals(contP);
371            if (!t) {
372                System.out.println("r1: " + r1 + " * " + contPS + " != " + contP + ", r1*cP="
373                                + contPS.multiply(r1));
374            }
375            C r2 = contS.leftDivide(contPS);
376            t = contPS.multiply(r2).equals(contS);
377            if (!t) {
378                System.out.println("r2: " + r2 + " * " + contPS + " != " + contS + ", r2*cS="
379                                + contPS.multiply(r2));
380            }
381            //System.out.println("contPS = " + contPS);
382        }
383        GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) P.leftDivideCoeff(contP);
384        GenSolvablePolynomial<C> s = (GenSolvablePolynomial<C>) S.leftDivideCoeff(contS);
385        if (debug) {
386            boolean t = p.multiplyLeft(contP).equals(P);
387            if (!t) {
388                System.out.println(
389                                "p: " + p + " * " + contP + " != " + P + ", p*cP=" + p.multiplyLeft(contP));
390            }
391            t = s.multiplyLeft(contS).equals(S);
392            if (!t) {
393                System.out.println(
394                                "s: " + s + " * " + contS + " != " + S + ", s*cS=" + s.multiplyLeft(contS));
395            }
396        }
397        // compute on main variable
398        if (p.isONE()) {
399            return ring.valueOf(contPS);
400        }
401        if (s.isONE()) {
402            return ring.valueOf(contPS);
403        }
404        boolean field = ring.coFac.isField();
405        GenSolvablePolynomial<C> r = p;
406        GenSolvablePolynomial<C> q = s;
407        GenSolvablePolynomial<C> x;
408        if (r.degree(0) > q.degree(0)) {
409            x = r;
410            r = q;
411            q = x;
412        }
413        //System.out.println("baseGCD: q = " + q + ", r = " + r);
414        while (!r.isZERO()) {
415            x = FDUtil.<C> rightBaseSparsePseudoRemainder(q, r);
416            q = r;
417            if (field) {
418                r = x.monic();
419            } else {
420                r = x;
421            }
422            //System.out.println("baseGCD: r = " + r);
423        }
424        q = leftBasePrimitivePart(q);
425        //q = rightBasePrimitivePart(q);
426        //q = (GenSolvablePolynomial<C>) q.abs();
427        //System.out.println("baseGCD: q = " + q + ", r = " + r);
428        GenSolvablePolynomial<C> p1 = FDUtil.<C> rightBasePseudoQuotient(p, q); // TODO
429        GenSolvablePolynomial<C> s1 = FDUtil.<C> rightBasePseudoQuotient(s, q); // TODO 
430        //System.out.println("p1 = " + p1 + ", s1 = " + s1);
431        if (debug) {
432            boolean t = q.multiply(p1).equals(p);
433            if (!t) {
434                GenSolvablePolynomial<C> p1q = q.multiply(p1);
435                GenSolvablePolynomial<C> pp = p;
436                C c1 = p1q.leadingBaseCoefficient();
437                C c2 = pp.leadingBaseCoefficient();
438                C[] oc = leftOreCond(c1, c2);
439                p1q = p1q.multiplyLeft(oc[0]);
440                pp = pp.multiplyLeft(oc[1]);
441                if (!p1q.equals(pp)) {
442                    System.out.println("Ore cond, p1q: " + p1q + " != " + pp);
443                }
444            }
445            t = q.multiply(s1).equals(s);
446            if (!t) {
447                GenSolvablePolynomial<C> s1q = q.multiply(s1);
448                GenSolvablePolynomial<C> sp = s;
449                C c1 = s1q.leadingBaseCoefficient();
450                C c2 = sp.leadingBaseCoefficient();
451                C[] oc = leftOreCond(c1, c2);
452                s1q = s1q.multiplyLeft(oc[0]);
453                sp = sp.multiplyLeft(oc[1]);
454                if (!s1q.equals(sp)) {
455                    System.out.println("Ore cond, s1q: " + s1q + " != " + sp);
456                }
457            }
458            t = p.multiplyLeft(contP).equals(P); // contPS q p1 == P
459            if (!t) {
460                System.out.println("p1P: " + contPS + " * " + p + " != " + P);
461            }
462            t = s.multiplyLeft(contS).equals(S); // PS
463            if (!t) {
464                System.out.println("s1S: " + contPS + " * " + s + " != " + S);
465            }
466            //System.out.println("isField: " + field);
467        }
468        return q.multiplyLeft(contPS);
469    }
470
471
472    /**
473     * Univariate GenSolvablePolynomial greatest common divisor. Uses
474     * pseudoRemainder for remainder.
475     * @param P univariate GenSolvablePolynomial.
476     * @param S univariate GenSolvablePolynomial.
477     * @return r = gcd(P,S) with P = P'*gcd(P,S) and S = S'*gcd(P,S).
478     */
479    @Override
480    public GenSolvablePolynomial<C> rightBaseGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) {
481        if (S == null || S.isZERO()) {
482            return P;
483        }
484        if (P == null || P.isZERO()) {
485            return S;
486        }
487        GenSolvablePolynomialRing<C> ring = P.ring;
488        if (ring.nvar > 1) {
489            throw new IllegalArgumentException(this.getClass().getName() + " no univariate polynomial");
490        }
491        // compute on coefficients
492        C contP = rightBaseContent(P);
493        C contS = rightBaseContent(S);
494        C contPS = contP.rightGcd(contS);
495        if (contPS.signum() < 0) {
496            contPS = contPS.negate();
497        }
498        if (debug) {
499            //System.out.println("contP = " + contP + ", contS = " + contS + ", rightGcd(contP,contS) = " + contPS);
500            C r1 = contP.rightDivide(contPS);
501            boolean t = r1.multiply(contPS).equals(contP);
502            if (!t) {
503                System.out.println("r1: " + r1 + " * " + contPS + " != " + contP + ", r1*cP="
504                                + r1.multiply(contPS));
505            }
506            C r2 = contS.rightDivide(contPS);
507            t = r2.multiply(contPS).equals(contS);
508            if (!t) {
509                System.out.println("r2: " + r2 + " * " + contPS + " != " + contS + ", r2*cS="
510                                + r2.multiply(contPS));
511            }
512            //System.out.println("contPS = " + contPS);
513        }
514        GenSolvablePolynomial<C> p = (GenSolvablePolynomial<C>) P.rightDivideCoeff(contP);
515        GenSolvablePolynomial<C> s = (GenSolvablePolynomial<C>) S.rightDivideCoeff(contS);
516        if (debug) {
517            boolean t = p.multiply(contP).equals(P);
518            if (!t) {
519                System.out.println("p: " + p + " * " + contP + " != " + P + ", p*cP=" + p.multiply(contP));
520            }
521            t = s.multiply(contS).equals(S);
522            if (!t) {
523                System.out.println("s: " + s + " * " + contS + " != " + S + ", s*cS=" + s.multiply(contS));
524            }
525        }
526        // compute on main variable
527        if (p.isONE()) {
528            return ring.valueOf(contPS);
529        }
530        if (s.isONE()) {
531            return ring.valueOf(contPS);
532        }
533        boolean field = ring.coFac.isField();
534        GenSolvablePolynomial<C> r = p;
535        GenSolvablePolynomial<C> q = s;
536        GenSolvablePolynomial<C> x;
537        if (r.degree(0) > q.degree(0)) {
538            x = r;
539            r = q;
540            q = x;
541        }
542        //System.out.println("baseGCD: q = " + q + ", r = " + r);
543        while (!r.isZERO()) {
544            x = FDUtil.<C> leftBaseSparsePseudoRemainder(q, r);
545            q = r;
546            if (field) {
547                r = x.monic();
548            } else {
549                r = x;
550            }
551            //System.out.println("baseGCD: r = " + r);
552        }
553        //q = leftBasePrimitivePart(q);
554        q = rightBasePrimitivePart(q);
555        //q = (GenSolvablePolynomial<C>) q.abs();
556        //System.out.println("baseGCD: q = " + q + ", r = " + r);
557        GenSolvablePolynomial<C> p1 = FDUtil.<C> leftBasePseudoQuotient(p, q); // TODO
558        GenSolvablePolynomial<C> s1 = FDUtil.<C> leftBasePseudoQuotient(s, q); // TODO 
559        //System.out.println("p1 = " + p1 + ", s1 = " + s1);
560        if (debug) {
561            boolean t = p1.multiply(q).equals(p);
562            if (!t) {
563                GenSolvablePolynomial<C> p1q = p1.multiply(q);
564                GenSolvablePolynomial<C> pp = p;
565                C c1 = p1q.leadingBaseCoefficient();
566                C c2 = pp.leadingBaseCoefficient();
567                C[] oc = rightOreCond(c1, c2);
568                p1q = p1q.multiply(oc[0]);
569                pp = pp.multiply(oc[1]);
570                if (!p1q.equals(pp)) {
571                    System.out.println("Ore cond, p1q: " + p1q + " != " + pp);
572                }
573            }
574            t = s1.multiply(q).equals(s);
575            if (!t) {
576                GenSolvablePolynomial<C> s1q = s1.multiply(q);
577                GenSolvablePolynomial<C> sp = s;
578                C c1 = s1q.leadingBaseCoefficient();
579                C c2 = sp.leadingBaseCoefficient();
580                C[] oc = rightOreCond(c1, c2);
581                s1q = s1q.multiply(oc[0]);
582                sp = sp.multiply(oc[1]);
583                if (!s1q.equals(sp)) {
584                    System.out.println("Ore cond, s1q: " + s1q + " != " + sp);
585                }
586            }
587            t = p.multiply(contP).equals(P); // contPS q p1 == P
588            if (!t) {
589                System.out.println("p1P: " + contPS + " * " + p + " != " + P);
590            }
591            t = s.multiply(contS).equals(S); // PS
592            if (!t) {
593                System.out.println("s1S: " + contPS + " * " + s + " != " + S);
594            }
595            //System.out.println("isField: " + field);
596        }
597        return q.multiply(contPS);
598    }
599
600
601    /**
602     * Univariate GenSolvablePolynomial left recursive greatest common divisor.
603     * Uses pseudoRemainder for remainder.
604     * @param P univariate recursive GenSolvablePolynomial.
605     * @param S univariate recursive GenSolvablePolynomial.
606     * @return 1 = gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where
607     *         deg_main(p) = deg_main(s) == 0.
608     */
609    @Override
610    public GenSolvablePolynomial<GenPolynomial<C>> leftRecursiveUnivariateGcd(
611                    GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) {
612        if (S == null || S.isZERO()) {
613            return P;
614        }
615        if (P == null || P.isZERO()) {
616            return S;
617        }
618        if (P.ring.nvar > 1) {
619            throw new IllegalArgumentException("no univariate polynomial");
620        }
621        return P.ring.getONE();
622    }
623
624
625    /**
626     * Univariate GenSolvablePolynomial right recursive greatest common divisor.
627     * Uses pseudoRemainder for remainder.
628     * @param P univariate recursive GenSolvablePolynomial.
629     * @param S univariate recursive GenSolvablePolynomial.
630     * @return 1 = gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where
631     *         deg_main(p) = deg_main(s) == 0.
632     */
633    @Override
634    public GenSolvablePolynomial<GenPolynomial<C>> rightRecursiveUnivariateGcd(
635                    GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) {
636        if (S == null || S.isZERO()) {
637            return P;
638        }
639        if (P == null || P.isZERO()) {
640            return S;
641        }
642        if (P.ring.nvar > 1) {
643            throw new IllegalArgumentException("no univariate polynomial");
644        }
645        return P.ring.getONE();
646    }
647
648}