Source code

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