Source code

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