Source code

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