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