Source code

001/*
002 * $Id: GCDModLongTest.java 3789 2011-10-01 18:54:43Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import junit.framework.Test;
012import junit.framework.TestCase;
013import junit.framework.TestSuite;
014
015import edu.jas.arith.BigInteger;
016import edu.jas.arith.ModLong;
017import edu.jas.arith.ModLongRing;
018import edu.jas.arith.PrimeList;
019import edu.jas.poly.GenPolynomial;
020import edu.jas.poly.GenPolynomialRing;
021import edu.jas.poly.PolyUtil;
022import edu.jas.poly.TermOrder;
023
024
025/**
026 * GCD Modular algorithm tests with JUnit.
027 * @author Heinz Kredel.
028 */
029
030public class GCDModLongTest 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 GCDModLongTest(String name) {
046        super(name);
047    }
048
049
050    /**
051     */
052    public static Test suite() {
053        TestSuite suite = new TestSuite(GCDModLongTest.class);
054        return suite;
055    }
056
057
058    //private final static int bitlen = 100;
059
060    GreatestCommonDivisorAbstract<ModLong> ufd;
061
062
063    TermOrder to = new TermOrder(TermOrder.INVLEX);
064
065
066    GenPolynomialRing<ModLong> dfac;
067
068
069    GenPolynomialRing<ModLong> cfac;
070
071
072    GenPolynomialRing<GenPolynomial<ModLong>> rfac;
073
074
075    PrimeList primes = new PrimeList();
076
077
078    ModLongRing mi;
079
080
081    ModLong ai;
082
083
084    ModLong bi;
085
086
087    ModLong ci;
088
089
090    ModLong di;
091
092
093    ModLong ei;
094
095
096    GenPolynomial<ModLong> a;
097
098
099    GenPolynomial<ModLong> b;
100
101
102    GenPolynomial<ModLong> c;
103
104
105    GenPolynomial<ModLong> d;
106
107
108    GenPolynomial<ModLong> e;
109
110
111    GenPolynomial<ModLong> ac;
112
113
114    GenPolynomial<ModLong> bc;
115
116
117    GenPolynomial<GenPolynomial<ModLong>> ar;
118
119
120    GenPolynomial<GenPolynomial<ModLong>> br;
121
122
123    GenPolynomial<GenPolynomial<ModLong>> cr;
124
125
126    GenPolynomial<GenPolynomial<ModLong>> dr;
127
128
129    GenPolynomial<GenPolynomial<ModLong>> er;
130
131
132    GenPolynomial<GenPolynomial<ModLong>> arc;
133
134
135    GenPolynomial<GenPolynomial<ModLong>> 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 ModLongRing(primes.get(0), true);
159        mi = new ModLongRing(5L, true);
160        ufd = new GreatestCommonDivisorPrimitive<ModLong>();
161        dfac = new GenPolynomialRing<ModLong>(mi, rl, to);
162        cfac = new GenPolynomialRing<ModLong>(mi, rl - 1, to);
163        rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(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     */
183    public void testModularEvaluationGcd() {
184
185        GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular<ModLong>(); // dummy type
186
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     */
243    public void testModularSimpleGcd() {
244
245        GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular<ModLong>(true); // dummy type
246
247        GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorPrimitive<BigInteger>();
248
249        GenPolynomial<BigInteger> a;
250        GenPolynomial<BigInteger> b;
251        GenPolynomial<BigInteger> c;
252        GenPolynomial<BigInteger> d;
253        GenPolynomial<BigInteger> e;
254
255        GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(), 3, to);
256
257        for (int i = 0; i < 1; i++) {
258            a = dfac.random(kl, ll + i, el + i, q);
259            b = dfac.random(kl, ll + i, el + i, q);
260            c = dfac.random(kl, ll + i, el + i, q);
261            c = c.multiply(dfac.univariate(0));
262            //a = ufd.basePrimitivePart(a);
263            //b = ufd.basePrimitivePart(b);
264
265            if (a.isZERO() || b.isZERO() || c.isZERO()) {
266                // skip for this turn
267                continue;
268            }
269            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
270            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
271            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
272
273            a = a.multiply(c);
274            b = b.multiply(c);
275
276            //System.out.println("a  = " + a);
277            //System.out.println("b  = " + b);
278
279            d = ufd_m.gcd(a, b);
280
281            c = ufd.basePrimitivePart(c).abs();
282            e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
283            //System.out.println("c  = " + c);
284            //System.out.println("d  = " + d);
285
286            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
287
288            e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
289            //System.out.println("e = " + e);
290            assertTrue("gcd(a,b) | a" + e, e.isZERO());
291
292            e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
293            //System.out.println("e = " + e);
294            assertTrue("gcd(a,b) | b" + e, e.isZERO());
295        }
296    }
297
298
299    /**
300     * Test recursive content and primitive part, modular coefficients.
301     * 
302     */
303    public void testRecursiveContentPPmodular() {
304
305        dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
306        cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
307        rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
308
309        GreatestCommonDivisorAbstract<ModLong> ufd = new GreatestCommonDivisorPrimitive<ModLong>();
310
311        for (int i = 0; i < 1; i++) {
312            a = cfac.random(kl, ll + 2 * i, el + i, q).monic();
313            cr = rfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
314            cr = PolyUtil.<ModLong> monic(cr);
315            //System.out.println("a  = " + a);
316            //System.out.println("cr = " + cr);
317            //a = ufd.basePrimitivePart(a);
318            //b = distribute(dfac,cr);
319            //b = ufd.basePrimitivePart(b);
320            //cr = recursive(rfac,b);
321            //System.out.println("a  = " + a);
322            //System.out.println("cr = " + cr);
323
324            cr = cr.multiply(a);
325            //System.out.println("cr = " + cr);
326
327            if (cr.isZERO()) {
328                // skip for this turn
329                continue;
330            }
331            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
332            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
333            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
334
335            c = ufd.recursiveContent(cr).monic();
336            dr = ufd.recursivePrimitivePart(cr);
337            dr = PolyUtil.<ModLong> monic(dr);
338            //System.out.println("c  = " + c);
339            //System.out.println("dr = " + dr);
340
341            //System.out.println("monic(a) = " + a.monic());
342            //System.out.println("monic(c) = " + c.monic());
343
344            ar = dr.multiply(c);
345            //System.out.println("ar = " + ar);
346            assertEquals("c == cont(c)pp(c)", cr, ar);
347        }
348    }
349
350
351    /**
352     * Test base gcd modular coefficients.
353     * 
354     */
355    public void testGCDbaseModular() {
356
357        dfac = new GenPolynomialRing<ModLong>(mi, 1, to);
358
359        GreatestCommonDivisorAbstract<ModLong> ufd = new GreatestCommonDivisorPrimitive<ModLong>();
360
361        for (int i = 0; i < 1; i++) {
362            a = dfac.random(kl, ll, el + 3 + i, q).monic();
363            b = dfac.random(kl, ll, el + 3 + i, q).monic();
364            c = dfac.random(kl, ll, el + 3 + i, q).monic();
365            //System.out.println("a = " + a);
366            //System.out.println("b = " + b);
367            //System.out.println("c = " + c);
368
369            if (a.isZERO() || b.isZERO() || c.isZERO()) {
370                // skip for this turn
371                continue;
372            }
373            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
374            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
375            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
376
377            ac = a.multiply(c);
378            bc = b.multiply(c);
379            //System.out.println("ac = " + ac);
380            //System.out.println("bc = " + bc);
381
382            //e = PolyUtil.<ModLong>basePseudoRemainder(ac,c);
383            //System.out.println("ac/c a = 0 " + e);
384            //assertTrue("ac/c-a != 0 " + e, e.isZERO() );
385            //e = PolyUtil.<ModLong>basePseudoRemainder(bc,c);
386            //System.out.println("bc/c-b = 0 " + e);
387            //assertTrue("bc/c-b != 0 " + e, e.isZERO() );
388
389            d = ufd.baseGcd(ac, bc);
390            d = d.monic(); // not required
391            //System.out.println("d = " + d);
392
393            e = PolyUtil.<ModLong> basePseudoRemainder(d, c);
394            //System.out.println("e = " + e);
395
396            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
397        }
398    }
399
400
401    /**
402     * Test recursive gcd modular coefficients.
403     * 
404     */
405    public void testRecursiveGCDModular() {
406
407        dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
408        cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
409        rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
410
411        //     GreatestCommonDivisorAbstract<ModLong> ufd 
412        //     = new GreatestCommonDivisorPrimitive<ModLong>();
413
414        for (int i = 0; i < 1; i++) {
415            ar = rfac.random(kl, 2, el + 2, q);
416            br = rfac.random(kl, 2, el + 2, q);
417            cr = rfac.random(kl, 2, el + 2, q);
418            ar = PolyUtil.<ModLong> monic(ar);
419            br = PolyUtil.<ModLong> monic(br);
420            cr = PolyUtil.<ModLong> monic(cr);
421            //System.out.println("ar = " + ar);
422            //System.out.println("br = " + br);
423            //System.out.println("cr = " + cr);
424
425            if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
426                // skip for this turn
427                continue;
428            }
429            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
430            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
431            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
432
433            arc = ar.multiply(cr);
434            brc = br.multiply(cr);
435            //System.out.println("arc = " + arc);
436            //System.out.println("brc = " + brc);
437
438            //er = PolyUtil.<ModLong>recursivePseudoRemainder(arc,cr);
439            //System.out.println("ac/c-a = 0 " + er);
440            //assertTrue("ac/c-a != 0 " + er, er.isZERO() );
441            //er = PolyUtil.<ModLong>recursivePseudoRemainder(brc,cr);
442            //System.out.println("bc/c-b = 0 " + er);
443            //assertTrue("bc/c-b != 0 " + er, er.isZERO() );
444
445            dr = ufd.recursiveUnivariateGcd(arc, brc);
446            dr = PolyUtil.<ModLong> monic(dr);
447            //System.out.println("cr = " + cr);
448            //System.out.println("dr = " + dr);
449
450            er = PolyUtil.<ModLong> recursivePseudoRemainder(dr, cr);
451            //System.out.println("er = " + er);
452
453            assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
454        }
455    }
456
457
458    /**
459     * Test arbitrary recursive gcd modular coefficients.
460     * 
461     */
462    public void testArbitraryRecursiveGCDModular() {
463
464        dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
465        cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
466        rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
467
468        //     GreatestCommonDivisorAbstract<ModLong> ufd 
469        //     = new GreatestCommonDivisorPrimitive<ModLong>();
470
471        for (int i = 0; i < 1; i++) {
472            ar = rfac.random(kl, 2, el + 2, q);
473            br = rfac.random(kl, 2, el + 2, q);
474            cr = rfac.random(kl, 2, el + 2, q);
475            ar = PolyUtil.<ModLong> monic(ar);
476            br = PolyUtil.<ModLong> monic(br);
477            cr = PolyUtil.<ModLong> monic(cr);
478            //System.out.println("ar = " + ar);
479            //System.out.println("br = " + br);
480            //System.out.println("cr = " + cr);
481
482            if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
483                // skip for this turn
484                continue;
485            }
486            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
487            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
488            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
489
490            arc = ar.multiply(cr);
491            brc = br.multiply(cr);
492            //System.out.println("arc = " + arc);
493            //System.out.println("brc = " + brc);
494
495            //er = PolyUtil.<ModLong>recursivePseudoRemainder(arc,cr);
496            //System.out.println("ac/c-a = 0 " + er);
497            //assertTrue("ac/c-a != 0 " + er, er.isZERO() );
498            //er = PolyUtil.<ModLong>recursivePseudoRemainder(brc,cr);
499            //System.out.println("bc/c-b = 0 " + er);
500            //assertTrue("bc/c-b != 0 " + er, er.isZERO() );
501
502            dr = ufd.recursiveGcd(arc, brc);
503            dr = PolyUtil.<ModLong> monic(dr);
504            //System.out.println("cr = " + cr);
505            //System.out.println("dr = " + dr);
506
507            er = PolyUtil.<ModLong> recursivePseudoRemainder(dr, cr);
508            //System.out.println("er = " + er);
509
510            assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
511        }
512    }
513
514
515    /**
516     * Test gcd modular coefficients.
517     * 
518     */
519    public void testGcdModular() {
520
521        dfac = new GenPolynomialRing<ModLong>(mi, 4, to);
522
523        for (int i = 0; i < 1; i++) {
524            a = dfac.random(kl, ll, el + i, q).monic();
525            b = dfac.random(kl, ll, el + i, q).monic();
526            c = dfac.random(kl, ll, el + i, q).monic();
527            //System.out.println("a = " + a);
528            //System.out.println("b = " + b);
529            //System.out.println("c = " + c);
530
531            if (a.isZERO() || b.isZERO() || c.isZERO()) {
532                // skip for this turn
533                continue;
534            }
535            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
536            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
537            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
538
539            ac = a.multiply(c);
540            bc = b.multiply(c);
541            //System.out.println("ac = " + ac);
542            //System.out.println("bc = " + bc);
543
544            //e = PolyUtil.<ModLong>basePseudoRemainder(ac,c);
545            //System.out.println("ac/c-a = 0 " + e);
546            //assertTrue("ac/c-a != 0 " + e, e.isZERO() );
547            //e = PolyUtil.<ModLong>basePseudoRemainder(bc,c);
548            //System.out.println("bc/c-b = 0 " + e);
549            //assertTrue("bc/c-b != 0 " + e, e.isZERO() );
550
551            d = ufd.gcd(ac, bc);
552            //System.out.println("d = " + d);
553            e = PolyUtil.<ModLong> basePseudoRemainder(d, c);
554            //System.out.println("e = " + e);
555            //System.out.println("c = " + c);
556            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
557
558            e = PolyUtil.<ModLong> basePseudoRemainder(ac, d);
559            //System.out.println("gcd(ac,bc) | ac " + e);
560            assertTrue("gcd(ac,bc) | ac " + e, e.isZERO());
561            e = PolyUtil.<ModLong> basePseudoRemainder(bc, d);
562            //System.out.println("gcd(ac,bc) | bc " + e);
563            assertTrue("gcd(ac,bc) | bc " + e, e.isZERO());
564        }
565    }
566
567
568    /**
569     * Test co-prime factors.
570     * 
571     */
572    public void testCoPrime() {
573
574        dfac = new GenPolynomialRing<ModLong>(mi, 3, to);
575
576        a = dfac.random(kl, 3, 2, q);
577        b = dfac.random(kl, 3, 2, q);
578        c = dfac.random(kl, 3, 2, q);
579        //System.out.println("a  = " + a);
580        //System.out.println("b  = " + b);
581        //System.out.println("c  = " + c);
582
583        if (a.isZERO() || b.isZERO() || c.isZERO()) {
584            // skip for this turn
585            return;
586        }
587        assertTrue("length( a ) <> 0", a.length() > 0);
588
589        d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
590        e = a.multiply(b).multiply(c);
591        //System.out.println("d  = " + d);
592        //System.out.println("c  = " + c);
593
594        List<GenPolynomial<ModLong>> F = new ArrayList<GenPolynomial<ModLong>>(5);
595        F.add(a);
596        F.add(b);
597        F.add(c);
598        F.add(d);
599        F.add(e);
600
601        List<GenPolynomial<ModLong>> P = ufd.coPrime(F);
602        //System.out.println("F = " + F);
603        //System.out.println("P = " + P);
604
605        assertTrue("is co-prime ", ufd.isCoPrime(P));
606        assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
607
608        P = ufd.coPrimeRec(F);
609        //System.out.println("F = " + F);
610        //System.out.println("P = " + P);
611
612        assertTrue("is co-prime ", ufd.isCoPrime(P));
613        assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
614    }
615
616}