Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.gbufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import edu.jas.arith.BigInteger;
012import edu.jas.arith.BigRational;
013import edu.jas.arith.ModInteger;
014import edu.jas.arith.ModIntegerRing;
015import edu.jas.arith.PrimeList;
016import edu.jas.kern.ComputerThreads;
017import edu.jas.poly.GenPolynomial;
018import edu.jas.poly.GenPolynomialRing;
019import edu.jas.poly.TermOrder;
020import edu.jas.ufd.GCDProxy;
021import edu.jas.ufd.GreatestCommonDivisorAbstract;
022import edu.jas.ufd.GreatestCommonDivisorModEval;
023import edu.jas.ufd.GreatestCommonDivisorModular;
024import edu.jas.ufd.GreatestCommonDivisorSimple;
025import edu.jas.ufd.GreatestCommonDivisorSubres;
026
027import junit.framework.Test;
028import junit.framework.TestCase;
029import junit.framework.TestSuite;
030
031
032/**
033 * PolyGBUtil tests with JUnit.
034 * @author Heinz Kredel
035 */
036public class PolyGBUtilTest extends TestCase {
037
038
039    /**
040     * main.
041     */
042    public static void main(String[] args) {
043        junit.textui.TestRunner.run(suite());
044        ComputerThreads.terminate();
045    }
046
047
048    /**
049     * Constructs a <CODE>PolyUtilTest</CODE> object.
050     * @param name String.
051     */
052    public PolyGBUtilTest(String name) {
053        super(name);
054    }
055
056
057    /**
058     */
059    public static Test suite() {
060        TestSuite suite = new TestSuite(PolyGBUtilTest.class);
061        return suite;
062    }
063
064
065    //TermOrder to = new TermOrder(TermOrder.INVLEX);
066    TermOrder to = new TermOrder(TermOrder.IGRLEX);
067
068
069    int rl = 3;
070
071
072    int kl = 3;
073
074
075    int ll = 4;
076
077
078    int el = 3;
079
080
081    float q = 0.29f;
082
083
084    @Override
085    protected void setUp() {
086    }
087
088
089    @Override
090    protected void tearDown() {
091    }
092
093
094    /**
095     * Test resultant modular.
096     */
097    public void testResultantModular() {
098        GenPolynomialRing<ModInteger> dfac;
099        ModIntegerRing mi;
100
101        PrimeList primes = new PrimeList();
102        mi = new ModIntegerRing(primes.get(1)); // 17, 19, 23, 41, 163, 
103        dfac = new GenPolynomialRing<ModInteger>(mi, rl, to);
104        //System.out.println("dfac = " + dfac);
105
106        GreatestCommonDivisorAbstract<ModInteger> ufds = new GreatestCommonDivisorSimple<ModInteger>();
107        GreatestCommonDivisorAbstract<ModInteger> sres = new GreatestCommonDivisorSubres<ModInteger>();
108        GreatestCommonDivisorAbstract<ModInteger> ufdm = new GreatestCommonDivisorModEval<ModInteger>();
109        GenPolynomial<ModInteger> a, b, c, d, e;
110
111        for (int i = 0; i < 1; i++) {
112            a = dfac.random(kl, ll, el, q);
113            b = dfac.random(kl, ll + 2, el, q);
114            //a = dfac.parse("6 x0^4 - 17");
115            //b = dfac.parse("6 x1^2 - 7 x0^2 - 5 x1 - 14");
116            //a = dfac.parse("5 x1^4 * x2^4 + 2 x1^2 + x0^2");
117            //b = dfac.parse("5 x0^2 * x1^2 + 2 x2^2 + 5 x2 + 15");
118            //a = dfac.parse("x0^3 * x2^2 + 6 x0^4 + 6 x0 + 7");
119            //b = dfac.parse("7 x0^2 * x2^2 + 3 x2^2 + 4 x1^2 * x2 + 4 x2 + 4 x1^2 + x1 + 7");
120            //System.out.println("a = " + a);
121            //System.out.println("b = " + b);
122
123            c = ufds.resultant(a, b);
124            d = sres.resultant(a, b);
125            e = ufdm.resultant(a, b);
126
127            boolean t1 = PolyGBUtil.<ModInteger> isResultant(a, b, c);
128            //System.out.println("t1 = " + t1);
129            boolean t2 = PolyGBUtil.<ModInteger> isResultant(a, b, d);
130            //System.out.println("t2 = " + t2);
131            boolean t3 = PolyGBUtil.<ModInteger> isResultant(a, b, e);
132            //System.out.println("t3 = " + t3);
133
134            //System.out.println("c = " + c);
135            //System.out.println("d = " + d);
136            //System.out.println("e = " + e);
137
138            assertTrue("isResultant(a,b,c): " + c, t1);
139            assertTrue("isResultant(a,b,d): " + d, t2);
140            assertTrue("isResultant(a,b,e): " + e, t3);
141        }
142    }
143
144
145    /**
146     * Test resultant integer.
147     */
148    public void testResultantInteger() {
149        GenPolynomialRing<BigInteger> dfac;
150        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to);
151        //System.out.println("dfac = " + dfac);
152
153        GreatestCommonDivisorAbstract<BigInteger> ufds = new GreatestCommonDivisorSimple<BigInteger>();
154        GreatestCommonDivisorAbstract<BigInteger> sres = new GreatestCommonDivisorSubres<BigInteger>();
155        GreatestCommonDivisorAbstract<BigInteger> ufdm = new GreatestCommonDivisorModular<ModInteger>(); //true);
156        GenPolynomial<BigInteger> a, b, c, d, e;
157
158        for (int i = 0; i < 1; i++) {
159            a = dfac.random(kl, ll, el, q);
160            b = dfac.random(kl, ll + 2, el, q);
161            //a = dfac.parse("6 x0^4 - 17");
162            //b = dfac.parse("6 x1^2 - 7 x0^2 - 5 x1 - 14");
163            //System.out.println("a = " + a);
164            //System.out.println("b = " + b);
165
166            c = ufds.resultant(a, b);
167            d = sres.resultant(a, b);
168            e = ufdm.resultant(a, b);
169
170            boolean t1 = PolyGBUtil.<BigInteger> isResultant(a, b, c);
171            //System.out.println("t1 = " + t1);
172            boolean t2 = PolyGBUtil.<BigInteger> isResultant(a, b, d);
173            //System.out.println("t2 = " + t2);
174            boolean t3 = PolyGBUtil.<BigInteger> isResultant(a, b, e);
175            //System.out.println("t3 = " + t3);
176
177            //System.out.println("c = " + c);
178            //System.out.println("d = " + d);
179            //System.out.println("e = " + e);
180
181            assertTrue("isResultant(a,b,d): " + d, t2);
182            assertTrue("isResultant(a,b,e): " + e, t3);
183            assertTrue("isResultant(a,b,c): " + c, t1);
184        }
185    }
186
187
188    /**
189     * Test resultant modular parallel proxy.
190     */
191    public void testResultantModularParallel() {
192        GenPolynomialRing<ModInteger> dfac;
193        ModIntegerRing mi;
194
195        PrimeList primes = new PrimeList();
196        mi = new ModIntegerRing(primes.get(1)); // 17, 19, 23, 41, 163, 
197        dfac = new GenPolynomialRing<ModInteger>(mi, rl, to);
198        //System.out.println("dfac = " + dfac);
199
200        GreatestCommonDivisorAbstract<ModInteger> ufds = new GreatestCommonDivisorSimple<ModInteger>();
201        GreatestCommonDivisorAbstract<ModInteger> sres = new GreatestCommonDivisorSubres<ModInteger>();
202        GreatestCommonDivisorAbstract<ModInteger> ufdm = new GreatestCommonDivisorModEval<ModInteger>();
203
204        GreatestCommonDivisorAbstract<ModInteger> pufds = new GCDProxy<ModInteger>(sres, ufds);
205        GreatestCommonDivisorAbstract<ModInteger> pufdm = new GCDProxy<ModInteger>(ufdm, sres);
206
207        GenPolynomial<ModInteger> a, b, c, d;
208
209        for (int i = 0; i < 1; i++) {
210            a = dfac.random(kl, ll, el, q);
211            b = dfac.random(kl, ll + 2, el, q);
212            //System.out.println("a = " + a);
213            //System.out.println("b = " + b);
214
215            c = pufds.resultant(a, b);
216            d = pufdm.resultant(a, b);
217
218            boolean t1 = PolyGBUtil.<ModInteger> isResultant(a, b, c);
219            //System.out.println("t1 = " + t1);
220            boolean t2 = PolyGBUtil.<ModInteger> isResultant(a, b, d);
221            //System.out.println("t2 = " + t2);
222
223            //System.out.println("c = " + c);
224            //System.out.println("d = " + d);
225
226            assertTrue("isResultant(a,b,c): " + c, t1);
227            assertTrue("isResultant(a,b,d): " + d, t2);
228        }
229    }
230
231
232    /**
233     * Test resultant integer parallel proxy.
234     */
235    public void testResultantIntegerProxy() {
236        GenPolynomialRing<BigInteger> dfac;
237        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to);
238        //System.out.println("dfac = " + dfac);
239
240        GreatestCommonDivisorAbstract<BigInteger> ufds = new GreatestCommonDivisorSimple<BigInteger>();
241        GreatestCommonDivisorAbstract<BigInteger> sres = new GreatestCommonDivisorSubres<BigInteger>();
242        GreatestCommonDivisorAbstract<BigInteger> ufdm = new GreatestCommonDivisorModular<ModInteger>(); //true);
243
244        GreatestCommonDivisorAbstract<BigInteger> pufds = new GCDProxy<BigInteger>(sres, ufds);
245        GreatestCommonDivisorAbstract<BigInteger> pufdm = new GCDProxy<BigInteger>(ufdm, sres);
246
247        GenPolynomial<BigInteger> a, b, c, d;
248
249        for (int i = 0; i < 1; i++) {
250            a = dfac.random(kl, ll, el, q);
251            b = dfac.random(kl, ll + 1, el, q);
252            //System.out.println("a = " + a);
253            //System.out.println("b = " + b);
254
255            c = pufds.resultant(a, b);
256            d = pufdm.resultant(a, b);
257
258            boolean t1 = PolyGBUtil.<BigInteger> isResultant(a, b, c);
259            //System.out.println("t1 = " + t1);
260            boolean t2 = PolyGBUtil.<BigInteger> isResultant(a, b, d);
261            //System.out.println("t2 = " + t2);
262
263            //System.out.println("c = " + c);
264            //System.out.println("d = " + d);
265
266            assertTrue("isResultant(a,b,d): " + d, t2);
267            assertTrue("isResultant(a,b,c): " + c, t1);
268        }
269    }
270
271
272    /**
273     * Test coefficient base pseudo remainder.
274     */
275    public void testCoefficientBasePseudoRemainder() {
276        GenPolynomialRing<BigRational> dfac;
277        BigRational br = new BigRational();
278        to = new TermOrder(TermOrder.INVLEX);
279        //String[] vars = new String[] { "x1",  "x2", "x3" };
280        String[] vars = new String[] { "x1", "x2" };
281        dfac = new GenPolynomialRing<BigRational>(br, to, vars);
282        //System.out.println("dfac = " + dfac);
283        GenPolynomialRing<GenPolynomial<BigRational>> rfac = dfac.recursive(1);
284        //System.out.println("rfac = " + rfac);
285        GenPolynomialRing<BigRational> cfac = (GenPolynomialRing<BigRational>) rfac.coFac;
286        //System.out.println("cfac = " + cfac);
287        GenPolynomial<GenPolynomial<BigRational>> ar, cr, dr, er;
288        GenPolynomial<BigRational> b;
289
290        ar = rfac.random(kl, ll, el, q * 1.1f);
291        b = cfac.random(kl, ll + 2, el * 2, q);
292        //System.out.println("ar = " + ar);
293        //System.out.println("b  = " + b);
294
295        cr = PolyGBUtil.<BigRational> coefficientPseudoRemainderBase(ar, b);
296        //System.out.println("cr = " + cr);
297        assertTrue("deg(c) < deg(a): ", cr.degree(0) <= ar.degree(0) || ar.degree(0) == 0);
298        assertTrue("deg(lfcd(c)) < deg(b): ",
299                        cr.leadingBaseCoefficient().degree(0) < b.degree(0) || b.degree(0) == 0);
300
301        dr = ar.multiply(b);
302        //System.out.println("dr = " + dr);
303        cr = PolyGBUtil.<BigRational> coefficientPseudoRemainderBase(dr, b);
304        //System.out.println("cr = " + cr);
305        assertTrue("c == 0: ", cr.isZERO());
306
307        long s = ar.degree(0);
308        er = rfac.univariate(0, s + 1);
309        //System.out.println("er = " + er);
310        er = er.multiply(b.multiply(b));
311        er = er.sum(ar);
312        //System.out.println("er = " + er);
313        cr = PolyGBUtil.<BigRational> coefficientPseudoRemainderBase(er, b);
314        //System.out.println("cr = " + cr);
315        assertTrue("deg(c) < deg(a): ", cr.degree(0) < er.degree(0));
316    }
317
318
319    /**
320     * Test coefficient recursive pseudo remainder.
321     */
322    public void testCoefficientRecursivePseudoRemainder() {
323        GenPolynomialRing<BigRational> dfac;
324        BigRational br = new BigRational();
325        to = new TermOrder(TermOrder.INVLEX);
326        String[] vars = new String[] { "x1", "x2", "x3" };
327        //String[] vars = new String[] { "x1",  "x2" };
328        dfac = new GenPolynomialRing<BigRational>(br, to, vars);
329        //System.out.println("dfac = " + dfac);
330        GenPolynomialRing<GenPolynomial<BigRational>> r1fac = dfac.recursive(2);
331        //System.out.println("r1fac = " + r1fac);
332        GenPolynomialRing<GenPolynomial<GenPolynomial<BigRational>>> rfac = r1fac.recursive(1);
333        //System.out.println("rfac = " + rfac);
334        GenPolynomialRing<GenPolynomial<BigRational>> cfac = (GenPolynomialRing<GenPolynomial<BigRational>>) rfac.coFac;
335        //System.out.println("cfac = " + cfac);
336        GenPolynomial<GenPolynomial<GenPolynomial<BigRational>>> ar, cr, dr, er;
337        GenPolynomial<GenPolynomial<BigRational>> b;
338
339        ar = rfac.random(kl, ll, el, q);
340        b = cfac.random(kl, ll + 2, el, q);
341        //System.out.println("ar = " + ar);
342        //System.out.println("b  = " + b);
343
344        cr = PolyGBUtil.<BigRational> coefficientPseudoRemainder(ar, b);
345        //System.out.println("cr = " + cr);
346        assertTrue("deg(c) < deg(a): ", cr.degree(0) <= ar.degree(0) || ar.degree(0) == 0);
347        assertTrue("deg(lfcd(c)) < deg(b): ",
348                        cr.leadingBaseCoefficient().degree(0) < b.degree(0) || b.degree(0) == 0);
349
350        dr = ar.multiply(b);
351        //System.out.println("dr = " + dr);
352        cr = PolyGBUtil.<BigRational> coefficientPseudoRemainder(dr, b);
353        //System.out.println("cr = " + cr);
354        assertTrue("c == 0: ", cr.isZERO());
355
356        long s = ar.degree(0);
357        er = rfac.univariate(0, s + 1);
358        ////System.out.println("er = " + er);
359        er = er.multiply(b.multiply(cfac.fromInteger(100)));
360        er = er.sum(ar);
361        //System.out.println("er = " + er);
362        cr = PolyGBUtil.<BigRational> coefficientPseudoRemainder(er, b);
363        //System.out.println("cr = " + cr);
364        assertTrue("deg(c) < deg(a): ", cr.degree(0) < er.degree(0));
365    }
366
367
368    /**
369     * Test sub ring membership.
370     */
371    public void testSubRing() {
372        GenPolynomialRing<BigRational> dfac;
373        dfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, to);
374        //System.out.println("dfac = " + dfac);
375        GenPolynomial<BigRational> a, b, c, d;
376        a = dfac.random(kl, ll, el, q).abs();
377        b = dfac.random(kl, ll, el, q).abs();
378        d = a.multiply(b).sum(b);
379        List<GenPolynomial<BigRational>> sr = new ArrayList<GenPolynomial<BigRational>>(3);
380        sr.add(a);
381        sr.add(b);
382        //System.out.println("sr  = " + sr);
383        List<GenPolynomial<BigRational>> srg = PolyGBUtil.<BigRational> subRing(sr);
384        //System.out.println("srg = " + srg);
385        boolean t = PolyGBUtil.<BigRational> subRingMember(srg, d);
386        assertTrue("d in SR: ", t);
387
388        c = dfac.random(kl, ll, el + el, q * 1.5f).abs();
389        sr.add(c);
390        //System.out.println("sr  = " + sr);
391        d = a.multiply(b).sum(c);
392        t = PolyGBUtil.<BigRational> subRingAndMember(sr, d);
393        assertTrue("d in SR: ", t);
394    }
395
396
397    /**
398     * Test Chinese remainder theorem, random.
399     */
400    public void testCRTrandom() {
401        String[] vars = new String[] { "x", "y", "z" };
402        GenPolynomialRing<BigRational> dfac;
403        dfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, to, vars);
404        //System.out.println("dfac = " + dfac.toScript());
405        GenPolynomial<BigRational> a, b;
406        List<List<GenPolynomial<BigRational>>> F = new ArrayList<List<GenPolynomial<BigRational>>>(2);
407        List<GenPolynomial<BigRational>> F1 = new ArrayList<GenPolynomial<BigRational>>(2);
408        a = dfac.random(kl, ll, el, q).abs();
409        b = dfac.random(kl, ll, el, q).abs();
410        F1.add(a);
411        F1.add(b);
412        F.add(F1);
413        List<GenPolynomial<BigRational>> F2 = new ArrayList<GenPolynomial<BigRational>>(2);
414        a = dfac.random(kl, ll, el, q).abs();
415        b = dfac.random(kl, ll, el, q).abs();
416        F2.add(a);
417        F2.add(b);
418        F.add(F2);
419        //System.out.println("F  = " + F);
420        List<GenPolynomial<BigRational>> A = new ArrayList<GenPolynomial<BigRational>>(2);
421        a = dfac.random(kl / 2, ll, el, q).abs();
422        b = dfac.random(kl / 2, ll, el, q).abs();
423        A.add(a);
424        A.add(b);
425        //System.out.println("A  = " + A);
426        GenPolynomial<BigRational> h = PolyGBUtil.<BigRational> chineseRemainderTheorem(F, A);
427        //System.out.println("h  = " + h);
428        assertTrue("h == null or deg(h) >= 0: ", (h == null || h.degree() >= 0));
429        if (h == null) {
430            return;
431        }
432        assertTrue("isChineseRemainder " + h, PolyGBUtil.<BigRational> isChineseRemainder(F, A, h));
433    }
434
435
436    /**
437     * Test Chinese remainder theorem, random.
438     */
439    public void testCRTrandomInt() {
440        String[] vars = new String[] { "x", "y", "z" };
441        GenPolynomialRing<BigInteger> dfac;
442        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to, vars);
443        //System.out.println("dfac = " + dfac.toScript());
444        GenPolynomial<BigInteger> a, b;
445        List<List<GenPolynomial<BigInteger>>> F = new ArrayList<List<GenPolynomial<BigInteger>>>(2);
446        List<GenPolynomial<BigInteger>> F1 = new ArrayList<GenPolynomial<BigInteger>>(2);
447        a = dfac.random(kl, ll, el, q).abs();
448        b = dfac.random(kl, ll, el, q).abs();
449        F1.add(a);
450        F1.add(b);
451        F.add(F1);
452        List<GenPolynomial<BigInteger>> F2 = new ArrayList<GenPolynomial<BigInteger>>(2);
453        a = dfac.random(kl, ll, el, q).abs();
454        b = dfac.random(kl, ll, el, q).abs();
455        F2.add(a);
456        F2.add(b);
457        F.add(F2);
458        //System.out.println("F  = " + F);
459        List<GenPolynomial<BigInteger>> A = new ArrayList<GenPolynomial<BigInteger>>(2);
460        a = dfac.random(kl / 2, ll, el, q).abs();
461        b = dfac.random(kl / 2, ll, el, q).abs();
462        A.add(a);
463        A.add(b);
464        //System.out.println("A  = " + A);
465        GenPolynomial<BigInteger> h = PolyGBUtil.<BigInteger> chineseRemainderTheorem(F, A);
466        //System.out.println("h  = " + h);
467        if (h == null) {
468            return;
469        }
470        assertTrue("h == null or deg(h) >= 0: ", (h == null || h.degree() >= 0));
471        //boolean t = PolyGBUtil.<BigInteger> isChineseRemainder(F, A, h);
472        //System.out.println("t  = " + t);
473        //assertTrue("isChineseRemainder " + h, PolyGBUtil.<BigInteger> isChineseRemainder(F, A, h));
474    }
475
476
477    /**
478     * Test Chinese remainder theorem, interpolation.
479     */
480    public void testCRTLagrange() {
481        String[] vars = new String[] { "x", "y", "z" };
482        GenPolynomialRing<BigRational> dfac;
483        dfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, to, vars);
484        //System.out.println("dfac = " + dfac.toScript());
485        GenPolynomial<BigRational> a, b, c;
486        List<List<GenPolynomial<BigRational>>> F = new ArrayList<List<GenPolynomial<BigRational>>>(2);
487        List<GenPolynomial<BigRational>> F1 = new ArrayList<GenPolynomial<BigRational>>(3);
488        a = dfac.parse("(x-(2**16-15))");
489        F1.add(a);
490        b = dfac.parse("(y-13)");
491        F1.add(b);
492        c = dfac.parse("(z-169)");
493        F1.add(c);
494        F.add(F1);
495        List<GenPolynomial<BigRational>> F2 = new ArrayList<GenPolynomial<BigRational>>(3);
496        a = dfac.parse("(x-7)");
497        F2.add(a);
498        b = dfac.parse("(y-(2**32-5))");
499        F2.add(b);
500        c = dfac.parse("(z-101)");
501        F2.add(c);
502        F.add(F2);
503        List<GenPolynomial<BigRational>> F3 = new ArrayList<GenPolynomial<BigRational>>(3);
504        a = dfac.parse("(x-17)");
505        F3.add(a);
506        b = dfac.parse("(y-23)");
507        F3.add(b);
508        c = dfac.parse("(z-(2**15-19))");
509        F3.add(c);
510        F.add(F3);
511        //System.out.println("F  = " + F);
512        List<GenPolynomial<BigRational>> A = new ArrayList<GenPolynomial<BigRational>>(2);
513        a = dfac.parse("(4)");
514        b = dfac.parse("(11)");
515        c = dfac.parse("(103)");
516        A.add(a);
517        A.add(b);
518        A.add(c);
519        //System.out.println("A  = " + A);
520        GenPolynomial<BigRational> h = PolyGBUtil.<BigRational> chineseRemainderTheorem(F, A);
521        //System.out.println("h  = " + h);
522        assertTrue("h == null or deg(h) >= 0: ", (h == null || h.degree() >= 0));
523        if (h == null) {
524            return;
525        }
526        assertTrue("isChineseRemainder " + h, PolyGBUtil.<BigRational> isChineseRemainder(F, A, h));
527    }
528
529
530    /**
531     * Test Chinese remainder theorem, interpolation.
532     */
533    public void testCRTLagrangeInt() {
534        String[] vars = new String[] { "x", "y", "z" };
535        GenPolynomialRing<BigInteger> dfac;
536        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to, vars);
537        //System.out.println("dfac = " + dfac.toScript());
538        GenPolynomial<BigInteger> a, b, c;
539        List<List<GenPolynomial<BigInteger>>> F = new ArrayList<List<GenPolynomial<BigInteger>>>(2);
540        List<GenPolynomial<BigInteger>> F1 = new ArrayList<GenPolynomial<BigInteger>>(3);
541        a = dfac.parse("(x-(2**16-15))");
542        F1.add(a);
543        b = dfac.parse("(y-13)");
544        F1.add(b);
545        c = dfac.parse("(z-169)");
546        F1.add(c);
547        F.add(F1);
548        List<GenPolynomial<BigInteger>> F2 = new ArrayList<GenPolynomial<BigInteger>>(3);
549        a = dfac.parse("(x-7)");
550        F2.add(a);
551        b = dfac.parse("(y-(2**32-5))");
552        F2.add(b);
553        c = dfac.parse("(z-101)");
554        F2.add(c);
555        F.add(F2);
556        List<GenPolynomial<BigInteger>> F3 = new ArrayList<GenPolynomial<BigInteger>>(3);
557        a = dfac.parse("(x-17)");
558        F3.add(a);
559        b = dfac.parse("(y-23)");
560        F3.add(b);
561        c = dfac.parse("(z-(2**15-19))");
562        F3.add(c);
563        F.add(F3);
564        //System.out.println("F  = " + F);
565        List<GenPolynomial<BigInteger>> A = new ArrayList<GenPolynomial<BigInteger>>(2);
566        a = dfac.parse("(4)");
567        b = dfac.parse("(11)");
568        c = dfac.parse("(103)");
569        A.add(a);
570        A.add(b);
571        A.add(c);
572        //System.out.println("A  = " + A);
573        GenPolynomial<BigInteger> h = PolyGBUtil.<BigInteger> chineseRemainderTheorem(F, A);
574        //System.out.println("h  = " + h);
575        assertTrue("deg(h) > 0: ", h.degree() > 0);
576        //if (h == null) {
577        //    return;
578        //}
579        //boolean t = PolyGBUtil.<BigInteger> isChineseRemainder(F, A, h);
580        //System.out.println("t  = " + t);
581        //assertTrue("isChineseRemainder " + h, PolyGBUtil.<BigInteger> isChineseRemainder(F, A, h));
582    }
583
584
585    /**
586     * Test Chinese remainder theorem, interpolation.
587     */
588    public void testCRTnterpolation() {
589        String[] vars = new String[] { "x", "y", "z" };
590        BigRational cfac = new BigRational(1);
591        GenPolynomialRing<BigRational> dfac;
592        dfac = new GenPolynomialRing<BigRational>(cfac, rl, to, vars);
593        //System.out.println("dfac = " + dfac.toScript());
594        BigRational a, b, c;
595        List<List<BigRational>> F = new ArrayList<List<BigRational>>(3);
596        List<BigRational> F1 = new ArrayList<BigRational>(3);
597        a = cfac.parse("65521");
598        F1.add(a);
599        b = cfac.parse("13");
600        F1.add(b);
601        c = cfac.parse("169");
602        F1.add(c);
603        F.add(F1);
604        List<BigRational> F2 = new ArrayList<BigRational>(3);
605        a = cfac.parse("7");
606        F2.add(a);
607        b = cfac.parse("4294967291");
608        F2.add(b);
609        c = cfac.parse("101");
610        F2.add(c);
611        F.add(F2);
612        List<BigRational> F3 = new ArrayList<BigRational>(3);
613        a = cfac.parse("17");
614        F3.add(a);
615        b = cfac.parse("23");
616        F3.add(b);
617        c = cfac.parse("32749");
618        F3.add(c);
619        F.add(F3);
620        List<BigRational> F4 = new ArrayList<BigRational>(3);
621        a = cfac.parse("27");
622        F4.add(a);
623        b = cfac.parse("33");
624        F4.add(b);
625        c = cfac.parse("42749");
626        F4.add(c);
627        F.add(F4);
628        List<BigRational> F5 = new ArrayList<BigRational>(3);
629        a = cfac.parse("37");
630        F5.add(a);
631        b = cfac.parse("43");
632        F5.add(b);
633        c = cfac.parse("22749");
634        F5.add(c);
635        F.add(F5);
636        List<BigRational> F6 = new ArrayList<BigRational>(3);
637        a = cfac.parse("47");
638        F6.add(a);
639        b = cfac.parse("53");
640        F6.add(b);
641        c = cfac.parse("12749");
642        F6.add(c);
643        F.add(F6);
644        List<BigRational> F7 = new ArrayList<BigRational>(3);
645        a = cfac.parse("57");
646        F7.add(a);
647        b = cfac.parse("63");
648        F7.add(b);
649        c = cfac.parse("2749");
650        F7.add(c);
651        F.add(F7);
652        List<BigRational> F8 = new ArrayList<BigRational>(3);
653        a = cfac.parse("67");
654        F8.add(a);
655        b = cfac.parse("93");
656        F8.add(b);
657        c = cfac.parse("749");
658        F8.add(c);
659        F.add(F8);
660        List<BigRational> F9 = new ArrayList<BigRational>(3);
661        a = cfac.parse("77");
662        F9.add(a);
663        b = cfac.parse("103");
664        F9.add(b);
665        c = cfac.parse("49");
666        F9.add(c);
667        F.add(F9);
668        //System.out.println("F  = " + F);
669        List<BigRational> A = new ArrayList<BigRational>(3);
670        a = cfac.parse("4");
671        b = cfac.parse("11");
672        c = cfac.parse("103");
673        A.add(a);
674        A.add(b);
675        A.add(c);
676        c = cfac.parse("13");
677        A.add(c);
678        c = cfac.parse("23");
679        A.add(c);
680        c = cfac.parse("91");
681        A.add(c);
682        c = cfac.parse("81");
683        A.add(c);
684        c = cfac.parse("72");
685        A.add(c);
686        c = cfac.parse("102");
687        A.add(c);
688        //System.out.println("A  = " + A);
689        GenPolynomial<BigRational> h = PolyGBUtil.<BigRational> CRTInterpolation(dfac, F, A);
690        //System.out.println("h  = " + h);
691        assertTrue("deg(h) > 0: ", h.degree() > 0);
692        //if (h == null) {
693        //    return;
694        //}
695        //boolean t = PolyGBUtil.<BigRational> isChineseRemainder(F, A, h);
696        //System.out.println("t  = " + t);
697        //assertTrue("isChineseRemainder " + h, PolyGBUtil.<BigRational> isChineseRemainder(F, A, h));
698    }
699
700}