Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import edu.jas.arith.BigInteger;
012import edu.jas.arith.ModInteger;
013import edu.jas.arith.ModIntegerRing;
014import edu.jas.arith.PrimeList;
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.GenPolynomialRing;
017import edu.jas.poly.PolyUtil;
018import edu.jas.poly.TermOrder;
019
020import junit.framework.Test;
021import junit.framework.TestCase;
022import junit.framework.TestSuite;
023
024
025/**
026 * GCD Modular algorithm tests with JUnit.
027 * @author Heinz Kredel
028 */
029
030public class GCDModularTest extends TestCase {
031
032
033    /**
034     * main.
035     */
036    public static void main(String[] args) {
037        junit.textui.TestRunner.run(suite());
038    }
039
040
041    /**
042     * Constructs a <CODE>GCDModularTest</CODE> object.
043     * @param name String.
044     */
045    public GCDModularTest(String name) {
046        super(name);
047    }
048
049
050    /**
051     */
052    public static Test suite() {
053        TestSuite suite = new TestSuite(GCDModularTest.class);
054        return suite;
055    }
056
057
058    GreatestCommonDivisorAbstract<ModInteger> ufd;
059
060
061    TermOrder to = new TermOrder(TermOrder.INVLEX);
062
063
064    GenPolynomialRing<ModInteger> dfac;
065
066
067    GenPolynomialRing<ModInteger> cfac;
068
069
070    GenPolynomialRing<GenPolynomial<ModInteger>> rfac;
071
072
073    PrimeList primes = new PrimeList();
074
075
076    ModIntegerRing mi;
077
078
079    ModInteger ai, bi, ci, di, ei;
080
081
082    GenPolynomial<ModInteger> a, b, c, d, e;
083
084
085    GenPolynomial<ModInteger> ac, bc;
086
087
088    GenPolynomial<GenPolynomial<ModInteger>> ar, br, cr, dr, er;
089
090
091    GenPolynomial<GenPolynomial<ModInteger>> arc, brc;
092
093
094    int rl = 5;
095
096
097    int kl = 4;
098
099
100    int ll = 5;
101
102
103    int el = 3;
104
105
106    float q = 0.3f;
107
108
109    @Override
110    protected void setUp() {
111        a = b = c = d = e = null;
112        ai = bi = ci = di = ei = null;
113        ar = br = cr = dr = er = null;
114        //mi = new ModIntegerRing(primes.get(0), true);
115        mi = new ModIntegerRing(19L, true);
116        ufd = new GreatestCommonDivisorPrimitive<ModInteger>();
117        dfac = new GenPolynomialRing<ModInteger>(mi, rl, to);
118        cfac = new GenPolynomialRing<ModInteger>(mi, rl - 1, to);
119        rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to);
120    }
121
122
123    @Override
124    protected void tearDown() {
125        a = b = c = d = e = null;
126        ai = bi = ci = di = ei = null;
127        ar = br = cr = dr = er = null;
128        ufd = null;
129        dfac = null;
130        cfac = null;
131        rfac = null;
132    }
133
134
135    /**
136     * Test modular algorithm gcd with modular evaluation recursive algorithm.
137     */
138    public void testModularEvaluationGcd() {
139        GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular<ModInteger>(/*false*/);
140        GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorPrimitive<BigInteger>();
141
142        GenPolynomial<BigInteger> a, b, c, d, e;
143
144        GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(), 3, to);
145
146        for (int i = 0; i < 2; i++) {
147            a = dfac.random(kl, ll + i, el + i, q);
148            b = dfac.random(kl, ll + i, el + i, q);
149            c = dfac.random(kl, ll + i, el + i, q);
150            c = c.multiply(dfac.univariate(0));
151            //a = ufd.basePrimitivePart(a);
152            //b = ufd.basePrimitivePart(b);
153
154            if (a.isZERO() || b.isZERO() || c.isZERO()) {
155                // skip for this turn
156                continue;
157            }
158            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
159            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
160            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
161
162            a = a.multiply(c);
163            b = b.multiply(c);
164
165            //System.out.println("a  = " + a);
166            //System.out.println("b  = " + b);
167
168            d = ufd_m.gcd(a, b);
169
170            c = ufd.basePrimitivePart(c).abs();
171            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(d, c);
172            //System.out.println("c  = " + c);
173            //System.out.println("d  = " + d);
174
175            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
176
177            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, d);
178            //System.out.println("e = " + e);
179            assertTrue("gcd(a,b) | a" + e, e.isZERO());
180
181            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(b, d);
182            //System.out.println("e = " + e);
183            assertTrue("gcd(a,b) | b" + e, e.isZERO());
184        }
185    }
186
187
188    /**
189     * Test modular algorithm gcd with simple PRS recursive algorithm.
190     */
191    public void testModularSimpleGcd() {
192        GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular<ModInteger>(true);
193        GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorPrimitive<BigInteger>();
194
195        GenPolynomial<BigInteger> a, b, c, d, e;
196
197        GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(), 3, to);
198
199        for (int i = 0; i < 1; i++) {
200            a = dfac.random(kl, ll + i, el + i, q);
201            b = dfac.random(kl, ll + i, el + i, q);
202            c = dfac.random(kl, ll + i, el + i, q);
203            c = c.multiply(dfac.univariate(0));
204            //a = ufd.basePrimitivePart(a);
205            //b = ufd.basePrimitivePart(b);
206
207            if (a.isZERO() || b.isZERO() || c.isZERO()) {
208                // skip for this turn
209                continue;
210            }
211            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
212            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
213            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
214
215            a = a.multiply(c);
216            b = b.multiply(c);
217
218            //System.out.println("a  = " + a);
219            //System.out.println("b  = " + b);
220
221            d = ufd_m.gcd(a, b);
222
223            c = ufd.basePrimitivePart(c).abs();
224            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(d, c);
225            //System.out.println("c  = " + c);
226            //System.out.println("d  = " + d);
227
228            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
229
230            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, d);
231            //System.out.println("e = " + e);
232            assertTrue("gcd(a,b) | a" + e, e.isZERO());
233
234            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(b, d);
235            //System.out.println("e = " + e);
236            assertTrue("gcd(a,b) | b" + e, e.isZERO());
237        }
238    }
239
240
241    /**
242     * Test recursive content and primitive part, modular coefficients.
243     */
244    public void testRecursiveContentPPmodular() {
245        dfac = new GenPolynomialRing<ModInteger>(mi, 2, to);
246        cfac = new GenPolynomialRing<ModInteger>(mi, 2 - 1, to);
247        rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to);
248
249        GreatestCommonDivisorAbstract<ModInteger> ufd = new GreatestCommonDivisorPrimitive<ModInteger>();
250
251        for (int i = 0; i < 1; i++) {
252            a = cfac.random(kl, ll + 2 * i, el + i, q).monic();
253            cr = rfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
254            cr = PolyUtil.<ModInteger> monic(cr);
255            //System.out.println("a  = " + a);
256            //System.out.println("cr = " + cr);
257            //a = ufd.basePrimitivePart(a);
258            //b = distribute(dfac,cr);
259            //b = ufd.basePrimitivePart(b);
260            //cr = recursive(rfac,b);
261            //System.out.println("a  = " + a);
262            //System.out.println("cr = " + cr);
263
264            cr = cr.multiply(a);
265            //System.out.println("cr = " + cr);
266
267            if (cr.isZERO()) {
268                // skip for this turn
269                continue;
270            }
271            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
272            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
273            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
274
275            c = ufd.recursiveContent(cr).monic();
276            dr = ufd.recursivePrimitivePart(cr);
277            dr = PolyUtil.<ModInteger> monic(dr);
278            //System.out.println("c  = " + c);
279            //System.out.println("dr = " + dr);
280
281            //System.out.println("monic(a) = " + a.monic());
282            //System.out.println("monic(c) = " + c.monic());
283
284            ar = dr.multiply(c);
285            //System.out.println("ar = " + ar);
286            assertEquals("c == cont(c)pp(c)", cr, ar);
287        }
288    }
289
290
291    /**
292     * Test base gcd modular coefficients.
293     */
294    public void testGCDbaseModular() {
295        dfac = new GenPolynomialRing<ModInteger>(mi, 1, to);
296
297        GreatestCommonDivisorAbstract<ModInteger> ufd = new GreatestCommonDivisorPrimitive<ModInteger>();
298
299        for (int i = 0; i < 1; i++) {
300            a = dfac.random(kl, ll, el + 3 + i, q).monic();
301            b = dfac.random(kl, ll, el + 3 + i, q).monic();
302            c = dfac.random(kl, ll, el + 3 + i, q).monic();
303            //System.out.println("a = " + a);
304            //System.out.println("b = " + b);
305            //System.out.println("c = " + c);
306
307            if (a.isZERO() || b.isZERO() || c.isZERO()) {
308                // skip for this turn
309                continue;
310            }
311            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
312            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
313            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
314
315            ac = a.multiply(c);
316            bc = b.multiply(c);
317            //System.out.println("ac = " + ac);
318            //System.out.println("bc = " + bc);
319
320            //e = PolyUtil.<ModInteger>baseSparsePseudoRemainder(ac,c);
321            //System.out.println("ac/c a = 0 " + e);
322            //assertTrue("ac/c-a != 0 " + e, e.isZERO() );
323            //e = PolyUtil.<ModInteger>baseSparsePseudoRemainder(bc,c);
324            //System.out.println("bc/c-b = 0 " + e);
325            //assertTrue("bc/c-b != 0 " + e, e.isZERO() );
326
327            d = ufd.baseGcd(ac, bc);
328            d = d.monic(); // not required
329            //System.out.println("d = " + d);
330
331            e = PolyUtil.<ModInteger> baseSparsePseudoRemainder(d, c);
332            //System.out.println("e = " + e);
333
334            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
335        }
336    }
337
338
339    /**
340     * Test recursive gcd modular coefficients.
341     */
342    public void testRecursiveGCDModular() {
343        dfac = new GenPolynomialRing<ModInteger>(mi, 2, to);
344        cfac = new GenPolynomialRing<ModInteger>(mi, 2 - 1, to);
345        rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to);
346
347        //     GreatestCommonDivisorAbstract<ModInteger> ufd 
348        //     = new GreatestCommonDivisorPrimitive<ModInteger>();
349
350        for (int i = 0; i < 1; i++) {
351            ar = rfac.random(kl, 2, el + 2, q);
352            br = rfac.random(kl, 2, el + 2, q);
353            cr = rfac.random(kl, 2, el + 2, q);
354            ar = PolyUtil.<ModInteger> monic(ar);
355            br = PolyUtil.<ModInteger> monic(br);
356            cr = PolyUtil.<ModInteger> monic(cr);
357            //System.out.println("ar = " + ar);
358            //System.out.println("br = " + br);
359            //System.out.println("cr = " + cr);
360
361            if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
362                // skip for this turn
363                continue;
364            }
365            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
366            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
367            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
368
369            arc = ar.multiply(cr);
370            brc = br.multiply(cr);
371            //System.out.println("arc = " + arc);
372            //System.out.println("brc = " + brc);
373
374            //er = PolyUtil.<ModInteger>recursiveSparsePseudoRemainder(arc,cr);
375            //System.out.println("ac/c-a = 0 " + er);
376            //assertTrue("ac/c-a != 0 " + er, er.isZERO() );
377            //er = PolyUtil.<ModInteger>recursiveSparsePseudoRemainder(brc,cr);
378            //System.out.println("bc/c-b = 0 " + er);
379            //assertTrue("bc/c-b != 0 " + er, er.isZERO() );
380
381            dr = ufd.recursiveUnivariateGcd(arc, brc);
382            dr = PolyUtil.<ModInteger> monic(dr);
383            //System.out.println("cr = " + cr);
384            //System.out.println("dr = " + dr);
385
386            er = PolyUtil.<ModInteger> recursiveSparsePseudoRemainder(dr, cr);
387            //System.out.println("er = " + er);
388
389            assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
390        }
391    }
392
393
394    /**
395     * Test arbitrary recursive gcd modular coefficients.
396     */
397    public void testArbitraryRecursiveGCDModular() {
398        dfac = new GenPolynomialRing<ModInteger>(mi, 2, to);
399        cfac = new GenPolynomialRing<ModInteger>(mi, 2 - 1, to);
400        rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to);
401
402        //     GreatestCommonDivisorAbstract<ModInteger> ufd 
403        //     = new GreatestCommonDivisorPrimitive<ModInteger>();
404
405        for (int i = 0; i < 1; i++) {
406            ar = rfac.random(kl, 2, el + 2, q);
407            br = rfac.random(kl, 2, el + 2, q);
408            cr = rfac.random(kl, 2, el + 2, q);
409            ar = PolyUtil.<ModInteger> monic(ar);
410            br = PolyUtil.<ModInteger> monic(br);
411            cr = PolyUtil.<ModInteger> monic(cr);
412            //System.out.println("ar = " + ar);
413            //System.out.println("br = " + br);
414            //System.out.println("cr = " + cr);
415
416            if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
417                // skip for this turn
418                continue;
419            }
420            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
421            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
422            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
423
424            arc = ar.multiply(cr);
425            brc = br.multiply(cr);
426            //System.out.println("arc = " + arc);
427            //System.out.println("brc = " + brc);
428
429            //er = PolyUtil.<ModInteger>recursiveSparsePseudoRemainder(arc,cr);
430            //System.out.println("ac/c-a = 0 " + er);
431            //assertTrue("ac/c-a != 0 " + er, er.isZERO() );
432            //er = PolyUtil.<ModInteger>recursiveSparsePseudoRemainder(brc,cr);
433            //System.out.println("bc/c-b = 0 " + er);
434            //assertTrue("bc/c-b != 0 " + er, er.isZERO() );
435
436            dr = ufd.recursiveGcd(arc, brc);
437            dr = PolyUtil.<ModInteger> monic(dr);
438            //System.out.println("cr = " + cr);
439            //System.out.println("dr = " + dr);
440
441            er = PolyUtil.<ModInteger> recursiveSparsePseudoRemainder(dr, cr);
442            //System.out.println("er = " + er);
443
444            assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
445        }
446    }
447
448
449    /**
450     * Test gcd modular coefficients.
451     */
452    public void testGcdModular() {
453        dfac = new GenPolynomialRing<ModInteger>(mi, 4, to);
454
455        for (int i = 0; i < 1; i++) {
456            a = dfac.random(kl, ll, el + i, q).monic();
457            b = dfac.random(kl, ll, el + i, q).monic();
458            c = dfac.random(kl, ll, el + i, q).monic();
459            //System.out.println("a = " + a);
460            //System.out.println("b = " + b);
461            //System.out.println("c = " + c);
462
463            if (a.isZERO() || b.isZERO() || c.isZERO()) {
464                // skip for this turn
465                continue;
466            }
467            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
468            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
469            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
470
471            ac = a.multiply(c);
472            bc = b.multiply(c);
473            //System.out.println("ac = " + ac);
474            //System.out.println("bc = " + bc);
475
476            //e = PolyUtil.<ModInteger>baseSparsePseudoRemainder(ac,c);
477            //System.out.println("ac/c-a = 0 " + e);
478            //assertTrue("ac/c-a != 0 " + e, e.isZERO() );
479            //e = PolyUtil.<ModInteger>baseSparsePseudoRemainder(bc,c);
480            //System.out.println("bc/c-b = 0 " + e);
481            //assertTrue("bc/c-b != 0 " + e, e.isZERO() );
482
483            d = ufd.gcd(ac, bc);
484            //System.out.println("d = " + d);
485            e = PolyUtil.<ModInteger> baseSparsePseudoRemainder(d, c);
486            //System.out.println("e = " + e);
487            //System.out.println("c = " + c);
488            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
489
490            e = PolyUtil.<ModInteger> baseSparsePseudoRemainder(ac, d);
491            //System.out.println("gcd(ac,bc) | ac " + e);
492            assertTrue("gcd(ac,bc) | ac " + e, e.isZERO());
493            e = PolyUtil.<ModInteger> baseSparsePseudoRemainder(bc, d);
494            //System.out.println("gcd(ac,bc) | bc " + e);
495            assertTrue("gcd(ac,bc) | bc " + e, e.isZERO());
496        }
497    }
498
499
500    /**
501     * Test co-prime factors.
502     */
503    public void testCoPrime() {
504        dfac = new GenPolynomialRing<ModInteger>(mi, 3, to);
505
506        a = dfac.random(kl, 3, 2, q);
507        b = dfac.random(kl, 3, 2, q);
508        c = dfac.random(kl, 3, 2, q);
509        //System.out.println("a  = " + a);
510        //System.out.println("b  = " + b);
511        //System.out.println("c  = " + c);
512
513        if (a.isZERO() || b.isZERO() || c.isZERO()) {
514            // skip for this turn
515            return;
516        }
517        assertTrue("length( a ) <> 0", a.length() > 0);
518
519        d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
520        e = a.multiply(b).multiply(c);
521        //System.out.println("d  = " + d);
522        //System.out.println("c  = " + c);
523
524        List<GenPolynomial<ModInteger>> F = new ArrayList<GenPolynomial<ModInteger>>(5);
525        F.add(a);
526        F.add(b);
527        F.add(c);
528        F.add(d);
529        F.add(e);
530
531        List<GenPolynomial<ModInteger>> P = ufd.coPrime(F);
532        //System.out.println("F = " + F);
533        //System.out.println("P = " + P);
534
535        assertTrue("is co-prime ", ufd.isCoPrime(P));
536        assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
537
538        P = ufd.coPrimeRec(F);
539        //System.out.println("F = " + F);
540        //System.out.println("P = " + P);
541
542        assertTrue("is co-prime ", ufd.isCoPrime(P));
543        assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
544    }
545
546
547    /**
548     * Test base resultant modular coefficients.
549     */
550    public void testResultantBaseModular() {
551        dfac = new GenPolynomialRing<ModInteger>(mi, 1, to);
552
553        GreatestCommonDivisorSimple<ModInteger> ufds = new GreatestCommonDivisorSimple<ModInteger>();
554        GreatestCommonDivisorSubres<ModInteger> sres = new GreatestCommonDivisorSubres<ModInteger>();
555
556        for (int i = 0; i < 3; i++) {
557            a = dfac.random(kl, ll, el + 3 + i, q).monic();
558            b = dfac.random(kl, ll, el + 3 + i, q).monic();
559            c = dfac.random(kl, ll, el + 3 + i, q).monic();
560            //System.out.println("a = " + a);
561            //System.out.println("b = " + b);
562            //System.out.println("c = " + c);
563
564            if (a.isZERO() || b.isZERO() || c.isZERO()) {
565                // skip for this turn
566                continue;
567            }
568            if (c.isConstant()) {
569                c = dfac.univariate(0, 1);
570            }
571            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
572
573            d = ufds.baseResultant(a, b);
574            //System.out.println("d = " + d);
575            e = sres.baseResultant(a, b);
576            //System.out.println("e = " + e);
577            assertEquals("d == e: " + d.subtract(e), d.signum(), e.signum());
578            //assertEquals("d == e: " + d.subtract(e), d, e);
579
580            ac = a.multiply(c);
581            bc = b.multiply(c);
582            //System.out.println("ac = " + ac);
583            //System.out.println("bc = " + bc);
584
585            d = ufds.baseResultant(ac, bc);
586            //System.out.println("d = " + d);
587            assertTrue("d == 0: " + d, d.isZERO());
588
589            e = sres.baseResultant(ac, bc);
590            //System.out.println("e = " + e);
591            assertTrue("e == 0: " + e, e.isZERO());
592
593            //assertEquals("d == e: " + d.subtract(e), d, e);
594        }
595    }
596
597
598    /**
599     * Test recursive resultant modular coefficients.
600     */
601    public void testRecursiveResultantModular() {
602        cfac = new GenPolynomialRing<ModInteger>(mi, 2 - 0, to);
603        rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to);
604        //System.out.println("rfac = " + rfac);
605
606        GreatestCommonDivisorSimple<ModInteger> ufds = new GreatestCommonDivisorSimple<ModInteger>();
607        GreatestCommonDivisorSubres<ModInteger> sres = new GreatestCommonDivisorSubres<ModInteger>();
608
609        for (int i = 0; i < 1; i++) {
610            ar = rfac.random(kl, 2, el + 2, q);
611            br = rfac.random(kl, 2, el + 3, q);
612            cr = rfac.random(kl, 2, el + 1, q);
613            ar = PolyUtil.<ModInteger> monic(ar);
614            br = PolyUtil.<ModInteger> monic(br);
615            cr = PolyUtil.<ModInteger> monic(cr);
616            //System.out.println("ar = " + ar);
617            //System.out.println("br = " + br);
618            //System.out.println("cr = " + cr);
619
620            if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
621                // skip for this turn
622                continue;
623            }
624            if (cr.isConstant()) {
625                cr = rfac.univariate(0, 1);
626            }
627            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
628
629            dr = ufds.recursiveUnivariateResultant(ar, br);
630            //System.out.println("dr = " + dr);
631            er = sres.recursiveUnivariateResultant(ar, br);
632            //System.out.println("er = " + er);
633            assertEquals("dr == er: " + dr.subtract(er), dr.signum(), er.signum());
634            //assertEquals("dr == er: " + dr.subtract(er), dr, er);
635
636            arc = ar.multiply(cr);
637            brc = br.multiply(cr);
638            //System.out.println("arc = " + arc);
639            //System.out.println("brc = " + brc);
640
641            dr = ufds.recursiveUnivariateResultant(arc, brc);
642            //System.out.println("dr = " + dr);
643            //assertTrue("dr == 0: " + dr, dr.isZERO());
644
645            er = sres.recursiveUnivariateResultant(arc, brc);
646            //System.out.println("er = " + er);
647            //assertTrue("er == 0: " + er, er.isZERO());
648
649            assertEquals("dr == er: " + dr.subtract(er), dr.signum(), er.signum());
650        }
651    }
652
653
654    /**
655     * Test resultant modular coefficients.
656     */
657    public void testResultantModular() {
658        dfac = new GenPolynomialRing<ModInteger>(mi, 4, to);
659        //System.out.println("dfac = " + dfac);
660
661        GreatestCommonDivisorSimple<ModInteger> ufds = new GreatestCommonDivisorSimple<ModInteger>();
662        GreatestCommonDivisorSubres<ModInteger> sres = new GreatestCommonDivisorSubres<ModInteger>();
663
664        for (int i = 0; i < 1; i++) {
665            a = dfac.random(kl, ll, el + i, q).monic();
666            b = dfac.random(kl, ll, el + i, q).monic();
667            c = dfac.random(kl, ll, el + i, q).monic();
668            //System.out.println("a = " + a);
669            //System.out.println("b = " + b);
670            //System.out.println("c = " + c);
671
672            if (a.isZERO() || b.isZERO() || c.isZERO()) {
673                // skip for this turn
674                continue;
675            }
676            if (c.isConstant()) {
677                c = dfac.univariate(0, 1);
678            }
679            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
680
681            d = ufds.resultant(a, b);
682            //System.out.println("d = " + d);
683            e = sres.resultant(a, b);
684            //System.out.println("e = " + e);
685            assertEquals("d == e: " + d.subtract(e), d.signum(), e.signum());
686            //assertEquals("d == e: " + d.subtract(e), d, e);
687
688            ac = a.multiply(c);
689            bc = b.multiply(c);
690            //System.out.println("ac = " + ac);
691            //System.out.println("bc = " + bc);
692
693            d = ufds.resultant(ac, bc);
694            //System.out.println("d = " + d);
695            //assertTrue("d == 0: " + d, d.isZERO());
696
697            e = sres.resultant(ac, bc);
698            //System.out.println("e = " + e);
699            //assertTrue("e == 0: " + e, e.isZERO());
700
701            assertEquals("d == e: " + d.subtract(e), d.signum(), e.signum());
702        }
703    }
704
705
706    /**
707     * Test gcd example modular.
708     */
709    public void testGCDExamModular() {
710        GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorModular<ModInteger>();
711        GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1),
712                        new String[] { "t", "x" }, to);
713        GenPolynomial<BigInteger> a, b, d, e;
714
715        a = dfac.parse("x**3 + x**2 - t * x - t");
716        b = dfac.parse("3 * x**2 + 2 * x - t");
717
718        //System.out.println("a = " + a);
719        //System.out.println("b = " + b);
720
721        d = ufd.gcd(a, b);
722        //System.out.println("c = " + c);
723        //System.out.println("d = " + d);
724
725        e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, d);
726        //System.out.println("e = " + e);
727        assertTrue("gcd(a,b) | a " + e, e.isZERO());
728
729        e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(b, d);
730        //System.out.println("e = " + e);
731        assertTrue("gcd(a,b) | b " + e, e.isZERO());
732    }
733
734}