Source code

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