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