001/*
002 * $Id: SquarefreeQuotModTest.java 3789 2011-10-01 18:54:43Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.SortedMap;
009
010import junit.framework.Test;
011import junit.framework.TestCase;
012import junit.framework.TestSuite;
013
014import edu.jas.arith.ModInteger;
015import edu.jas.arith.ModIntegerRing;
016import edu.jas.kern.ComputerThreads;
017import edu.jas.poly.ExpVector;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import edu.jas.poly.PolyUtil;
021import edu.jas.poly.TermOrder;
022import edu.jas.structure.Power;
023
024
025/**
026 * Squarefree factorization tests with JUnit.
027 * @author Heinz Kredel.
028 */
029
030public class SquarefreeQuotModTest extends TestCase {
031
032
033    /**
034     * main.
035     */
036    public static void main(String[] args) {
037        //BasicConfigurator.configure();
038        junit.textui.TestRunner.run(suite());
039        ComputerThreads.terminate();
040    }
041
042
043    /**
044     * Constructs a <CODE>SquarefreeQuotModTest</CODE> object.
045     * @param name String.
046     */
047    public SquarefreeQuotModTest(String name) {
048        super(name);
049    }
050
051
052    /**
053     */
054    public static Test suite() {
055        TestSuite suite = new TestSuite(SquarefreeQuotModTest.class);
056        return suite;
057    }
058
059
060    TermOrder to = new TermOrder(TermOrder.INVLEX);
061
062
063    int rl = 3;
064
065
066    int kl = 1;
067
068
069    int ll = 3;
070
071
072    int el = 3;
073
074
075    float q = 0.25f;
076
077
078    String[] vars;
079
080
081    String[] cvars;
082
083
084    String[] c1vars;
085
086
087    String[] rvars;
088
089
090    ModIntegerRing mfac;
091
092
093    String[] alpha;
094
095
096    GenPolynomialRing<ModInteger> mpfac;
097
098
099    GenPolynomial<ModInteger> agen;
100
101
102    QuotientRing<ModInteger> fac;
103
104
105    GreatestCommonDivisorAbstract<Quotient<ModInteger>> ufd;
106
107
108    SquarefreeInfiniteFieldCharP<ModInteger> sqf;
109
110
111    GenPolynomialRing<Quotient<ModInteger>> dfac;
112
113
114    GenPolynomial<Quotient<ModInteger>> a;
115
116
117    GenPolynomial<Quotient<ModInteger>> b;
118
119
120    GenPolynomial<Quotient<ModInteger>> c;
121
122
123    GenPolynomial<Quotient<ModInteger>> d;
124
125
126    GenPolynomial<Quotient<ModInteger>> e;
127
128
129    GenPolynomialRing<Quotient<ModInteger>> cfac;
130
131
132    GenPolynomialRing<GenPolynomial<Quotient<ModInteger>>> rfac;
133
134
135    GenPolynomial<GenPolynomial<Quotient<ModInteger>>> ar;
136
137
138    GenPolynomial<GenPolynomial<Quotient<ModInteger>>> br;
139
140
141    GenPolynomial<GenPolynomial<Quotient<ModInteger>>> cr;
142
143
144    GenPolynomial<GenPolynomial<Quotient<ModInteger>>> dr;
145
146
147    GenPolynomial<GenPolynomial<Quotient<ModInteger>>> er;
148
149
150    @Override
151    protected void setUp() {
152        vars = ExpVector.STDVARS(rl);
153        cvars = ExpVector.STDVARS(rl - 1);
154        c1vars = new String[] { cvars[0] };
155        rvars = new String[] { vars[rl - 1] };
156
157        mfac = new ModIntegerRing(7);
158        alpha = new String[] { "u" };
159        mpfac = new GenPolynomialRing<ModInteger>(mfac, 1, to, alpha);
160        fac = new QuotientRing<ModInteger>(mpfac);
161
162        //ufd = new GreatestCommonDivisorSubres<Quotient<ModInteger>>();
163        //ufd = GCDFactory.<Quotient<ModInteger>> getImplementation(fac);
164        ufd = GCDFactory.<Quotient<ModInteger>> getProxy(fac);
165
166        sqf = new SquarefreeInfiniteFieldCharP<ModInteger>(fac);
167
168        SquarefreeAbstract<Quotient<ModInteger>> sqff = SquarefreeFactory.getImplementation(fac);
169        //System.out.println("sqf  = " + sqf);
170        //System.out.println("sqff = " + sqff);
171        assertEquals("sqf == sqff ", sqf.getClass(), sqff.getClass());
172
173        a = b = c = d = e = null;
174        ar = br = cr = dr = er = null;
175    }
176
177
178    @Override
179    protected void tearDown() {
180        a = b = c = d = e = null;
181        ar = br = cr = dr = er = null;
182        //ComputerThreads.terminate();
183    }
184
185
186    /**
187     * Test base squarefree.
188     * 
189     */
190    public void testBaseSquarefree() {
191        //System.out.println("\nbase:");
192
193        dfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, 1, to, rvars);
194
195        a = dfac.random(kl + 1, ll, el + 1, q);
196        b = dfac.random(kl + 1, ll, el + 1, q);
197        c = dfac.random(kl, ll, el, q);
198        //System.out.println("a  = " + a);
199        //System.out.println("b  = " + b);
200        //System.out.println("c  = " + c);
201
202        if (a.isZERO() || b.isZERO() || c.isZERO()) {
203            // skip for this turn
204            return;
205        }
206
207        // a a b b b c
208        d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
209        c = a.multiply(b).multiply(c);
210        //System.out.println("d  = " + d);
211        //System.out.println("c  = " + c);
212
213        c = sqf.baseSquarefreePart(c);
214        d = sqf.baseSquarefreePart(d);
215        //System.out.println("d  = " + d);
216        //System.out.println("c  = " + c);
217        assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
218        assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
219
220        e = PolyUtil.<Quotient<ModInteger>> basePseudoRemainder(d, c);
221        //System.out.println("e  = " + e);
222        assertTrue("squarefree(abc) | squarefree(aabbbc) " + e, e.isZERO());
223    }
224
225
226    /**
227     * Test base squarefree factors.
228     * 
229     */
230    public void testBaseSquarefreeFactors() {
231
232        dfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, 1, to, rvars);
233
234        a = dfac.random(kl + 1, ll, el + 2, q);
235        b = dfac.random(kl + 1, ll, el + 2, q);
236        c = dfac.random(kl, ll, el + 1, q);
237        //System.out.println("a  = " + a);
238        //System.out.println("b  = " + b);
239        //System.out.println("c  = " + c);
240
241        if (a.isZERO() || b.isZERO() || c.isZERO()) {
242            // skip for this turn
243            return;
244        }
245
246        // a a b b b c
247        d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
248        //System.out.println("d  = " + d);
249
250        SortedMap<GenPolynomial<Quotient<ModInteger>>, Long> sfactors;
251        sfactors = sqf.baseSquarefreeFactors(d);
252        //System.out.println("sfactors = " + sfactors);
253
254        assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
255    }
256
257
258    /**
259     * Test recursive squarefree.
260     * 
261     */
262    public void testRecursiveSquarefree() {
263        //System.out.println("\nrecursive:");
264
265        cfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, 2 - 1, to, c1vars);
266        rfac = new GenPolynomialRing<GenPolynomial<Quotient<ModInteger>>>(cfac, 1, to, rvars);
267
268        ar = rfac.random(kl, 3, 2, q);
269        br = rfac.random(kl, 3, 2, q);
270        cr = rfac.random(kl, ll, el, q);
271        //System.out.println("ar = " + ar);
272        //System.out.println("br = " + br);
273        //System.out.println("cr = " + cr);
274
275        if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
276            // skip for this turn
277            return;
278        }
279
280        dr = ar.multiply(ar).multiply(br).multiply(br);
281        cr = ar.multiply(br);
282        //System.out.println("dr  = " + dr);
283        //System.out.println("cr  = " + cr);
284
285        cr = sqf.recursiveUnivariateSquarefreePart(cr);
286        dr = sqf.recursiveUnivariateSquarefreePart(dr);
287        //System.out.println("dr  = " + dr);
288        //System.out.println("cr  = " + cr);
289        assertTrue("isSquarefree(cr) " + cr, sqf.isRecursiveSquarefree(cr));
290        assertTrue("isSquarefree(dr) " + dr, sqf.isRecursiveSquarefree(dr));
291
292        er = PolyUtil.<Quotient<ModInteger>> recursivePseudoRemainder(dr, cr);
293        //System.out.println("er  = " + er);
294        assertTrue("squarefree(abc) | squarefree(aabbc) " + er, er.isZERO());
295    }
296
297
298    /**
299     * Test recursive squarefree factors.
300     * 
301     */
302    public void testRecursiveSquarefreeFactors() {
303
304        cfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, 2 - 1, to, c1vars);
305        rfac = new GenPolynomialRing<GenPolynomial<Quotient<ModInteger>>>(cfac, 1, to, rvars);
306
307        ar = rfac.random(kl, 3, 2, q);
308        br = rfac.random(kl, 3, 2, q);
309        cr = rfac.random(kl, 3, 2, q);
310        //System.out.println("ar = " + ar);
311        //System.out.println("br = " + br);
312        //System.out.println("cr = " + cr);
313
314        if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
315            // skip for this turn
316            return;
317        }
318
319        dr = ar.multiply(cr).multiply(br).multiply(br);
320        //System.out.println("dr  = " + dr);
321
322        SortedMap<GenPolynomial<GenPolynomial<Quotient<ModInteger>>>, Long> sfactors;
323        sfactors = sqf.recursiveUnivariateSquarefreeFactors(dr);
324        //System.out.println("sfactors = " + sfactors);
325
326        assertTrue("isFactorization(d,sfactors) ", sqf.isRecursiveFactorization(dr, sfactors));
327    }
328
329
330    /**
331     * Test squarefree.
332     * 
333     */
334    public void testSquarefree() {
335        //System.out.println("\nfull:");
336
337        dfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, rl, to, vars);
338
339        a = dfac.random(kl, ll, 2, q);
340        b = dfac.random(kl, ll - 1, 2, q);
341        c = dfac.random(kl, ll, 2, q);
342        //System.out.println("a  = " + a);
343        //System.out.println("b  = " + b);
344        //System.out.println("c  = " + c);
345
346        if (a.isZERO() || b.isZERO() || c.isZERO()) {
347            // skip for this turn
348            return;
349        }
350
351        d = a.multiply(a).multiply(b).multiply(b).multiply(c);
352        c = a.multiply(b).multiply(c);
353        //System.out.println("d  = " + d);
354        //System.out.println("c  = " + c);
355
356        c = sqf.squarefreePart(c);
357        d = sqf.squarefreePart(d);
358        //System.out.println("c  = " + c);
359        //System.out.println("d  = " + d);
360        assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
361        assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
362
363        e = PolyUtil.<Quotient<ModInteger>> basePseudoRemainder(d, c);
364        //System.out.println("e  = " + e);
365
366        assertTrue("squarefree(abc) | squarefree(aabbc) " + e, e.isZERO());
367    }
368
369
370    /**
371     * Test squarefree factors.
372     * 
373     */
374    public void testSquarefreeFactors() {
375
376        dfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, rl, to, vars);
377
378        a = dfac.random(kl, 3, 2, q);
379        b = dfac.random(kl, 2, 2, q);
380        c = dfac.random(kl, 3, 2, q);
381        //System.out.println("a  = " + a);
382        //System.out.println("b  = " + b);
383        //System.out.println("c  = " + c);
384
385        if (a.isZERO() || b.isZERO() || c.isZERO()) {
386            // skip for this turn
387            return;
388        }
389
390        d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
391        //System.out.println("d  = " + d);
392
393        SortedMap<GenPolynomial<Quotient<ModInteger>>, Long> sfactors;
394        sfactors = sqf.squarefreeFactors(d);
395        //System.out.println("sfactors = " + sfactors);
396
397        assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
398    }
399
400
401    /* ------------char-th root ------------------------- */
402
403
404    /**
405     * Test base squarefree with char-th root.
406     * 
407     */
408    public void testBaseSquarefreeCharRoot() {
409        //System.out.println("\nbase CharRoot:");
410
411        long p = fac.characteristic().longValue();
412
413        //dfac = new GenPolynomialRing<ModInteger>(fac,1,to,rvars);
414        dfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, 1, to, rvars);
415
416        a = dfac.random(kl + 1, ll + 1, el + 2, q).monic();
417        b = dfac.random(kl, ll + 1, el + 2, q).monic();
418        c = dfac.random(kl + 1, ll, el, q).monic();
419
420        if (a.isZERO() || b.isZERO() || c.isZERO() || a.isConstant() || b.isConstant()) {
421            // skip for this turn
422            return;
423        }
424        //System.out.println("a  = " + a);
425        //System.out.println("b  = " + b);
426        //System.out.println("c  = " + c);
427
428        // a a b^p c
429        d = a.multiply(a).multiply(Power.<GenPolynomial<Quotient<ModInteger>>> positivePower(b, p)).multiply(
430                c);
431        c = a.multiply(b).multiply(c);
432        //System.out.println("c  = " + c);
433        //System.out.println("d  = " + d);
434
435        c = sqf.baseSquarefreePart(c);
436        d = sqf.baseSquarefreePart(d);
437        //System.out.println("c  = " + c);
438        //System.out.println("d  = " + d);
439        assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
440        assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
441
442        e = PolyUtil.<Quotient<ModInteger>> basePseudoRemainder(d, c);
443        //System.out.println("e  = " + e);
444        assertTrue("squarefree(abc) | squarefree(aab^pc) " + e, e.isZERO());
445    }
446
447
448    /**
449     * Test base squarefree factors with char-th root.
450     * 
451     */
452    public void testBaseSquarefreeFactorsCharRoot() {
453
454        long p = fac.characteristic().longValue();
455
456        //dfac = new GenPolynomialRing<ModInteger>(fac,1,to,rvars);
457        dfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, 1, to, rvars);
458
459        a = dfac.random(kl, ll + 1, el + 3, q).monic();
460        b = dfac.random(kl, ll + 1, el + 3, q).monic();
461        c = dfac.random(kl, ll, el + 2, q).monic();
462
463        if (a.isZERO() || b.isZERO() || c.isZERO() || a.isConstant() || b.isConstant()) {
464            // skip for this turn
465            return;
466        }
467        //System.out.println("a  = " + a);
468        //System.out.println("b  = " + b);
469        //System.out.println("c  = " + c);
470
471        // a a b^p c
472        d = a.multiply(a).multiply(Power.<GenPolynomial<Quotient<ModInteger>>> positivePower(b, p)).multiply(
473                c);
474        //d = d.monic();
475        //System.out.println("d  = " + d);
476
477        SortedMap<GenPolynomial<Quotient<ModInteger>>, Long> sfactors;
478        sfactors = sqf.baseSquarefreeFactors(d);
479        //System.out.println("sfactors = " + sfactors);
480
481        assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
482    }
483
484
485    /**
486     * Test recursive squarefree with char-th root.
487     * 
488     */
489    public void testRecursiveSquarefreeCharRoot() {
490        //System.out.println("\nrecursive CharRoot:");
491
492        long p = fac.characteristic().longValue();
493
494        cfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, 2 - 1, to, c1vars);
495        rfac = new GenPolynomialRing<GenPolynomial<Quotient<ModInteger>>>(cfac, 1, to, rvars);
496
497        ar = rfac.random(kl, 3, 2 + 1, q);
498        br = rfac.random(kl, 3, 2, q);
499        cr = rfac.random(kl, ll, el, q);
500
501        if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
502            // skip for this turn
503            return;
504        }
505        ar = PolyUtil.<Quotient<ModInteger>> monic(ar);
506        br = PolyUtil.<Quotient<ModInteger>> monic(br);
507        cr = PolyUtil.<Quotient<ModInteger>> monic(cr);
508        //System.out.println("ar = " + ar);
509        //System.out.println("br = " + br);
510        //System.out.println("cr = " + cr);
511
512        // a b^p c
513        dr = ar.multiply(Power.<GenPolynomial<GenPolynomial<Quotient<ModInteger>>>> positivePower(br, p)).multiply(cr);
514        cr = ar.multiply(br).multiply(cr);
515        //System.out.println("cr  = " + cr);
516        //System.out.println("dr  = " + dr);
517
518        cr = sqf.recursiveUnivariateSquarefreePart(cr);
519        dr = sqf.recursiveUnivariateSquarefreePart(dr);
520        //System.out.println("cr  = " + cr);
521        //System.out.println("dr  = " + dr);
522        assertTrue("isSquarefree(cr) " + cr, sqf.isRecursiveSquarefree(cr));
523        assertTrue("isSquarefree(dr) " + dr, sqf.isRecursiveSquarefree(dr));
524
525        er = PolyUtil.<Quotient<ModInteger>> recursivePseudoRemainder(dr, cr);
526        //System.out.println("er  = " + er);
527        assertTrue("squarefree(abc) | squarefree(aabbc) " + er, er.isZERO());
528    }
529
530
531    /**
532     * Test recursive squarefree factors with char-th root.
533     * 
534     */
535    public void testRecursiveSquarefreeFactorsCharRoot() {
536
537        long p = fac.characteristic().longValue();
538
539        cfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, 2 - 1, to, c1vars);
540        rfac = new GenPolynomialRing<GenPolynomial<Quotient<ModInteger>>>(cfac, 1, to, rvars);
541
542        ar = rfac.random(kl, 3, 2 + 1, q);
543        br = rfac.random(kl, 3, 2, q);
544        cr = rfac.random(kl, 3, 2, q);
545
546        if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
547            // skip for this turn
548            return;
549        }
550        ar = PolyUtil.<Quotient<ModInteger>> monic(ar);
551        br = PolyUtil.<Quotient<ModInteger>> monic(br);
552        cr = PolyUtil.<Quotient<ModInteger>> monic(cr);
553        //System.out.println("ar = " + ar);
554        //System.out.println("br = " + br);
555        //System.out.println("cr = " + cr);
556
557        // a b^p c
558        dr = ar.multiply(Power.<GenPolynomial<GenPolynomial<Quotient<ModInteger>>>> positivePower(br, p)).multiply(cr);
559        //System.out.println("dr  = " + dr);
560
561        SortedMap<GenPolynomial<GenPolynomial<Quotient<ModInteger>>>, Long> sfactors;
562        sfactors = sqf.recursiveUnivariateSquarefreeFactors(dr);
563        //System.out.println("sfactors = " + sfactors);
564
565        assertTrue("isFactorization(d,sfactors) ", sqf.isRecursiveFactorization(dr, sfactors));
566    }
567
568
569    /**
570     * Test squarefree with char-th root.
571     * 
572     */
573    public void testSquarefreeCharRoot() {
574        //System.out.println("\nfull CharRoot:");
575
576        long p = fac.characteristic().longValue();
577
578        dfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, rl, to, vars);
579
580        a = dfac.random(kl, ll, 3, q);
581        b = dfac.random(kl, 3, 2, q);
582        c = dfac.random(kl, ll, 3, q);
583
584        if (a.isZERO() || b.isZERO() || c.isZERO() || b.isConstant()) {
585            // skip for this turn
586            return;
587        }
588        //System.out.println("a  = " + a);
589        //System.out.println("b  = " + b);
590        //System.out.println("c  = " + c);
591
592        // a a b^p c
593        d = a.multiply(a).multiply(Power.<GenPolynomial<Quotient<ModInteger>>> positivePower(b, p)).multiply(c);
594        c = a.multiply(b).multiply(c);
595        //System.out.println("c  = " + c);
596        //System.out.println("d  = " + d);
597
598        c = sqf.squarefreePart(c);
599        d = sqf.squarefreePart(d);
600        //System.out.println("c  = " + c);
601        //System.out.println("d  = " + d);
602        assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
603        assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
604
605        e = PolyUtil.<Quotient<ModInteger>> basePseudoRemainder(d, c);
606        //System.out.println("e  = " + e);
607        assertTrue("squarefree(abc) | squarefree(aab^pc) " + e, e.isZERO());
608    }
609
610
611    /**
612     * Test squarefree factors with char-th root.
613     * 
614     */
615    public void testSquarefreeFactorsCharRoot() {
616
617        long p = fac.characteristic().longValue();
618
619        dfac = new GenPolynomialRing<Quotient<ModInteger>>(fac, rl, to, vars);
620
621        a = dfac.random(kl, ll, 3, q);
622        b = dfac.random(kl, 3, 2, q);
623        c = dfac.random(kl, ll, 3, q);
624
625        if (a.isZERO() || b.isZERO() || c.isZERO() || b.isConstant()) {
626            // skip for this turn
627            return;
628        }
629        //System.out.println("a  = " + a);
630        //System.out.println("b  = " + b);
631        //System.out.println("c  = " + c);
632
633        // a a b^p c
634        d = a.multiply(a).multiply(Power.<GenPolynomial<Quotient<ModInteger>>> positivePower(b, p)).multiply(c);
635        //System.out.println("d  = " + d);
636
637        SortedMap<GenPolynomial<Quotient<ModInteger>>, Long> sfactors;
638        sfactors = sqf.squarefreeFactors(d);
639        //System.out.println("sfactors = " + sfactors);
640
641        assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
642    }
643
644}