Source code

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