001/*
002 * $Id: SquarefreeModTest.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 SquarefreeModTest 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>SquarefreeModTest</CODE> object.
045     * @param name String.
046     */
047    public SquarefreeModTest(String name) {
048        super(name);
049    }
050
051
052    /**
053     */
054    public static Test suite() {
055        TestSuite suite = new TestSuite(SquarefreeModTest.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 = 3;
067
068
069    int ll = 4;
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 fac;
091
092
093    GreatestCommonDivisorAbstract<ModInteger> ufd;
094
095
096    SquarefreeFiniteFieldCharP<ModInteger> sqf;
097
098
099    GenPolynomialRing<ModInteger> dfac;
100
101
102    GenPolynomial<ModInteger> a;
103
104
105    GenPolynomial<ModInteger> b;
106
107
108    GenPolynomial<ModInteger> c;
109
110
111    GenPolynomial<ModInteger> d;
112
113
114    GenPolynomial<ModInteger> e;
115
116
117    GenPolynomialRing<ModInteger> cfac;
118
119
120    GenPolynomialRing<GenPolynomial<ModInteger>> rfac;
121
122
123    GenPolynomial<GenPolynomial<ModInteger>> ar;
124
125
126    GenPolynomial<GenPolynomial<ModInteger>> br;
127
128
129    GenPolynomial<GenPolynomial<ModInteger>> cr;
130
131
132    GenPolynomial<GenPolynomial<ModInteger>> dr;
133
134
135    GenPolynomial<GenPolynomial<ModInteger>> er;
136
137
138    @Override
139    protected void setUp() {
140        vars = ExpVector.STDVARS(rl);
141        cvars = ExpVector.STDVARS(rl - 1);
142        c1vars = new String[] { cvars[0] };
143        rvars = new String[] { vars[rl - 1] };
144
145        fac = new ModIntegerRing(11);
146        //ufd = new GreatestCommonDivisorSubres<ModInteger>();
147        //ufd = GCDFactory.<ModInteger> getImplementation(fac);
148        ufd = GCDFactory.getProxy(fac);
149        sqf = new SquarefreeFiniteFieldCharP<ModInteger>(fac);
150
151        a = b = c = d = e = null;
152        ar = br = cr = dr = er = null;
153    }
154
155
156    @Override
157    protected void tearDown() {
158        a = b = c = d = e = null;
159        ar = br = cr = dr = er = null;
160        //ComputerThreads.terminate();
161    }
162
163
164    /**
165     * Test base squarefree.
166     * 
167     */
168    public void testBaseSquarefree() {
169        //System.out.println("\nbase:");
170
171        dfac = new GenPolynomialRing<ModInteger>(fac, 1, to, rvars);
172
173        a = dfac.random(kl, ll, el + 2, q);
174        b = dfac.random(kl, ll, el + 2, q);
175        c = dfac.random(kl, ll, el, q);
176        //System.out.println("a  = " + a);
177        //System.out.println("b  = " + b);
178        //System.out.println("c  = " + c);
179
180        if (a.isZERO() || b.isZERO() || c.isZERO()) {
181            // skip for this turn
182            return;
183        }
184
185        // a a b b b c
186        d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
187        c = a.multiply(b).multiply(c);
188        //System.out.println("c  = " + c);
189        //System.out.println("d  = " + d);
190
191        c = sqf.baseSquarefreePart(c);
192        d = sqf.baseSquarefreePart(d);
193        //System.out.println("c  = " + c);
194        //System.out.println("d  = " + d);
195        assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
196        assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
197
198        e = PolyUtil.<ModInteger> basePseudoRemainder(d, c);
199        //System.out.println("e  = " + e);
200        assertTrue("squarefree(abc) | squarefree(aabbbc) " + e, e.isZERO());
201    }
202
203
204    /**
205     * Test base squarefree factors.
206     * 
207     */
208    public void testBaseSquarefreeFactors() {
209
210        dfac = new GenPolynomialRing<ModInteger>(fac, 1, to, rvars);
211
212        a = dfac.random(kl, ll, el + 3, q);
213        b = dfac.random(kl, ll, el + 3, q);
214        c = dfac.random(kl, ll, el + 2, q);
215        //System.out.println("a  = " + a);
216        //System.out.println("b  = " + b);
217        //System.out.println("c  = " + c);
218
219        if (a.isZERO() || b.isZERO() || c.isZERO()) {
220            // skip for this turn
221            return;
222        }
223
224        // a a b b b c
225        d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
226        //System.out.println("d  = " + d);
227
228        SortedMap<GenPolynomial<ModInteger>, Long> sfactors;
229        sfactors = sqf.baseSquarefreeFactors(d);
230        //System.out.println("sfactors = " + sfactors);
231        assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
232    }
233
234
235    /**
236     * Test recursive squarefree.
237     * 
238     */
239    public void testRecursiveSquarefree() {
240        //System.out.println("\nrecursive:");
241
242        cfac = new GenPolynomialRing<ModInteger>(fac, 2 - 1, to, c1vars);
243        rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to, rvars);
244
245        ar = rfac.random(kl, ll, el, q);
246        br = rfac.random(kl, ll, el, q);
247        cr = rfac.random(kl, ll, el, q);
248        //System.out.println("ar = " + ar);
249        //System.out.println("br = " + br);
250        //System.out.println("cr = " + cr);
251
252        if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
253            // skip for this turn
254            return;
255        }
256
257        dr = ar.multiply(ar).multiply(br).multiply(br);
258        cr = ar.multiply(br);
259        //System.out.println("cr  = " + cr);
260        //System.out.println("dr  = " + dr);
261
262        cr = sqf.recursiveUnivariateSquarefreePart(cr);
263        dr = sqf.recursiveUnivariateSquarefreePart(dr);
264        //System.out.println("cr  = " + cr);
265        //System.out.println("dr  = " + dr);
266        assertTrue("isSquarefree(cr) " + cr, sqf.isRecursiveSquarefree(cr));
267        assertTrue("isSquarefree(dr) " + dr, sqf.isRecursiveSquarefree(dr));
268
269        er = PolyUtil.<ModInteger> recursivePseudoRemainder(dr, cr);
270        //System.out.println("er  = " + er);
271        assertTrue("squarefree(abc) | squarefree(aabbc) " + er, er.isZERO());
272    }
273
274
275    /**
276     * Test recursive squarefree factors.
277     * 
278     */
279    public void testRecursiveSquarefreeFactors() {
280
281        cfac = new GenPolynomialRing<ModInteger>(fac, 2 - 1, to, c1vars);
282        rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to, rvars);
283
284        ar = rfac.random(kl, 3, 2, q);
285        br = rfac.random(kl, 3, 2, q);
286        cr = rfac.random(kl, 3, 2, q);
287        //System.out.println("ar = " + ar);
288        //System.out.println("br = " + br);
289        //System.out.println("cr = " + cr);
290
291        if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
292            // skip for this turn
293            return;
294        }
295
296        dr = ar.multiply(cr).multiply(br).multiply(br);
297        //System.out.println("dr  = " + dr);
298
299        SortedMap<GenPolynomial<GenPolynomial<ModInteger>>, Long> sfactors;
300        sfactors = sqf.recursiveUnivariateSquarefreeFactors(dr);
301        //System.out.println("sfactors = " + sfactors);
302        assertTrue("isFactorization(d,sfactors) ", sqf.isRecursiveFactorization(dr, sfactors));
303    }
304
305
306    /**
307     * Test squarefree.
308     * 
309     */
310    public void testSquarefree() {
311        //System.out.println("\nfull:");
312
313        dfac = new GenPolynomialRing<ModInteger>(fac, rl, to, vars);
314
315        a = dfac.random(kl, ll, 2, q);
316        b = dfac.random(kl, ll, 2, q);
317        c = dfac.random(kl, ll, 2, q);
318        //System.out.println("a  = " + a);
319        //System.out.println("b  = " + b);
320        //System.out.println("c  = " + c);
321
322        if (a.isZERO() || b.isZERO() || c.isZERO()) {
323            // skip for this turn
324            return;
325        }
326
327        d = a.multiply(a).multiply(b).multiply(b).multiply(c);
328        c = a.multiply(b).multiply(c);
329        //System.out.println("c  = " + c);
330        //System.out.println("d  = " + d);
331
332        c = sqf.squarefreePart(c);
333        d = sqf.squarefreePart(d);
334        //System.out.println("c  = " + c);
335        //System.out.println("d  = " + d);
336        assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
337        assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
338
339        e = PolyUtil.<ModInteger> basePseudoRemainder(d, c);
340        //System.out.println("e  = " + e);
341        assertTrue("squarefree(abc) | squarefree(aabbc) " + e, e.isZERO());
342    }
343
344
345    /**
346     * Test squarefree factors.
347     * 
348     */
349    public void testSquarefreeFactors() {
350
351        dfac = new GenPolynomialRing<ModInteger>(fac, rl, to, vars);
352
353        a = dfac.random(kl, 3, 2, q);
354        b = dfac.random(kl, 3, 2, q);
355        c = dfac.random(kl, 3, 2, q);
356        //System.out.println("a  = " + a);
357        //System.out.println("b  = " + b);
358        //System.out.println("c  = " + c);
359
360        if (a.isZERO() || b.isZERO() || c.isZERO()) {
361            // skip for this turn
362            return;
363        }
364
365        d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
366        //System.out.println("d  = " + d);
367
368        SortedMap<GenPolynomial<ModInteger>, Long> sfactors;
369        sfactors = sqf.squarefreeFactors(d);
370        //System.out.println("sfactors = " + sfactors);
371        assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
372    }
373
374
375    /* ------------char-th root ------------------------- */
376
377    /**
378     * Test base squarefree with char-th root.
379     * 
380     */
381    public void testBaseSquarefreeCharRoot() {
382        //System.out.println("\nbase CharRoot:");
383
384        long p = fac.characteristic().longValue();
385
386        dfac = new GenPolynomialRing<ModInteger>(fac, 1, to, rvars);
387
388        a = dfac.random(kl, ll + 2, el + 2, q);
389        b = dfac.random(kl, ll + 2, el + 2, q);
390        c = dfac.random(kl, ll, el, q);
391
392        if (a.isZERO() || b.isZERO() || c.isZERO() || a.isConstant() || b.isConstant()) {
393            // skip for this turn
394            return;
395        }
396        //System.out.println("a  = " + a);
397        //System.out.println("b  = " + b);
398        //System.out.println("c  = " + c);
399
400        // a a b^p c
401        d = a.multiply(a).multiply(Power.<GenPolynomial<ModInteger>> positivePower(b, p)).multiply(c);
402        c = a.multiply(b).multiply(c);
403        //System.out.println("c  = " + c);
404        //System.out.println("d  = " + d);
405
406        c = sqf.baseSquarefreePart(c);
407        d = sqf.baseSquarefreePart(d);
408        //System.out.println("c  = " + c);
409        //System.out.println("d  = " + d);
410        assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
411        assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
412
413        e = PolyUtil.<ModInteger> basePseudoRemainder(d, c);
414        //System.out.println("e  = " + e);
415        assertTrue("squarefree(abc) | squarefree(aab^pc) " + e, e.isZERO());
416    }
417
418
419    /**
420     * Test base squarefree factors with char-th root.
421     * 
422     */
423    public void testBaseSquarefreeFactorsCharRoot() {
424
425        long p = fac.characteristic().longValue();
426
427        dfac = new GenPolynomialRing<ModInteger>(fac, 1, to, rvars);
428
429        a = dfac.random(kl, ll + 2, el + 3, q);
430        b = dfac.random(kl, ll + 2, el + 3, q);
431        c = dfac.random(kl, ll, el + 2, q);
432
433        if (a.isZERO() || b.isZERO() || c.isZERO() || a.isConstant() || b.isConstant()) {
434            // skip for this turn
435            return;
436        }
437        //System.out.println("a  = " + a);
438        //System.out.println("b  = " + b);
439        //System.out.println("c  = " + c);
440
441        // a a b^p c
442        d = a.multiply(a).multiply(Power.<GenPolynomial<ModInteger>> positivePower(b, p)).multiply(c);
443        //System.out.println("d  = " + d);
444
445        SortedMap<GenPolynomial<ModInteger>, Long> sfactors;
446        sfactors = sqf.baseSquarefreeFactors(d);
447        //System.out.println("sfactors = " + sfactors);
448        assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
449    }
450
451
452    /**
453     * Test recursive squarefree with char-th root.
454     * 
455     */
456    public void testRecursiveSquarefreeCharRoot() {
457        //System.out.println("\nrecursive CharRoot:");
458
459        long p = fac.characteristic().longValue();
460
461        cfac = new GenPolynomialRing<ModInteger>(fac, 2 - 1, to, c1vars);
462        rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to, rvars);
463
464        ar = rfac.random(kl, ll, el + 1, q).monic();
465        br = rfac.random(kl, ll, el + 1, q).monic();
466        cr = rfac.random(kl, ll, el, q).monic();
467
468        if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
469            // skip for this turn
470            return;
471        }
472        //System.out.println("ar = " + ar);
473        //System.out.println("br = " + br);
474        //System.out.println("cr = " + cr);
475
476        // a a b^p 
477        dr = ar.multiply(ar).multiply(Power.<GenPolynomial<GenPolynomial<ModInteger>>> positivePower(br, p));
478        cr = ar.multiply(ar).multiply(br);
479        //System.out.println("cr  = " + cr);
480        //System.out.println("dr  = " + dr);
481
482        cr = sqf.recursiveUnivariateSquarefreePart(cr);
483        dr = sqf.recursiveUnivariateSquarefreePart(dr);
484        //System.out.println("cr  = " + cr);
485        //System.out.println("dr  = " + dr);
486        assertTrue("isSquarefree(cr) " + cr, sqf.isRecursiveSquarefree(cr));
487        assertTrue("isSquarefree(dr) " + dr, sqf.isRecursiveSquarefree(dr));
488
489        er = PolyUtil.<ModInteger> recursivePseudoRemainder(dr, cr);
490        //System.out.println("er  = " + er);
491        assertTrue("squarefree(abc) | squarefree(aabbc) " + er, er.isZERO());
492    }
493
494
495    /**
496     * Test recursive squarefree factors with char-th root.
497     * 
498     */
499    public void testRecursiveSquarefreeFactorsCharRoot() {
500
501        long p = fac.characteristic().longValue();
502
503        cfac = new GenPolynomialRing<ModInteger>(fac, 2 - 1, to, c1vars);
504        rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to, rvars);
505
506        ar = rfac.random(kl, 3, 2 + 1, q).monic();
507        br = rfac.random(kl, 3, 2 + 1, q).monic();
508        cr = rfac.random(kl, 3, 2, q).monic();
509
510        if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
511            // skip for this turn
512            return;
513        }
514        //System.out.println("ar = " + ar);
515        //System.out.println("br = " + br);
516        //System.out.println("cr = " + cr);
517
518        // a a b^p c
519        dr = ar.multiply(ar).multiply(Power.<GenPolynomial<GenPolynomial<ModInteger>>> positivePower(br, p)).multiply(cr);
520        //System.out.println("dr  = " + dr);
521
522        SortedMap<GenPolynomial<GenPolynomial<ModInteger>>, Long> sfactors;
523        sfactors = sqf.recursiveUnivariateSquarefreeFactors(dr);
524        //System.out.println("sfactors = " + sfactors);
525        assertTrue("isFactorization(d,sfactors) ", sqf.isRecursiveFactorization(dr, sfactors));
526    }
527
528
529    /**
530     * Test squarefree with char-th root.
531     * 
532     */
533    public void testSquarefreeCharRoot() {
534        //System.out.println("\nfull CharRoot:");
535
536        long p = fac.characteristic().longValue();
537
538        dfac = new GenPolynomialRing<ModInteger>(fac, rl, to, vars);
539
540        a = dfac.random(kl, ll, 3, q).monic();
541        b = dfac.random(kl, ll, 3, q).monic();
542        c = dfac.random(kl, ll, 3, q).monic();
543
544        if (a.isZERO() || b.isZERO() || c.isZERO()) {
545            // skip for this turn
546            return;
547        }
548        //System.out.println("a  = " + a);
549        //System.out.println("b  = " + b);
550        //System.out.println("c  = " + c);
551
552        // a a b^p c
553        d = a.multiply(a).multiply(Power.<GenPolynomial<ModInteger>> positivePower(b, p)).multiply(c);
554        c = a.multiply(b).multiply(c);
555        //System.out.println("c  = " + c);
556        //System.out.println("d  = " + d);
557
558        c = sqf.squarefreePart(c);
559        d = sqf.squarefreePart(d);
560        //System.out.println("c  = " + c);
561        //System.out.println("d  = " + d);
562        assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
563        assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
564
565        e = PolyUtil.<ModInteger> basePseudoRemainder(d, c);
566        //System.out.println("e  = " + e);
567        assertTrue("squarefree(abc) | squarefree(aab^pc) " + e, e.isZERO());
568    }
569
570
571    /**
572     * Test squarefree factors with char-th root.
573     * 
574     */
575    public void testSquarefreeFactorsCharRoot() {
576
577        long p = fac.characteristic().longValue();
578
579        dfac = new GenPolynomialRing<ModInteger>(fac, rl, to, vars);
580
581        a = dfac.random(kl, ll, 3, q).monic();
582        b = dfac.random(kl, ll, 3, q).monic();
583        c = dfac.random(kl, ll, 3, q).monic();
584
585        if (a.isZERO() || b.isZERO() || c.isZERO()) {
586            // skip for this turn
587            return;
588        }
589        //System.out.println("a  = " + a);
590        //System.out.println("b  = " + b);
591        //System.out.println("c  = " + c);
592
593        // a a b^p c
594        d = a.multiply(a).multiply(Power.<GenPolynomial<ModInteger>> positivePower(b, p)).multiply(c);
595        //System.out.println("d  = " + d);
596
597        SortedMap<GenPolynomial<ModInteger>, Long> sfactors;
598        sfactors = sqf.squarefreeFactors(d);
599        //System.out.println("sfactors = " + sfactors);
600        assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
601    }
602
603}