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.ModLong;
013import edu.jas.arith.ModLongRing;
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 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    GreatestCommonDivisorAbstract<ModLong> ufd;
059
060
061    TermOrder to = new TermOrder(TermOrder.INVLEX);
062
063
064    GenPolynomialRing<ModLong> dfac;
065
066
067    GenPolynomialRing<ModLong> cfac;
068
069
070    GenPolynomialRing<GenPolynomial<ModLong>> rfac;
071
072
073    PrimeList primes = new PrimeList();
074
075
076    ModLongRing mi;
077
078
079    ModLong ai, bi, ci, di, ei;
080
081
082    GenPolynomial<ModLong> a, b, c, d, e;
083
084
085    GenPolynomial<ModLong> ac;
086
087
088    GenPolynomial<ModLong> bc;
089
090
091    GenPolynomial<GenPolynomial<ModLong>> ar, br, cr, dr, er;
092
093
094    GenPolynomial<GenPolynomial<ModLong>> arc;
095
096
097    GenPolynomial<GenPolynomial<ModLong>> brc;
098
099
100    int rl = 5;
101
102
103    int kl = 4;
104
105
106    int ll = 5;
107
108
109    int el = 3;
110
111
112    float q = 0.3f;
113
114
115    @Override
116    protected void setUp() {
117        a = b = c = d = e = null;
118        ai = bi = ci = di = ei = null;
119        ar = br = cr = dr = er = null;
120        //mi = new ModLongRing(primes.get(0), true);
121        mi = new ModLongRing(5L, true);
122        ufd = new GreatestCommonDivisorPrimitive<ModLong>();
123        dfac = new GenPolynomialRing<ModLong>(mi, rl, to);
124        cfac = new GenPolynomialRing<ModLong>(mi, rl - 1, to);
125        rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
126    }
127
128
129    @Override
130    protected void tearDown() {
131        a = b = c = d = e = null;
132        ai = bi = ci = di = ei = null;
133        ar = br = cr = dr = er = null;
134        ufd = null;
135        dfac = null;
136        cfac = null;
137        rfac = null;
138    }
139
140
141    /**
142     * Test modular algorithm gcd with modular evaluation recursive algorithm.
143     */
144    public void testModularEvaluationGcd() {
145        GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular<ModLong>(); // dummy type
146
147        GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorPrimitive<BigInteger>();
148
149        GenPolynomial<BigInteger> a;
150        GenPolynomial<BigInteger> b;
151        GenPolynomial<BigInteger> c;
152        GenPolynomial<BigInteger> d;
153        GenPolynomial<BigInteger> e;
154
155        GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(), 3, to);
156
157        for (int i = 0; i < 2; i++) {
158            a = dfac.random(kl, ll + i, el + i, q);
159            b = dfac.random(kl, ll + i, el + i, q);
160            c = dfac.random(kl, ll + i, el + i, q);
161            c = c.multiply(dfac.univariate(0));
162            //a = ufd.basePrimitivePart(a);
163            //b = ufd.basePrimitivePart(b);
164
165            if (a.isZERO() || b.isZERO() || c.isZERO()) {
166                // skip for this turn
167                continue;
168            }
169            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
170            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
171            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
172
173            a = a.multiply(c);
174            b = b.multiply(c);
175
176            //System.out.println("a  = " + a);
177            //System.out.println("b  = " + b);
178
179            d = ufd_m.gcd(a, b);
180
181            c = ufd.basePrimitivePart(c).abs();
182            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(d, c);
183            //System.out.println("c  = " + c);
184            //System.out.println("d  = " + d);
185
186            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
187
188            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, d);
189            //System.out.println("e = " + e);
190            assertTrue("gcd(a,b) | a" + e, e.isZERO());
191
192            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(b, d);
193            //System.out.println("e = " + e);
194            assertTrue("gcd(a,b) | b" + e, e.isZERO());
195        }
196    }
197
198
199    /**
200     * Test modular algorithm gcd with simple PRS recursive algorithm.
201     */
202    public void testModularSimpleGcd() {
203        GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular<ModLong>(true); // dummy type
204
205        GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorPrimitive<BigInteger>();
206
207        GenPolynomial<BigInteger> a;
208        GenPolynomial<BigInteger> b;
209        GenPolynomial<BigInteger> c;
210        GenPolynomial<BigInteger> d;
211        GenPolynomial<BigInteger> e;
212
213        GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(), 3, to);
214
215        for (int i = 0; i < 1; i++) {
216            a = dfac.random(kl, ll + i, el + i, q);
217            b = dfac.random(kl, ll + i, el + i, q);
218            c = dfac.random(kl, ll + i, el + i, q);
219            c = c.multiply(dfac.univariate(0));
220            //a = ufd.basePrimitivePart(a);
221            //b = ufd.basePrimitivePart(b);
222
223            if (a.isZERO() || b.isZERO() || c.isZERO()) {
224                // skip for this turn
225                continue;
226            }
227            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
228            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
229            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
230
231            a = a.multiply(c);
232            b = b.multiply(c);
233
234            //System.out.println("a  = " + a);
235            //System.out.println("b  = " + b);
236
237            d = ufd_m.gcd(a, b);
238
239            c = ufd.basePrimitivePart(c).abs();
240            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(d, c);
241            //System.out.println("c  = " + c);
242            //System.out.println("d  = " + d);
243
244            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
245
246            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, d);
247            //System.out.println("e = " + e);
248            assertTrue("gcd(a,b) | a" + e, e.isZERO());
249
250            e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(b, d);
251            //System.out.println("e = " + e);
252            assertTrue("gcd(a,b) | b" + e, e.isZERO());
253        }
254    }
255
256
257    /**
258     * Test recursive content and primitive part, modular coefficients.
259     */
260    public void testRecursiveContentPPmodular() {
261        dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
262        cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
263        rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
264
265        GreatestCommonDivisorAbstract<ModLong> ufd = new GreatestCommonDivisorPrimitive<ModLong>();
266
267        for (int i = 0; i < 1; i++) {
268            a = cfac.random(kl, ll + 2 * i, el + i, q).monic();
269            cr = rfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
270            cr = PolyUtil.<ModLong> monic(cr);
271            //System.out.println("a  = " + a);
272            //System.out.println("cr = " + cr);
273            //a = ufd.basePrimitivePart(a);
274            //b = distribute(dfac,cr);
275            //b = ufd.basePrimitivePart(b);
276            //cr = recursive(rfac,b);
277            //System.out.println("a  = " + a);
278            //System.out.println("cr = " + cr);
279
280            cr = cr.multiply(a);
281            //System.out.println("cr = " + cr);
282
283            if (cr.isZERO()) {
284                // skip for this turn
285                continue;
286            }
287            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
288            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
289            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
290
291            c = ufd.recursiveContent(cr).monic();
292            dr = ufd.recursivePrimitivePart(cr);
293            dr = PolyUtil.<ModLong> monic(dr);
294            //System.out.println("c  = " + c);
295            //System.out.println("dr = " + dr);
296
297            //System.out.println("monic(a) = " + a.monic());
298            //System.out.println("monic(c) = " + c.monic());
299
300            ar = dr.multiply(c);
301            //System.out.println("ar = " + ar);
302            assertEquals("c == cont(c)pp(c)", cr, ar);
303        }
304    }
305
306
307    /**
308     * Test base gcd modular coefficients.
309     */
310    public void testGCDbaseModular() {
311        dfac = new GenPolynomialRing<ModLong>(mi, 1, to);
312
313        GreatestCommonDivisorAbstract<ModLong> ufd = new GreatestCommonDivisorPrimitive<ModLong>();
314
315        for (int i = 0; i < 1; i++) {
316            a = dfac.random(kl, ll, el + 3 + i, q).monic();
317            b = dfac.random(kl, ll, el + 3 + i, q).monic();
318            c = dfac.random(kl, ll, el + 3 + i, q).monic();
319            //System.out.println("a = " + a);
320            //System.out.println("b = " + b);
321            //System.out.println("c = " + c);
322
323            if (a.isZERO() || b.isZERO() || c.isZERO()) {
324                // skip for this turn
325                continue;
326            }
327            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
328            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
329            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
330
331            ac = a.multiply(c);
332            bc = b.multiply(c);
333            //System.out.println("ac = " + ac);
334            //System.out.println("bc = " + bc);
335
336            //e = PolyUtil.<ModLong>baseSparsePseudoRemainder(ac,c);
337            //System.out.println("ac/c a = 0 " + e);
338            //assertTrue("ac/c-a != 0 " + e, e.isZERO() );
339            //e = PolyUtil.<ModLong>baseSparsePseudoRemainder(bc,c);
340            //System.out.println("bc/c-b = 0 " + e);
341            //assertTrue("bc/c-b != 0 " + e, e.isZERO() );
342
343            d = ufd.baseGcd(ac, bc);
344            d = d.monic(); // not required
345            //System.out.println("d = " + d);
346
347            e = PolyUtil.<ModLong> baseSparsePseudoRemainder(d, c);
348            //System.out.println("e = " + e);
349
350            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
351        }
352    }
353
354
355    /**
356     * Test recursive gcd modular coefficients.
357     */
358    public void testRecursiveGCDModular() {
359        dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
360        cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
361        rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
362
363        //     GreatestCommonDivisorAbstract<ModLong> ufd 
364        //     = new GreatestCommonDivisorPrimitive<ModLong>();
365
366        for (int i = 0; i < 1; i++) {
367            ar = rfac.random(kl, 2, el + 2, q);
368            br = rfac.random(kl, 2, el + 2, q);
369            cr = rfac.random(kl, 2, el + 2, q);
370            ar = PolyUtil.<ModLong> monic(ar);
371            br = PolyUtil.<ModLong> monic(br);
372            cr = PolyUtil.<ModLong> monic(cr);
373            //System.out.println("ar = " + ar);
374            //System.out.println("br = " + br);
375            //System.out.println("cr = " + cr);
376
377            if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
378                // skip for this turn
379                continue;
380            }
381            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
382            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
383            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
384
385            arc = ar.multiply(cr);
386            brc = br.multiply(cr);
387            //System.out.println("arc = " + arc);
388            //System.out.println("brc = " + brc);
389
390            //er = PolyUtil.<ModLong>recursiveSparsePseudoRemainder(arc,cr);
391            //System.out.println("ac/c-a = 0 " + er);
392            //assertTrue("ac/c-a != 0 " + er, er.isZERO() );
393            //er = PolyUtil.<ModLong>recursiveSparsePseudoRemainder(brc,cr);
394            //System.out.println("bc/c-b = 0 " + er);
395            //assertTrue("bc/c-b != 0 " + er, er.isZERO() );
396
397            dr = ufd.recursiveUnivariateGcd(arc, brc);
398            dr = PolyUtil.<ModLong> monic(dr);
399            //System.out.println("cr = " + cr);
400            //System.out.println("dr = " + dr);
401
402            er = PolyUtil.<ModLong> recursiveSparsePseudoRemainder(dr, cr);
403            //System.out.println("er = " + er);
404
405            assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
406        }
407    }
408
409
410    /**
411     * Test arbitrary recursive gcd modular coefficients.
412     */
413    public void testArbitraryRecursiveGCDModular() {
414        dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
415        cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
416        rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
417
418        //     GreatestCommonDivisorAbstract<ModLong> ufd 
419        //     = new GreatestCommonDivisorPrimitive<ModLong>();
420
421        for (int i = 0; i < 1; i++) {
422            ar = rfac.random(kl, 2, el + 2, q);
423            br = rfac.random(kl, 2, el + 2, q);
424            cr = rfac.random(kl, 2, el + 2, q);
425            ar = PolyUtil.<ModLong> monic(ar);
426            br = PolyUtil.<ModLong> monic(br);
427            cr = PolyUtil.<ModLong> monic(cr);
428            //System.out.println("ar = " + ar);
429            //System.out.println("br = " + br);
430            //System.out.println("cr = " + cr);
431
432            if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
433                // skip for this turn
434                continue;
435            }
436            assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
437            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
438            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
439
440            arc = ar.multiply(cr);
441            brc = br.multiply(cr);
442            //System.out.println("arc = " + arc);
443            //System.out.println("brc = " + brc);
444
445            //er = PolyUtil.<ModLong>recursiveSparsePseudoRemainder(arc,cr);
446            //System.out.println("ac/c-a = 0 " + er);
447            //assertTrue("ac/c-a != 0 " + er, er.isZERO() );
448            //er = PolyUtil.<ModLong>recursiveSparsePseudoRemainder(brc,cr);
449            //System.out.println("bc/c-b = 0 " + er);
450            //assertTrue("bc/c-b != 0 " + er, er.isZERO() );
451
452            dr = ufd.recursiveGcd(arc, brc);
453            dr = PolyUtil.<ModLong> monic(dr);
454            //System.out.println("cr = " + cr);
455            //System.out.println("dr = " + dr);
456
457            er = PolyUtil.<ModLong> recursiveSparsePseudoRemainder(dr, cr);
458            //System.out.println("er = " + er);
459
460            assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
461        }
462    }
463
464
465    /**
466     * Test gcd modular coefficients.
467     */
468    public void testGcdModular() {
469        dfac = new GenPolynomialRing<ModLong>(mi, 4, to);
470
471        for (int i = 0; i < 1; i++) {
472            a = dfac.random(kl, ll, el + i, q).monic();
473            b = dfac.random(kl, ll, el + i, q).monic();
474            c = dfac.random(kl, ll, el + i, q).monic();
475            //System.out.println("a = " + a);
476            //System.out.println("b = " + b);
477            //System.out.println("c = " + c);
478
479            if (a.isZERO() || b.isZERO() || c.isZERO()) {
480                // skip for this turn
481                continue;
482            }
483            assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
484            //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
485            //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
486
487            ac = a.multiply(c);
488            bc = b.multiply(c);
489            //System.out.println("ac = " + ac);
490            //System.out.println("bc = " + bc);
491
492            //e = PolyUtil.<ModLong>baseSparsePseudoRemainder(ac,c);
493            //System.out.println("ac/c-a = 0 " + e);
494            //assertTrue("ac/c-a != 0 " + e, e.isZERO() );
495            //e = PolyUtil.<ModLong>baseSparsePseudoRemainder(bc,c);
496            //System.out.println("bc/c-b = 0 " + e);
497            //assertTrue("bc/c-b != 0 " + e, e.isZERO() );
498
499            d = ufd.gcd(ac, bc);
500            //System.out.println("d = " + d);
501            e = PolyUtil.<ModLong> baseSparsePseudoRemainder(d, c);
502            //System.out.println("e = " + e);
503            //System.out.println("c = " + c);
504            assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
505
506            e = PolyUtil.<ModLong> baseSparsePseudoRemainder(ac, d);
507            //System.out.println("gcd(ac,bc) | ac " + e);
508            assertTrue("gcd(ac,bc) | ac " + e, e.isZERO());
509            e = PolyUtil.<ModLong> baseSparsePseudoRemainder(bc, d);
510            //System.out.println("gcd(ac,bc) | bc " + e);
511            assertTrue("gcd(ac,bc) | bc " + e, e.isZERO());
512        }
513    }
514
515
516    /**
517     * Test co-prime factors.
518     */
519    public void testCoPrime() {
520        dfac = new GenPolynomialRing<ModLong>(mi, 3, to);
521
522        a = dfac.random(kl, 3, 2, q);
523        b = dfac.random(kl, 3, 2, q);
524        c = dfac.random(kl, 3, 2, q);
525        //System.out.println("a  = " + a);
526        //System.out.println("b  = " + b);
527        //System.out.println("c  = " + c);
528
529        if (a.isZERO() || b.isZERO() || c.isZERO()) {
530            // skip for this turn
531            return;
532        }
533        assertTrue("length( a ) <> 0", a.length() > 0);
534
535        d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
536        e = a.multiply(b).multiply(c);
537        //System.out.println("d  = " + d);
538        //System.out.println("c  = " + c);
539
540        List<GenPolynomial<ModLong>> F = new ArrayList<GenPolynomial<ModLong>>(5);
541        F.add(a);
542        F.add(b);
543        F.add(c);
544        F.add(d);
545        F.add(e);
546
547        List<GenPolynomial<ModLong>> P = ufd.coPrime(F);
548        //System.out.println("F = " + F);
549        //System.out.println("P = " + P);
550
551        assertTrue("is co-prime ", ufd.isCoPrime(P));
552        assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
553
554        P = ufd.coPrimeRec(F);
555        //System.out.println("F = " + F);
556        //System.out.println("P = " + P);
557
558        assertTrue("is co-prime ", ufd.isCoPrime(P));
559        assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
560    }
561
562}