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