Source code

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