Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import edu.jas.arith.BigComplex;
012import edu.jas.arith.BigInteger;
013import edu.jas.arith.BigRational;
014import edu.jas.arith.ModInteger;
015import edu.jas.arith.ModIntegerRing;
016import edu.jas.arith.Product;
017import edu.jas.arith.ProductRing;
018
019import junit.framework.Test;
020import junit.framework.TestCase;
021import junit.framework.TestSuite;
022
023
024/**
025 * PolyUtil tests with JUnit.
026 * @author Heinz Kredel
027 */
028
029public class PolyUtilTest extends TestCase {
030
031
032    /**
033     * main.
034     */
035    public static void main(String[] args) {
036        junit.textui.TestRunner.run(suite());
037    }
038
039
040    /**
041     * Constructs a <CODE>PolyUtilTest</CODE> object.
042     * @param name String.
043     */
044    public PolyUtilTest(String name) {
045        super(name);
046    }
047
048
049    /**
050     */
051    public static Test suite() {
052        TestSuite suite = new TestSuite(PolyUtilTest.class);
053        return suite;
054    }
055
056
057    //private final static int bitlen = 100;
058
059    TermOrder to = new TermOrder(TermOrder.INVLEX);
060
061
062    GenPolynomialRing<BigInteger> dfac;
063
064
065    GenPolynomialRing<BigInteger> cfac;
066
067
068    GenPolynomialRing<GenPolynomial<BigInteger>> rfac;
069
070
071    BigInteger ai, bi, ci, di, ei;
072
073
074    GenPolynomial<BigInteger> a, b, c, d, e;
075
076
077    GenPolynomial<GenPolynomial<BigInteger>> ar, br, cr, dr, er;
078
079
080    int rl = 5;
081
082
083    int kl = 5;
084
085
086    int ll = 5;
087
088
089    int el = 3;
090
091
092    float q = 0.3f;
093
094
095    @Override
096    protected void setUp() {
097        a = b = c = d = e = null;
098        ai = bi = ci = di = ei = null;
099        ar = br = cr = dr = er = null;
100        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to);
101        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to);
102        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
103    }
104
105
106    @Override
107    protected void tearDown() {
108        a = b = c = d = e = null;
109        ai = bi = ci = di = ei = null;
110        ar = br = cr = dr = er = null;
111        dfac = null;
112        cfac = null;
113        rfac = null;
114    }
115
116
117    protected static java.math.BigInteger getPrime1() {
118        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
119        for (int i = 1; i < 60; i++) {
120            prime *= 2;
121        }
122        prime -= 93;
123        //prime = 37;
124        //System.out.println("p1 = " + prime);
125        return new java.math.BigInteger("" + prime);
126    }
127
128
129    protected static java.math.BigInteger getPrime2() {
130        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
131        for (int i = 1; i < 30; i++) {
132            prime *= 2;
133        }
134        prime -= 35;
135        //prime = 19;
136        //System.out.println("p1 = " + prime);
137        return new java.math.BigInteger("" + prime);
138    }
139
140
141    /**
142     * Test recursive -- distributive conversion.
143     */
144    public void testConversion() {
145        c = dfac.getONE();
146        assertTrue("length( c ) = 1", c.length() == 1);
147        assertTrue("isZERO( c )", !c.isZERO());
148        assertTrue("isONE( c )", c.isONE());
149
150        cr = PolyUtil.recursive(rfac, c);
151        a = PolyUtil.distribute(dfac, cr);
152        assertEquals("c == dist(rec(c))", c, a);
153
154        d = dfac.getZERO();
155        assertTrue("length( d ) = 0", d.length() == 0);
156        assertTrue("isZERO( d )", d.isZERO());
157        assertTrue("isONE( d )", !d.isONE());
158
159        dr = PolyUtil.recursive(rfac, d);
160        b = PolyUtil.distribute(dfac, dr);
161        assertEquals("d == dist(rec(d))", d, b);
162    }
163
164
165    /**
166     * Test recursive -- distributive ring conversion.
167     */
168    public void testConversionRing() {
169        GenPolynomialRing<GenPolynomial<BigInteger>> rf = dfac.recursive(1);
170        GenPolynomialRing<BigInteger> cf = (GenPolynomialRing<BigInteger>) rf.coFac;
171        assertEquals("rfac#var == rf#var ", rfac.nvar, rf.nvar);
172        assertEquals("rfac.coFac#var == rf.coFac#var ", cfac.nvar, cf.nvar);
173        assertEquals("rfac.coFac.coFac == rf.coFac.coFac ", cfac.coFac, cf.coFac);
174        // variable names not same in this test
175    }
176
177
178    /**
179     * Test random recursive -- distributive conversion.
180     */
181    public void testRandomConversion() {
182        for (int i = 0; i < 7; i++) {
183            c = dfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
184
185            assertTrue("length( c" + i + " ) <> 0", c.length() >= 0);
186            assertTrue(" not isZERO( c" + i + " )", !c.isZERO());
187            assertTrue(" not isONE( c" + i + " )", !c.isONE());
188
189            cr = PolyUtil.recursive(rfac, c);
190            a = PolyUtil.distribute(dfac, cr);
191            //System.out.println("c   = " + c);
192            //System.out.println("cr  = " + cr);
193            //System.out.println("crd = " + a);
194
195            assertEquals("c == dist(rec(c))", c, a);
196        }
197    }
198
199
200    /**
201     * Test random rational -- integer conversion.
202     */
203    @SuppressWarnings("unchecked")
204    public void testRationalConversion() {
205        GenPolynomialRing<BigRational> rfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, to);
206
207        GenPolynomial<BigRational> ar;
208        GenPolynomial<BigRational> br;
209
210        for (int i = 0; i < 3; i++) {
211            c = dfac.random(kl * (i + 9), ll * (i + 3), el + i, q).abs();
212            //c = c.multiply( new BigInteger(99) ); // fails, since not primitive
213            //c = GreatestCommonDivisor.primitivePart(c);
214
215            assertTrue("length( c" + i + " ) <> 0", c.length() >= 0);
216            assertTrue(" not isZERO( c" + i + " )", !c.isZERO());
217            assertTrue(" not isONE( c" + i + " )", !c.isONE());
218
219            ar = PolyUtil.<BigRational> fromIntegerCoefficients(rfac, c);
220            br = ar.monic();
221            a = PolyUtil.integerFromRationalCoefficients(dfac, br);
222            //System.out.println("c   = " + c);
223            //System.out.println("ar  = " + ar);
224            //System.out.println("br  = " + br);
225            //System.out.println("crd = " + a);
226            assertEquals("c == integer(rational(c))", c, a);
227
228            //ar = PolyUtil.<BigRational> fromIntegerCoefficients(rfac, c);
229            //br = ar.monic();
230            Object[] fa = PolyUtil.integerFromRationalCoefficientsFactor(dfac, br);
231            //System.out.println("c  = " + c);
232            //System.out.println("ar = " + ar);
233            //System.out.println("br = " + br);
234            //System.out.println("fa = " + Arrays.toString(fa));
235            java.math.BigInteger gcd = (java.math.BigInteger) fa[0];
236            java.math.BigInteger lcm = (java.math.BigInteger) fa[1];
237            a = (GenPolynomial<BigInteger>) fa[2];
238            //System.out.println("gcd = " + gcd);
239            //System.out.println("lcm = " + lcm);
240            //System.out.println("a = " + a);
241            assertEquals("c == integer(rational(c))", c, a);
242            assertEquals("gcd == 1", gcd, java.math.BigInteger.ONE);
243            assertEquals("lcm == lc(a)", lcm, a.leadingBaseCoefficient().val);
244        }
245    }
246
247
248    /**
249     * Test random modular -- integer conversion.
250     */
251    public void testModularConversion() {
252        ModIntegerRing pm = new ModIntegerRing(getPrime1());
253        GenPolynomialRing<ModInteger> mfac = new GenPolynomialRing<ModInteger>(pm, rl, to);
254
255        GenPolynomial<ModInteger> ar;
256
257        for (int i = 0; i < 3; i++) {
258            c = dfac.random(kl * (i + 2), ll * (i + 1), el + i, q).abs();
259            //c = c.multiply( new BigInteger(99) ); // fails, since not primitive
260            //c = GreatestCommonDivisor.primitivePart(c);
261
262            assertTrue("length( c" + i + " ) <> 0", c.length() >= 0);
263            assertTrue(" not isZERO( c" + i + " )", !c.isZERO());
264            assertTrue(" not isONE( c" + i + " )", !c.isONE());
265
266            ar = PolyUtil.<ModInteger> fromIntegerCoefficients(mfac, c);
267            a = PolyUtil.integerFromModularCoefficients(dfac, ar);
268            //System.out.println("c   = " + c);
269            //System.out.println("ar  = " + ar);
270            //System.out.println("crd = " + a);
271
272            assertEquals("c == integer(modular(c))", c, a);
273        }
274    }
275
276
277    /**
278     * Test chinese remainder.
279     */
280    public void testChineseRemainder() {
281        java.math.BigInteger p1 = getPrime1();
282        java.math.BigInteger p2 = getPrime2();
283        java.math.BigInteger p12 = p1.multiply(p2);
284
285        ModIntegerRing pm1 = new ModIntegerRing(p1);
286        GenPolynomialRing<ModInteger> mfac1 = new GenPolynomialRing<ModInteger>(pm1, rl, to);
287
288        ModIntegerRing pm2 = new ModIntegerRing(p2);
289        GenPolynomialRing<ModInteger> mfac2 = new GenPolynomialRing<ModInteger>(pm2, rl, to);
290
291        ModIntegerRing pm12 = new ModIntegerRing(p12);
292        GenPolynomialRing<ModInteger> mfac = new GenPolynomialRing<ModInteger>(pm12, rl, to);
293
294        ModInteger di = pm2.create(p1);
295        di = di.inverse();
296        //System.out.println("di = " + di);
297
298        GenPolynomial<ModInteger> am;
299        GenPolynomial<ModInteger> bm;
300        GenPolynomial<ModInteger> cm;
301
302        ExpVector degv, qdegv;
303
304        for (int i = 0; i < 3; i++) {
305            c = dfac.random((59 + 29) / 2, ll * (i + 1), el + i, q);
306            //c = c.multiply( new BigInteger(99) ); // fails, since not primitive
307            //c = GreatestCommonDivisor.primitivePart(c);
308            degv = c.degreeVector();
309            //System.out.println("degv  = " + degv);
310
311            assertTrue("length( c" + i + " ) <> 0", c.length() >= 0);
312            assertTrue(" not isZERO( c" + i + " )", !c.isZERO());
313            assertTrue(" not isONE( c" + i + " )", !c.isONE());
314
315            am = PolyUtil.<ModInteger> fromIntegerCoefficients(mfac1, c);
316            qdegv = am.degreeVector();
317            //System.out.println("qdegv  = " + qdegv);
318            if (!degv.equals(qdegv)) {
319                continue;
320            }
321            bm = PolyUtil.<ModInteger> fromIntegerCoefficients(mfac2, c);
322            qdegv = bm.degreeVector();
323            //System.out.println("qdegv  = " + qdegv);
324            if (!degv.equals(qdegv)) {
325                continue;
326            }
327
328            cm = PolyUtil.chineseRemainder(mfac, am, di, bm);
329            a = PolyUtil.integerFromModularCoefficients(dfac, cm);
330
331            //System.out.println("c  = " + c);
332            //System.out.println("am = " + am);
333            //System.out.println("bm = " + bm);
334            //System.out.println("cm = " + cm);
335            //System.out.println("a  = " + a);
336
337            assertEquals("cra(c mod p1,c mod p2) = c", c, a);
338        }
339    }
340
341
342    /**
343     * Test complex conversion.
344     */
345    public void testComplexConversion() {
346        BigRational rf = new BigRational(1);
347        GenPolynomialRing<BigRational> rfac = new GenPolynomialRing<BigRational>(rf, rl, to);
348
349        BigComplex cf = new BigComplex(1);
350        GenPolynomialRing<BigComplex> cfac = new GenPolynomialRing<BigComplex>(cf, rl, to);
351
352        BigComplex imag = BigComplex.I;
353
354        GenPolynomial<BigRational> rp;
355        GenPolynomial<BigRational> ip;
356        GenPolynomial<BigComplex> crp;
357        GenPolynomial<BigComplex> cip;
358        GenPolynomial<BigComplex> cp;
359        GenPolynomial<BigComplex> ap;
360
361        for (int i = 0; i < 3; i++) {
362            cp = cfac.random(kl + 2 * i, ll * (i + 1), el + i, q);
363
364            assertTrue("length( c" + i + " ) <> 0", cp.length() >= 0);
365            assertTrue(" not isZERO( c" + i + " )", !cp.isZERO());
366            assertTrue(" not isONE( c" + i + " )", !cp.isONE());
367
368            rp = PolyUtil.realPart(rfac, cp);
369            ip = PolyUtil.imaginaryPart(rfac, cp);
370
371            crp = PolyUtil.complexFromRational(cfac, rp);
372            cip = PolyUtil.complexFromRational(cfac, ip);
373
374            ap = crp.sum(cip.multiply(imag));
375
376            //System.out.println("cp = " + cp);
377            //System.out.println("rp = " + rp);
378            //System.out.println("ip = " + ip);
379            //System.out.println("crp = " + crp);
380            //System.out.println("cip = " + cip);
381            //System.out.println("ap  = " + ap);
382
383            assertEquals("re(c)+i*im(c) = c", cp, ap);
384        }
385    }
386
387
388    /**
389     * Test base pseudo division.
390     */
391    public void testBasePseudoDivision() {
392        String[] names = new String[] { "x" };
393        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), to, names);
394        GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1), dfac);
395        //System.out.println("\ndfac  = " + dfac);
396        //System.out.println("rdfac = " + rdfac);
397
398        a = dfac.random(kl, 2 * ll, el + 17, q);
399        //a = dfac.parse(" 3 x^5 + 44 ");
400        //b = a;
401        b = dfac.random(kl, 2 * ll, el + 3, q);
402        //a = a.multiply(b);
403        //a = a.sum(b);
404        //b = dfac.parse(" 2 x^2 + 40 ");
405        //System.out.println("a   = " + a);
406        //System.out.println("b   = " + b);
407
408        GenPolynomial<BigInteger>[] QR = PolyUtil.<BigInteger> basePseudoQuotientRemainder(a, b);
409        c = QR[1];
410        d = QR[0];
411        //System.out.println("q   = " + d);
412        //System.out.println("r   = " + c);
413
414        boolean t = PolyUtil.<BigInteger> isBasePseudoQuotientRemainder(a, b, d, c);
415        assertTrue("lc^n a = q b + r: " + c, t);
416
417        GenPolynomial<BigRational> ap = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, a);
418        GenPolynomial<BigRational> bp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, b);
419        GenPolynomial<BigRational> cp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, c);
420        GenPolynomial<BigRational> dp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, d);
421        //System.out.println("ap  = " + ap);
422        //System.out.println("bp  = " + bp);
423        //System.out.println("cp  = " + cp);
424        ////System.out.println("dp  = " + dp);
425        //System.out.println("dp  = " + dp.monic());
426
427        GenPolynomial<BigRational> qp = ap.divide(bp);
428        GenPolynomial<BigRational> rp = ap.remainder(bp);
429        //System.out.println("qp  = " + qp);
430        //System.out.println("qp  = " + qp.monic());
431        //System.out.println("rp  = " + rp);
432        GenPolynomial<BigRational> rhs = qp.multiply(bp).sum(rp);
433        //System.out.println("qp bp + rp  = " + rhs);
434
435        assertEquals("ap = qp bp + rp: ", ap, rhs);
436
437        assertEquals("cp = rp: ", rp.monic(), cp.monic());
438        assertEquals("dp = qp: ", qp.monic(), dp.monic()); // ??
439        //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
440    }
441
442
443    /**
444     * Test base sparse pseudo division.
445     */
446    public void testBasePseudoDivisionSparse() {
447        String[] names = new String[] { "x" };
448        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), to, names);
449        GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1), dfac);
450        //System.out.println("\ndfac  = " + dfac);
451        //System.out.println("rdfac = " + rdfac);
452
453        a = dfac.random(kl, 2 * ll, el + 17, q);
454        //a = dfac.parse(" 3 x^5 + 44 ");
455        //b = a;
456        b = dfac.random(kl, 2 * ll, el + 3, q);
457        //a = a.multiply(b);
458        //a = a.sum(b);
459        //b = dfac.parse(" 2 x^2 + 40 ");
460        //System.out.println("a   = " + a);
461        //System.out.println("b   = " + b);
462
463        d = PolyUtil.<BigInteger> basePseudoDivide(a, b);
464        //System.out.println("q   = " + d);
465        c = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, b);
466        //System.out.println("r   = " + c);
467
468        boolean t = PolyUtil.<BigInteger> isBasePseudoQuotientRemainder(a, b, d, c);
469        assertTrue("lc^n a = q b + r: " + c, t);
470
471        GenPolynomial<BigRational> ap = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, a);
472        GenPolynomial<BigRational> bp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, b);
473        GenPolynomial<BigRational> cp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, c);
474        GenPolynomial<BigRational> dp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, d);
475        //System.out.println("ap  = " + ap);
476        //System.out.println("bp  = " + bp);
477        //System.out.println("cp  = " + cp);
478        ////System.out.println("dp  = " + dp);
479        //System.out.println("dp  = " + dp.monic());
480
481        GenPolynomial<BigRational> qp = ap.divide(bp);
482        GenPolynomial<BigRational> rp = ap.remainder(bp);
483        //System.out.println("qp  = " + qp);
484        //System.out.println("qp  = " + qp.monic());
485        //System.out.println("rp  = " + rp);
486        GenPolynomial<BigRational> rhs = qp.multiply(bp).sum(rp);
487        //System.out.println("qp bp + rp  = " + rhs);
488
489        assertEquals("ap = qp bp + rp: ", ap, rhs);
490
491        assertEquals("cp = rp: ", rp.monic(), cp.monic());
492        assertEquals("dp = qp: ", qp.monic(), dp.monic()); // ??
493        //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
494    }
495
496
497    /**
498     * Test base dense pseudo division.
499     */
500    public void testBasePseudoDivisionDense() {
501        String[] names = new String[] { "x" };
502        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), to, names);
503        GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1), dfac);
504        //System.out.println("\ndfac  = " + dfac);
505        //System.out.println("rdfac = " + rdfac);
506
507        a = dfac.random(kl, 2 * ll, el + 17, q);
508        //a = dfac.parse(" 3 x^5 + 44 ");
509        //b = a;
510        b = dfac.random(kl, 2 * ll, el + 3, q);
511        //a = a.multiply(b);
512        //a = a.sum(b);
513        //b = dfac.parse(" 2 x^2 + 40 ");
514        //System.out.println("a   = " + a);
515        //System.out.println("b   = " + b);
516
517        d = PolyUtil.<BigInteger> baseDensePseudoQuotient(a, b);
518        //System.out.println("q   = " + d);
519        c = PolyUtil.<BigInteger> baseDensePseudoRemainder(a, b);
520        //System.out.println("r   = " + c);
521
522        boolean t = PolyUtil.<BigInteger> isBasePseudoQuotientRemainder(a, b, d, c);
523        assertTrue("lc^n a = q b + r: " + c, t);
524
525        GenPolynomial<BigRational> ap = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, a);
526        GenPolynomial<BigRational> bp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, b);
527        GenPolynomial<BigRational> cp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, c);
528        GenPolynomial<BigRational> dp = PolyUtil.<BigRational> fromIntegerCoefficients(rdfac, d);
529        //System.out.println("ap  = " + ap);
530        //System.out.println("bp  = " + bp);
531        //System.out.println("cp  = " + cp);
532        ////System.out.println("dp  = " + dp);
533        //System.out.println("dp  = " + dp.monic());
534
535        GenPolynomial<BigRational> qp = ap.divide(bp);
536        GenPolynomial<BigRational> rp = ap.remainder(bp);
537        //System.out.println("qp  = " + qp);
538        //System.out.println("qp  = " + qp.monic());
539        //System.out.println("rp  = " + rp);
540        GenPolynomial<BigRational> rhs = qp.multiply(bp).sum(rp);
541        //System.out.println("qp bp + rp  = " + rhs);
542
543        assertEquals("ap = qp bp + rp: ", ap, rhs);
544
545        assertEquals("cp = rp: ", rp.monic(), cp.monic());
546        assertEquals("dp = qp: ", qp.monic(), dp.monic()); // ??
547        //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) );
548    }
549
550
551    /**
552     * Test recursive pseudo quotient and remainder.
553     * @see edu.jas.ufd.PolyUfdUtilTest#testRecursivePseudoDivisionSparse
554     */
555    public void testRecursivePseudoDivision() {
556    }
557
558
559    /**
560     * Test evaluate main recursive.
561     */
562    public void testEvalMainRecursive() {
563        ai = (new BigInteger()).random(kl);
564        //System.out.println("ai  = " + ai);
565
566        ar = rfac.getZERO();
567        //System.out.println("ar  = " + ar);
568
569        a = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, ar, ai);
570        //System.out.println("a   = " + a);
571
572        assertTrue("isZERO( a )", a.isZERO());
573
574        ar = rfac.getONE();
575        //System.out.println("ar  = " + ar);
576
577        a = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, ar, ai);
578        //System.out.println("a   = " + a);
579
580        assertTrue("isONE( a )", a.isONE());
581
582
583        //ar = rfac.getONE();
584        ar = rfac.random(kl, ll, el, q);
585        //System.out.println("ar  = " + ar);
586        //br = rfac.getONE();
587        br = rfac.random(kl, ll, el, q);
588        //System.out.println("br  = " + br);
589
590        cr = br.sum(ar);
591        //System.out.println("cr  = " + cr);
592
593        a = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, ar, ai);
594        b = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, br, ai);
595        c = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, cr, ai);
596        //System.out.println("a   = " + a);
597        //System.out.println("b   = " + b);
598        //System.out.println("c   = " + c);
599
600        d = a.sum(b);
601        //System.out.println("d   = " + d);
602
603        assertEquals("eval(a+b) == eval(a) + eval(b)", c, d);
604
605
606        cr = br.multiply(ar);
607        //System.out.println("cr  = " + cr);
608
609        a = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, ar, ai);
610        b = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, br, ai);
611        c = PolyUtil.<BigInteger> evaluateMainRecursive(cfac, cr, ai);
612        //System.out.println("a   = " + a);
613        //System.out.println("b   = " + b);
614        //System.out.println("c   = " + c);
615
616        d = a.multiply(b);
617        //System.out.println("d   = " + d);
618
619        assertEquals("eval(a*b) == eval(a) * eval(b)", c, d);
620    }
621
622
623    /**
624     * Test evaluate main.
625     */
626    public void testEvalMain() {
627        ei = (new BigInteger()).random(kl);
628        //System.out.println("ei  = " + ei);
629
630        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
631        //System.out.println("cfac  = " + cfac);
632
633        a = cfac.getZERO();
634        //System.out.println("a  = " + a);
635
636        ai = PolyUtil.<BigInteger> evaluateMain(ei, a, ei);
637        //System.out.println("ai   = " + ai);
638
639        assertTrue("isZERO( ai )", ai.isZERO());
640
641        a = cfac.getONE();
642        //System.out.println("a  = " + a);
643
644        ai = PolyUtil.<BigInteger> evaluateMain(ei, a, ei);
645        //System.out.println("ai   = " + ai);
646
647        assertTrue("isONE( ai )", ai.isONE());
648
649        //a = cfac.getONE();
650        a = cfac.random(kl, ll, el, q);
651        //System.out.println("a  = " + a);
652        //b = cfac.getONE();
653        b = cfac.random(kl, ll, el, q);
654        //System.out.println("b  = " + b);
655
656        c = b.sum(a);
657        //System.out.println("c  = " + c);
658
659        ai = PolyUtil.<BigInteger> evaluateMain(ei, a, ei);
660        bi = PolyUtil.<BigInteger> evaluateMain(ei, b, ei);
661        ci = PolyUtil.<BigInteger> evaluateMain(ei, c, ei);
662        //System.out.println("ai   = " + ai);
663        //System.out.println("bi   = " + bi);
664        //System.out.println("ci   = " + ci);
665
666        di = bi.sum(ai);
667        //System.out.println("di   = " + di);
668
669        assertEquals("eval(a+b) == eval(a) + eval(b)", ci, di);
670
671        c = b.multiply(a);
672        //System.out.println("c  = " + c);
673
674        ai = PolyUtil.<BigInteger> evaluateMain(ei, a, ei);
675        bi = PolyUtil.<BigInteger> evaluateMain(ei, b, ei);
676        ci = PolyUtil.<BigInteger> evaluateMain(ei, c, ei);
677        //System.out.println("ai   = " + ai);
678        //System.out.println("bi   = " + bi);
679        //System.out.println("ci   = " + ci);
680
681        di = bi.multiply(ai);
682        //System.out.println("di   = " + di);
683
684        assertEquals("eval(a*b) == eval(a) * eval(b)", ci, di);
685    }
686
687
688    /**
689     * Test evaluate first.
690     */
691    public void testEvalFirst() {
692        ei = (new BigInteger()).random(kl);
693        //System.out.println("ei  = " + ei);
694
695        GenPolynomial<BigInteger> ae, be, ce, de;
696
697        GenPolynomialRing<BigInteger> fac;
698        fac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to);
699        //System.out.println("fac  = " + fac);
700
701        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
702        //System.out.println("cfac  = " + cfac);
703
704        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to);
705        //System.out.println("dfac  = " + dfac);
706
707        a = fac.getZERO();
708        //System.out.println("a  = " + a);
709
710        ae = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, a, ei);
711        //System.out.println("ae   = " + ae);
712
713        assertTrue("isZERO( ae )", ae.isZERO());
714
715        a = fac.getONE();
716        //System.out.println("a  = " + a);
717
718        ae = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, a, ei);
719        //System.out.println("ae   = " + ae);
720
721        assertTrue("isONE( ae )", ae.isONE());
722
723        //a = fac.getONE();
724        a = fac.random(kl, ll, el, q);
725        //System.out.println("a  = " + a);
726        //b = fac.getONE();
727        b = fac.random(kl, ll, el, q);
728        //System.out.println("b  = " + b);
729
730        c = b.sum(a);
731        //System.out.println("c  = " + c);
732
733        ae = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, a, ei);
734        be = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, b, ei);
735        ce = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, c, ei);
736        //System.out.println("ae   = " + ae);
737        //System.out.println("be   = " + be);
738        //System.out.println("ce   = " + ce);
739
740        de = be.sum(ae);
741        //System.out.println("de   = " + de);
742
743        assertEquals("eval(a+b) == eval(a) + eval(b)", ce, de);
744
745        c = b.multiply(a);
746        //System.out.println("c  = " + c);
747
748        ae = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, a, ei);
749        be = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, b, ei);
750        ce = PolyUtil.<BigInteger> evaluateFirst(cfac, dfac, c, ei);
751        //System.out.println("ae   = " + ae);
752        //System.out.println("be   = " + be);
753        //System.out.println("ce   = " + ce);
754
755        de = be.multiply(ae);
756        //System.out.println("de   = " + de);
757
758        assertEquals("eval(a*b) == eval(a) * eval(b)", ce, de);
759    }
760
761
762    /**
763     * Test evaluate all.
764     */
765    public void testEvalAll() {
766        BigInteger cfac = new BigInteger();
767
768        List<BigInteger> Ev = new ArrayList<BigInteger>();
769        for (int i = 0; i < rl; i++) {
770            ei = cfac.random(kl);
771            Ev.add(ei);
772        }
773        //System.out.println("Ev  = " + Ev);
774
775        BigInteger ae, be, ce, de;
776
777        GenPolynomialRing<BigInteger> fac;
778        fac = new GenPolynomialRing<BigInteger>(cfac, rl, to);
779        //System.out.println("fac  = " + fac);
780
781        List<GenPolynomial<BigInteger>> list = new ArrayList<GenPolynomial<BigInteger>>();
782        List<BigInteger> evlist;
783
784        a = fac.getZERO();
785        //System.out.println("a  = " + a);
786        ae = PolyUtil.<BigInteger> evaluateAll(cfac, a, Ev);
787        //System.out.println("ae   = " + ae);
788        assertTrue("isZERO( ae )", ae.isZERO());
789
790        a = fac.getONE();
791        //System.out.println("a  = " + a);
792        ae = PolyUtil.<BigInteger> evaluateAll(cfac, a, Ev);
793        //System.out.println("ae   = " + ae);
794        assertTrue("isONE( ae )", ae.isONE());
795
796        //a = fac.getONE();
797        a = fac.random(kl, ll, el, q);
798        //System.out.println("a  = " + a);
799        //b = fac.getONE();
800        b = fac.random(kl, ll, el, q);
801        //System.out.println("b  = " + b);
802
803        c = b.sum(a);
804        //System.out.println("c  = " + c);
805        ae = PolyUtil.<BigInteger> evaluateAll(cfac, a, Ev);
806        be = PolyUtil.<BigInteger> evaluateAll(cfac, b, Ev);
807        ce = PolyUtil.<BigInteger> evaluateAll(cfac, c, Ev);
808        //System.out.println("ae   = " + ae);
809        //System.out.println("be   = " + be);
810        //System.out.println("ce   = " + ce);
811        de = be.sum(ae);
812        //System.out.println("de   = " + de);
813        assertEquals("eval(a+b) == eval(a) + eval(b)", ce, de);
814
815        list.add(a);
816        list.add(b);
817        list.add(c);
818        //System.out.println("list = " + list);
819        evlist = PolyUtil.<BigInteger> evaluateAll(cfac, list, Ev);
820        //System.out.println("evlist = " + evlist);
821        de = evlist.get(1).sum(evlist.get(0));
822        assertEquals("eval(a+b) == eval(a) + eval(b)", ce, de);
823
824        c = b.multiply(a);
825        //System.out.println("c  = " + c);
826        ce = PolyUtil.<BigInteger> evaluateAll(cfac, c, Ev);
827        //System.out.println("ae   = " + ae);
828        //System.out.println("be   = " + be);
829        //System.out.println("ce   = " + ce);
830        de = be.multiply(ae);
831        //System.out.println("de   = " + de);
832        assertEquals("eval(a*b) == eval(a) * eval(b)", ce, de);
833
834        list.clear();
835        list.add(a);
836        list.add(b);
837        list.add(c);
838        //System.out.println("list = " + list);
839        evlist = PolyUtil.<BigInteger> evaluateAll(cfac, list, Ev);
840        //System.out.println("evlist = " + evlist);
841        de = evlist.get(1).multiply(evlist.get(0));
842        assertEquals("eval(a*b) == eval(a) * eval(b)", ce, de);
843    }
844
845
846    /**
847     * Test interpolate univariate 1 polynomial.
848     */
849    public void testInterpolateUnivariateOne() {
850        ModInteger ai, bi, ci, di, ei, fi, gi, hi;
851        GenPolynomial<ModInteger> a;
852        GenPolynomialRing<ModInteger> cfac;
853        ModIntegerRing fac;
854        GenPolynomial<ModInteger> r;
855        GenPolynomial<ModInteger> Q;
856        GenPolynomial<ModInteger> Qp;
857
858        fac = new ModIntegerRing(19);
859        //System.out.println("fac.modul  = " + fac.getModul());
860        cfac = new GenPolynomialRing<ModInteger>(fac, 1, to);
861        //System.out.println("cfac  = " + cfac);
862
863        a = cfac.getONE();
864        //System.out.println("a  = " + a);
865
866        ei = fac.fromInteger(11);
867        //System.out.println("ei  = " + ei);
868        // a(ei)
869        ai = PolyUtil.<ModInteger> evaluateMain(fac, a, ei);
870        //System.out.println("ai   = " + ai);
871        assertTrue("isONE( ai )", ai.isONE());
872
873        di = fac.fromInteger(13);
874        //System.out.println("di  = " + di);
875        // a(di)
876        bi = PolyUtil.<ModInteger> evaluateMain(fac, a, di);
877        //System.out.println("bi   = " + bi);
878        assertTrue("isONE( bi )", bi.isONE());
879
880        // interpolation result
881        r = cfac.getZERO();
882        //System.out.println("r   = " + r);
883
884        // interpolation polynomials product
885        Q = cfac.getONE();
886        //System.out.println("Q   = " + Q);
887
888        ci = PolyUtil.<ModInteger> evaluateMain(fac, Q, ei);
889        //System.out.println("ci   = " + ci);
890        // Q(ei)^-1
891        fi = ci.inverse();
892        //System.out.println("fi   = " + fi);
893        r = PolyUtil.<ModInteger> interpolate(cfac, r, Q, fi, ai, ei);
894        //System.out.println("r   = " + r);
895
896        // next evaluation polynomial
897        Qp = cfac.univariate(0);
898        Qp = Qp.subtract(cfac.getONE().multiply(ei));
899        //System.out.println("Qp   = " + Qp);
900        Q = Q.multiply(Qp);
901        //System.out.println("Q   = " + Q);
902
903        ci = PolyUtil.<ModInteger> evaluateMain(fac, Q, di);
904        //System.out.println("ci   = " + ci);
905        // Q(di)^-1
906        fi = ci.inverse();
907        //System.out.println("fi   = " + fi);
908        r = PolyUtil.<ModInteger> interpolate(cfac, r, Q, fi, bi, di);
909        //System.out.println("r   = " + r);
910
911        // check evaluation
912        gi = PolyUtil.<ModInteger> evaluateMain(fac, r, ei);
913        //System.out.println("gi   = " + gi);
914        hi = PolyUtil.<ModInteger> evaluateMain(fac, r, di);
915        //System.out.println("hi   = " + hi);
916        assertTrue("gi == 1 ", gi.isONE());
917        assertTrue("hi == 1 ", hi.isONE());
918
919        //            interpolate( a(ei), a(di) )            = a (mod 19)
920        assertEquals("interpolate(a mod (x-ei),a mod (x-di)) = a (mod 19)", a, r);
921    }
922
923
924    /**
925     * Test interpolate univariate deg &gt; 0 polynomial.
926     */
927    public void testInterpolateUnivariate() {
928        ModInteger ai, ci, ei, fi;
929        GenPolynomial<ModInteger> a;
930        GenPolynomialRing<ModInteger> cfac;
931        ModIntegerRing fac;
932        GenPolynomial<ModInteger> r;
933        GenPolynomial<ModInteger> Q;
934        GenPolynomial<ModInteger> Qp;
935
936        //long prime = 19;
937        long prime = getPrime1().longValue();
938        fac = new ModIntegerRing(prime);
939        //System.out.println("fac.modul  = " + fac.getModul());
940        cfac = new GenPolynomialRing<ModInteger>(fac, 1, to);
941        //System.out.println("cfac  = " + cfac);
942        int maxdeg = 19;
943
944        // polynomial to interpolate
945        long deg = 0;
946        do {
947            a = cfac.random(kl, ll, maxdeg, q);
948            if (!a.isZERO()) {
949                deg = a.degree(0);
950            }
951        } while (deg <= 0);
952        //System.out.println("a  = " + a);
953        //System.out.println("deg  = " + deg);
954
955        // interpolation result
956        r = cfac.getZERO();
957        //System.out.println("r   = " + r);
958
959        // interpolation polynomials product
960        Q = cfac.getONE();
961        //System.out.println("Q   = " + Q);
962
963        long i = -1;
964        long qdeg;
965        do {
966            i++;
967            if (i >= prime) {
968                assertTrue("elements of Z_prime exhausted", i < prime);
969            }
970            qdeg = Q.degree(0);
971            ei = fac.fromInteger(i);
972            //System.out.println("ei  = " + ei);
973            // a(ei)
974            ai = PolyUtil.<ModInteger> evaluateMain(fac, a, ei);
975            //System.out.println("ai   = " + ai);
976
977            ci = PolyUtil.<ModInteger> evaluateMain(fac, Q, ei);
978            //System.out.println("ci   = " + ci);
979            // Q(ei)^-1
980            fi = ci.inverse();
981            //System.out.println("fi   = " + fi);
982            r = PolyUtil.<ModInteger> interpolate(cfac, r, Q, fi, ai, ei);
983            //System.out.println("r   = " + r);
984
985            // next evaluation polynomial
986            Qp = cfac.univariate(0);
987            Qp = Qp.subtract(cfac.getONE().multiply(ei));
988            //System.out.println("Qp   = " + Qp);
989            Q = Q.multiply(Qp);
990            //System.out.println("Q   = " + Q);
991        } while (qdeg < deg);
992
993        //System.out.println("a   = " + a);
994        //System.out.println("r   = " + r);
995
996        //            interpolate( a(e1), ..., a(ei) )           = a (mod 19)
997        assertEquals("interpolate(a mod (x-e1),...,a mod (x-ei)) = a (mod 19)", a, r);
998    }
999
1000
1001    /**
1002     * Test interpolate multivariate deg &gt; 0 polynomial.
1003     */
1004    public void testInterpolateMultivariate() {
1005        ModInteger ci, ei, fi;
1006        GenPolynomial<ModInteger> ap, bp;
1007        GenPolynomial<GenPolynomial<ModInteger>> a;
1008        GenPolynomialRing<GenPolynomial<ModInteger>> cfac;
1009        GenPolynomialRing<ModInteger> ufac;
1010        GenPolynomialRing<ModInteger> dfac;
1011        ModIntegerRing fac;
1012        GenPolynomial<GenPolynomial<ModInteger>> r;
1013        GenPolynomial<ModInteger> Q;
1014        GenPolynomial<ModInteger> Qp;
1015
1016        //long prime = 19;
1017        long prime = getPrime1().longValue();
1018        fac = new ModIntegerRing(prime);
1019        //System.out.println("fac.modul  = " + fac.getModul());
1020        ufac = new GenPolynomialRing<ModInteger>(fac, 1, to);
1021        //System.out.println("ufac  = " + ufac);
1022        cfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(ufac, rl, to);
1023        //System.out.println("cfac  = " + cfac);
1024        dfac = new GenPolynomialRing<ModInteger>(fac, rl, to);
1025        //System.out.println("dfac  = " + dfac);
1026        int maxdeg = 19;
1027
1028        // polynomial to interpolate
1029        long deg = 0;
1030        do {
1031            a = cfac.random(kl, ll + 9, maxdeg, q);
1032            if (!a.isZERO()) {
1033                deg = PolyUtil.<ModInteger> coeffMaxDegree(a);
1034            }
1035        } while (deg <= 0);
1036        //System.out.println("a  = " + a);
1037        //System.out.println("deg  = " + deg);
1038        ExpVector degv = a.degreeVector();
1039        //System.out.println("degv  = " + degv);
1040
1041        // interpolation result
1042        r = cfac.getZERO();
1043        //System.out.println("r   = " + r);
1044
1045        // interpolation polynomials product
1046        Q = ufac.getONE();
1047        //System.out.println("Q   = " + Q);
1048
1049        long i = -1;
1050        long qdeg;
1051        ExpVector qdegv;
1052        do {
1053            i++;
1054            if (i >= prime) {
1055                assertTrue("elements of Z_prime exhausted", i < prime);
1056            }
1057            qdeg = Q.degree(0);
1058            ei = fac.fromInteger(i);
1059            //System.out.println("ei  = " + ei);
1060            // a(ei)
1061            ap = PolyUtil.<ModInteger> evaluateFirstRec(ufac, dfac, a, ei);
1062            //System.out.println("ap   = " + ap);
1063            qdegv = ap.degreeVector();
1064            //System.out.println("qdegv = " + qdegv);
1065            if (!degv.equals(qdegv)) {
1066                continue;
1067            }
1068            ci = PolyUtil.<ModInteger> evaluateMain(fac, Q, ei);
1069            //System.out.println("ci   = " + ci);
1070            // Q(ei)^-1
1071            fi = ci.inverse();
1072            //System.out.println("fi   = " + fi);
1073            r = PolyUtil.<ModInteger> interpolate(cfac, r, Q, fi, ap, ei);
1074            //System.out.println("r   = " + r);
1075
1076            // check
1077            bp = PolyUtil.<ModInteger> evaluateFirstRec(ufac, dfac, r, ei);
1078            //System.out.println("bp   = " + bp);
1079            assertEquals("interpolate(a)(ei) == a ", bp, ap);
1080
1081
1082            // next evaluation polynomial
1083            Qp = ufac.univariate(0);
1084            Qp = Qp.subtract(ufac.getONE().multiply(ei));
1085            //System.out.println("Qp   = " + Qp);
1086            Q = Q.multiply(Qp);
1087            //System.out.println("Q   = " + Q);
1088        } while (qdeg <= deg);
1089
1090        //System.out.println("a   = " + a);
1091        //System.out.println("r   = " + r);
1092
1093        //            interpolate( a(e1), ..., a(ei) )           = a (mod 19)
1094        assertEquals("interpolate(a mod (x-e1),...,a mod (x-ei)) = a (mod 19)", a, r);
1095    }
1096
1097
1098    /**
1099     * Test interpolate rational multivariate deg &gt; 0 polynomial.
1100     */
1101    public void testInterpolateRationalMultivariate() {
1102        BigRational ci, ei, fi;
1103        GenPolynomial<BigRational> ap, bp;
1104        GenPolynomial<GenPolynomial<BigRational>> a;
1105        GenPolynomialRing<GenPolynomial<BigRational>> cfac;
1106        GenPolynomialRing<BigRational> ufac;
1107        GenPolynomialRing<BigRational> dfac;
1108        BigRational fac;
1109        GenPolynomial<GenPolynomial<BigRational>> r;
1110        GenPolynomial<BigRational> Q;
1111        GenPolynomial<BigRational> Qp;
1112
1113        fac = new BigRational();
1114        //System.out.println("fac.modul  = " + fac.getModul());
1115        ufac = new GenPolynomialRing<BigRational>(fac, 1, to);
1116        //System.out.println("ufac  = " + ufac);
1117        cfac = new GenPolynomialRing<GenPolynomial<BigRational>>(ufac, rl, to);
1118        //System.out.println("cfac  = " + cfac);
1119        dfac = new GenPolynomialRing<BigRational>(fac, rl, to);
1120        //System.out.println("dfac  = " + dfac);
1121        int maxdeg = 19;
1122
1123        // polynomial to interpolate
1124        long deg = 0;
1125        do {
1126            a = cfac.random(kl, ll + 9, maxdeg, q);
1127            if (!a.isZERO()) {
1128                deg = PolyUtil.<BigRational> coeffMaxDegree(a);
1129            }
1130        } while (deg <= 0);
1131        //System.out.println("a  = " + a);
1132        //System.out.println("deg  = " + deg);
1133        ExpVector degv = a.degreeVector();
1134        //System.out.println("degv  = " + degv);
1135
1136        // interpolation result
1137        r = cfac.getZERO();
1138        //System.out.println("r   = " + r);
1139
1140        // interpolation polynomials product
1141        Q = ufac.getONE();
1142        //System.out.println("Q   = " + Q);
1143
1144        long i = -1;
1145        long qdeg;
1146        ExpVector qdegv;
1147        do {
1148            i++;
1149            qdeg = Q.degree(0);
1150            ei = fac.fromInteger(i);
1151            //System.out.println("ei  = " + ei);
1152            // a(ei)
1153            ap = PolyUtil.<BigRational> evaluateFirstRec(ufac, dfac, a, ei);
1154            //System.out.println("ap   = " + ap);
1155            qdegv = ap.degreeVector();
1156            //System.out.println("qdegv = " + qdegv);
1157            if (!degv.equals(qdegv)) {
1158                continue;
1159            }
1160            ci = PolyUtil.<BigRational> evaluateMain(fac, Q, ei);
1161            //System.out.println("ci   = " + ci);
1162            // Q(ei)^-1
1163            fi = ci.inverse();
1164            //System.out.println("fi   = " + fi);
1165            r = PolyUtil.<BigRational> interpolate(cfac, r, Q, fi, ap, ei);
1166            //System.out.println("r   = " + r);
1167
1168            // check
1169            bp = PolyUtil.<BigRational> evaluateFirstRec(ufac, dfac, r, ei);
1170            //System.out.println("bp   = " + bp);
1171            assertEquals("interpolate(a)(ei) == a ", bp, ap);
1172
1173
1174            // next evaluation polynomial
1175            Qp = ufac.univariate(0);
1176            Qp = Qp.subtract(ufac.getONE().multiply(ei));
1177            //System.out.println("Qp   = " + Qp);
1178            Q = Q.multiply(Qp);
1179            //System.out.println("Q   = " + Q);
1180        } while (qdeg <= deg);
1181
1182        //System.out.println("a   = " + a);
1183        //System.out.println("r   = " + r);
1184
1185        //            interpolate( a(e1), ..., a(ei) )           = a (mod 19)
1186        assertEquals("interpolate(a mod (x-e1),...,a mod (x-ei)) = a (mod 19)", a, r);
1187    }
1188
1189
1190    /**
1191     * Test coefficient map function.
1192     */
1193    public void testMap() {
1194        // integers
1195        BigInteger fi = new BigInteger();
1196        //System.out.println("fi = " + fi);
1197
1198        // rational numbers
1199        BigRational fr = new BigRational();
1200        //System.out.println("fr = " + fr);
1201
1202        // modular integers
1203        ModIntegerRing fm = new ModIntegerRing(17);
1204        //System.out.println("fm = " + fm);
1205
1206        // polynomials over integral numbers
1207        GenPolynomialRing<BigInteger> pfi = new GenPolynomialRing<BigInteger>(fi, rl);
1208        //System.out.println("pfi = " + pfi);
1209
1210        // polynomials over rational numbers
1211        GenPolynomialRing<BigRational> pfr = new GenPolynomialRing<BigRational>(fr, rl);
1212        //System.out.println("pfr = " + pfr);
1213
1214        // polynomials over modular integers
1215        GenPolynomialRing<ModInteger> pfm = new GenPolynomialRing<ModInteger>(fm, rl);
1216        //System.out.println("pfm = " + pfm);
1217
1218
1219        // random polynomial
1220        GenPolynomial<BigInteger> pi = pfi.random(kl, 2 * ll, el, q);
1221        //System.out.println("pi = " + pi);
1222
1223        // random polynomial
1224        GenPolynomial<BigRational> pr = pfr.random(kl, 2 * ll, el, q).monic();
1225        //System.out.println("pr = " + pr);
1226
1227        // random polynomial
1228        GenPolynomial<ModInteger> pm = pfm.random(kl, 2 * ll, el, q);
1229        //System.out.println("pm = " + pm);
1230
1231        // test integer to rational and back
1232        GenPolynomial<BigRational> qr;
1233        GenPolynomial<BigInteger> qi;
1234        qr = PolyUtil.<BigInteger, BigRational> map(pfr, pi, new FromInteger<BigRational>(fr));
1235        qi = PolyUtil.<BigRational, BigInteger> map(pfi, qr, new RatNumer());
1236        //System.out.println("qr = " + qr);
1237        //System.out.println("qi = " + qi);
1238        assertEquals("pi == qi ", pi, qi);
1239
1240        // test rational to integer and back
1241        qi = PolyUtil.integerFromRationalCoefficients(pfi, pr);
1242        qr = PolyUtil.<BigInteger, BigRational> map(pfr, qi, new FromInteger<BigRational>(fr));
1243        qr = qr.monic();
1244        //System.out.println("pr = " + pr);
1245        //System.out.println("qr = " + qr);
1246        //System.out.println("qi = " + qi);
1247        assertEquals("pr == qr ", pr, qr);
1248
1249        // test symmetric modular integer to integer and back
1250        GenPolynomial<ModInteger> qm;
1251        qi = PolyUtil.<ModInteger, BigInteger> map(pfi, pm, new ModSymToInt<ModInteger>());
1252        qm = PolyUtil.<BigInteger, ModInteger> map(pfm, qi, new FromInteger<ModInteger>(fm));
1253        //System.out.println("qi = " + qi);
1254        //System.out.println("qm = " + qm);
1255        assertEquals("pm == qm ", pm, qm);
1256
1257        // test modular integer to integer and back
1258        qi = PolyUtil.<ModInteger, BigInteger> map(pfi, pm, new ModToInt<ModInteger>());
1259        qm = PolyUtil.<BigInteger, ModInteger> map(pfm, qi, new FromInteger<ModInteger>(fm));
1260        //System.out.println("qi = " + qi);
1261        //System.out.println("qm = " + qm);
1262        assertEquals("pm == qm ", pm, qm);
1263
1264        // test symmetric modular integer to integer to rational and back
1265        qi = PolyUtil.<ModInteger, BigInteger> map(pfi, pm, new ModSymToInt<ModInteger>());
1266        qr = PolyUtil.<BigInteger, BigRational> map(pfr, qi, new FromInteger<BigRational>(fr));
1267        qi = PolyUtil.<BigRational, BigInteger> map(pfi, qr, new RatNumer());
1268        qm = PolyUtil.<BigInteger, ModInteger> map(pfm, qi, new FromInteger<ModInteger>(fm));
1269        //System.out.println("qi = " + qi);
1270        //System.out.println("qm = " + qm);
1271        assertEquals("pm == qm ", pm, qm);
1272    }
1273
1274
1275    /**
1276     * Test substitution.
1277     */
1278    public void testSubstitution() {
1279        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
1280
1281        // subs = x - 7
1282        GenPolynomial<BigInteger> s = dfac.univariate(0).subtract(dfac.fromInteger(7));
1283        GenPolynomial<BigInteger> s1 = dfac.univariate(0).sum(dfac.fromInteger(7));
1284        //System.out.println("s = " + s);
1285        //System.out.println("s1 = " + s1);
1286
1287        for (int i = 0; i < 5; i++) {
1288            a = dfac.random(kl, ll, el, q);
1289            //System.out.println("a = " + a);
1290            b = PolyUtil.<BigInteger> substituteMain(a, s);
1291            c = PolyUtil.<BigInteger> substituteMain(b, s1);
1292            //System.out.println("b = " + b);
1293            //System.out.println("c = " + c);
1294            //System.out.println("a == c " + a.equals(c));
1295            assertEquals("a == c ", a, c);
1296        }
1297    }
1298
1299
1300    /**
1301     * Test algebraic substitution.
1302     */
1303    public void testAlgebraicSubstitution() {
1304
1305        BigRational cfac = new BigRational(1);
1306        String[] alpha = new String[] { "alpha" };
1307        String[] vars = new String[] { "z" };
1308        GenPolynomialRing<BigRational> pfac = new GenPolynomialRing<BigRational>(cfac, 1, to, alpha);
1309        GenPolynomial<BigRational> agen = pfac.univariate(0, 2);
1310        agen = agen.sum(pfac.getONE()); // x^2 + 1
1311        AlgebraicNumberRing<BigRational> afac = new AlgebraicNumberRing<BigRational>(agen, true);
1312        GenPolynomialRing<AlgebraicNumber<BigRational>> apfac = new GenPolynomialRing<AlgebraicNumber<BigRational>>(
1313                        afac, 1, to, vars); // univariate
1314
1315        //System.out.println("agen  = " + agen);
1316        //System.out.println("afac  = " + afac);
1317        //System.out.println("apfac = " + apfac);
1318
1319        // subs = x - 7
1320        GenPolynomial<AlgebraicNumber<BigRational>> s = apfac.univariate(0)
1321                        .subtract(apfac.fromInteger(7).multiply(afac.getGenerator()));
1322        GenPolynomial<AlgebraicNumber<BigRational>> s1 = apfac.univariate(0)
1323                        .sum(apfac.fromInteger(7).multiply(afac.getGenerator()));
1324        //System.out.println("s = " + s);
1325        //System.out.println("s1 = " + s1);
1326
1327        GenPolynomial<AlgebraicNumber<BigRational>> a, b, c;
1328        for (int i = 0; i < 5; i++) {
1329            a = apfac.random(kl, ll, el, q);
1330            //System.out.println("a = " + a);
1331            b = PolyUtil.<AlgebraicNumber<BigRational>> substituteMain(a, s);
1332            c = PolyUtil.<AlgebraicNumber<BigRational>> substituteMain(b, s1);
1333            //System.out.println("b = " + b);
1334            //System.out.println("c = " + c);
1335            //System.out.println("a == c " + a.equals(c));
1336            assertEquals("a == c ", a, c);
1337        }
1338    }
1339
1340
1341    /**
1342     * Test multivariate substitution.
1343     */
1344    public void testMultivarSubstitution() {
1345        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 2, to);
1346        // subs = x - 7
1347        GenPolynomial<BigInteger> s = dfac.univariate(0).subtract(dfac.fromInteger(7));
1348        GenPolynomial<BigInteger> s1 = dfac.univariate(0).sum(dfac.fromInteger(7));
1349        //System.out.println("s = " + s);
1350        //System.out.println("s1 = " + s1);
1351
1352        for (int i = 0; i < 5; i++) {
1353            a = dfac.random(kl, ll, el, q);
1354            //System.out.println("a = " + a);
1355            b = PolyUtil.<BigInteger> substituteUnivariateMult(a, s);
1356            c = PolyUtil.<BigInteger> substituteUnivariateMult(b, s1);
1357            //System.out.println("b = " + b);
1358            //System.out.println("c = " + c);
1359            //System.out.println("a == c " + a.equals(c));
1360            assertEquals("a == c ", a, c);
1361        }
1362    }
1363
1364
1365    /**
1366     * Test switch variables.
1367     */
1368    public void testSwitchVariables() {
1369        BigRational cfac = new BigRational(1);
1370        GenPolynomialRing<BigRational> pfac = new GenPolynomialRing<BigRational>(cfac, rl, to);
1371        GenPolynomialRing<GenPolynomial<BigRational>> rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(
1372                        pfac, rl, to);
1373
1374        //System.out.println("pfac  = " + pfac);
1375        //System.out.println("rfac  = " + rfac);
1376
1377        GenPolynomial<GenPolynomial<BigRational>> a, c;
1378        GenPolynomial<GenPolynomial<BigRational>> b;
1379        for (int i = 0; i < 5; i++) {
1380            a = rfac.random(kl, ll, el, q);
1381            //System.out.println("a = " + a);
1382            b = PolyUtil.<BigRational> switchVariables(a);
1383            c = PolyUtil.<BigRational> switchVariables(b);
1384            //System.out.println("b = " + b);
1385            //System.out.println("c = " + c);
1386            //System.out.println("a == c " + a.equals(c));
1387            assertEquals("a == c ", a, c);
1388        }
1389    }
1390
1391
1392    /**
1393     * Test algebraic conversions.
1394     */
1395    public void testAlgebraicConversions() {
1396        BigRational cfac = new BigRational(1);
1397        String[] alpha = new String[] { "alpha" };
1398        //String[] vars = new String[] { "z" };
1399        GenPolynomialRing<BigRational> pfac = new GenPolynomialRing<BigRational>(cfac, 1, to, alpha);
1400        GenPolynomial<BigRational> agen = pfac.univariate(0, 2);
1401        agen = agen.sum(pfac.getONE()); // x^2 + 1
1402        AlgebraicNumberRing<BigRational> afac = new AlgebraicNumberRing<BigRational>(agen, true);
1403        GenPolynomialRing<AlgebraicNumber<BigRational>> apfac = new GenPolynomialRing<AlgebraicNumber<BigRational>>(
1404                        afac, rl, to);
1405        GenPolynomialRing<GenPolynomial<BigRational>> rfac = new GenPolynomialRing<GenPolynomial<BigRational>>(
1406                        pfac, rl, to);
1407
1408        //System.out.println("agen  = " + agen);
1409        //System.out.println("afac  = " + afac);
1410        //System.out.println("apfac = " + apfac);
1411        //System.out.println("pfac  = " + pfac);
1412        //System.out.println("rfac  = " + rfac);
1413
1414        GenPolynomial<AlgebraicNumber<BigRational>> a, c;
1415        GenPolynomial<GenPolynomial<BigRational>> b;
1416        for (int i = 0; i < 5; i++) {
1417            a = apfac.random(kl, ll, el, q);
1418            //System.out.println("a = " + a);
1419            b = PolyUtil.<BigRational> fromAlgebraicCoefficients(rfac, a);
1420            c = PolyUtil.<BigRational> convertRecursiveToAlgebraicCoefficients(apfac, b);
1421            //System.out.println("b = " + b);
1422            //System.out.println("c = " + c);
1423            //System.out.println("a == c " + a.equals(c));
1424            assertEquals("a == c ", a, c);
1425        }
1426    }
1427
1428
1429    /**
1430     * Test Taylor series.
1431     */
1432    public void testTaylorSeries() {
1433        GenPolynomial<BigRational> a;
1434        GenPolynomial<BigRational> b;
1435        GenPolynomial<BigRational> c;
1436        GenPolynomialRing<BigRational> dfac;
1437        BigRational cfac;
1438
1439        cfac = new BigRational(1);
1440        String[] vars = new String[] { "x" };
1441        dfac = new GenPolynomialRing<BigRational>(cfac, 1, to, vars);
1442
1443        a = dfac.random(kl, ll, el, q);
1444        //System.out.println("a = " + a);
1445
1446        BigRational v = cfac.getZERO();
1447        //System.out.println("v = " + v);
1448
1449        b = PolyUtil.<BigRational> seriesOfTaylor(a, v);
1450        //System.out.println("taylor(a,0) = " + b);
1451        assertTrue("taylor(a,0) == a ", a.equals(b));
1452
1453        v = cfac.random(kl);
1454        //System.out.println("v = " + v);
1455
1456        b = PolyUtil.<BigRational> seriesOfTaylor(a, v);
1457        //System.out.println("taylor(a,v) = " + b);
1458
1459        c = PolyUtil.<BigRational> seriesOfTaylor(b, v.negate());
1460        //System.out.println("tailor(taylor(a,v),-v) = " + c);
1461        assertTrue("tailor(taylor(a,v),-v) == a ", a.equals(c));
1462    }
1463
1464
1465    /**
1466     * Test Complex real and imaginary part.
1467     */
1468    public void testComplexParts() {
1469        BigRational rf = new BigRational(1);
1470        GenPolynomialRing<BigRational> rfac = new GenPolynomialRing<BigRational>(rf, rl, to);
1471
1472        ComplexRing<BigRational> cf = new ComplexRing<BigRational>(new BigRational(1));
1473        GenPolynomialRing<Complex<BigRational>> cfac = new GenPolynomialRing<Complex<BigRational>>(cf, rl,
1474                        to);
1475
1476        Complex<BigRational> imag = cf.getIMAG();
1477
1478        GenPolynomial<BigRational> rp;
1479        GenPolynomial<BigRational> ip;
1480        GenPolynomial<Complex<BigRational>> crp;
1481        GenPolynomial<Complex<BigRational>> cip;
1482        GenPolynomial<Complex<BigRational>> cp;
1483        GenPolynomial<Complex<BigRational>> ap;
1484
1485        for (int i = 0; i < 3; i++) {
1486            cp = cfac.random(kl + 2 * i, ll * (i + 1), el + i, q);
1487
1488            assertTrue("length( c" + i + " ) <> 0", cp.length() >= 0);
1489            assertTrue(" not isZERO( c" + i + " )", !cp.isZERO());
1490            assertTrue(" not isONE( c" + i + " )", !cp.isONE());
1491
1492            rp = PolyUtil.<BigRational> realPartFromComplex(rfac, cp);
1493            ip = PolyUtil.<BigRational> imaginaryPartFromComplex(rfac, cp);
1494
1495            crp = PolyUtil.<BigRational> toComplex(cfac, rp);
1496            cip = PolyUtil.<BigRational> toComplex(cfac, ip);
1497
1498            ap = crp.sum(cip.multiply(imag));
1499
1500            //System.out.println("cp = " + cp);
1501            //System.out.println("rp = " + rp);
1502            //System.out.println("ip = " + ip);
1503            //System.out.println("crp = " + crp);
1504            //System.out.println("cip = " + cip);
1505            //System.out.println("ap  = " + ap);
1506
1507            assertEquals("re(c)+i*im(c) = c", cp, ap);
1508        }
1509    }
1510
1511
1512    /**
1513     * Test product representation conversion, rational numbers.
1514     */
1515    public void testProductConversionRN() {
1516        GenPolynomialRing<BigRational> ufac;
1517        ufac = new GenPolynomialRing<BigRational>(new BigRational(1), 1);
1518
1519        ProductRing<GenPolynomial<BigRational>> pfac;
1520        pfac = new ProductRing<GenPolynomial<BigRational>>(ufac, rl);
1521
1522        GenPolynomialRing<BigRational> dfac = new GenPolynomialRing<BigRational>(new BigRational(1), rl, to);
1523
1524        GenPolynomial<BigRational> c;
1525        Product<GenPolynomial<BigRational>> cp;
1526
1527        c = dfac.getONE();
1528        //System.out.println("c = " + c);
1529
1530        cp = PolyUtil.<BigRational> toProduct(pfac, c);
1531        //System.out.println("cp = " + cp);
1532        assertTrue("isONE( cp )", cp.isONE());
1533
1534        c = dfac.random(kl, ll, el, q);
1535        //System.out.println("c = " + c);
1536
1537        cp = PolyUtil.<BigRational> toProduct(pfac, c);
1538        //System.out.println("cp = " + cp);
1539        assertTrue("!isONE( cp )", !cp.isONE());
1540    }
1541
1542
1543    /**
1544     * Test polynomal over product representation conversion, algebraic numbers.
1545     */
1546    public void testPolyProductConversionAN() {
1547        GenPolynomialRing<BigRational> ufac;
1548        ufac = new GenPolynomialRing<BigRational>(new BigRational(1), 1);
1549
1550        GenPolynomial<BigRational> m;
1551        m = ufac.univariate(0, 2);
1552        m = m.subtract(ufac.univariate(0, 1));
1553        //System.out.println("m = " + m);
1554
1555        AlgebraicNumberRing<BigRational> afac;
1556        afac = new AlgebraicNumberRing<BigRational>(m);
1557        //System.out.println("afac = " + afac);
1558
1559        ProductRing<AlgebraicNumber<BigRational>> pfac;
1560        pfac = new ProductRing<AlgebraicNumber<BigRational>>(afac, rl);
1561
1562        GenPolynomialRing<Product<AlgebraicNumber<BigRational>>> dpfac;
1563        dpfac = new GenPolynomialRing<Product<AlgebraicNumber<BigRational>>>(pfac, 2);
1564
1565        GenPolynomialRing<AlgebraicNumber<BigRational>> dfac;
1566        dfac = new GenPolynomialRing<AlgebraicNumber<BigRational>>(afac, 2, to);
1567
1568
1569        GenPolynomial<AlgebraicNumber<BigRational>> c;
1570        GenPolynomial<Product<AlgebraicNumber<BigRational>>> cp;
1571
1572        c = dfac.getONE();
1573        //System.out.println("c = " + c);
1574
1575        cp = PolyUtil.<AlgebraicNumber<BigRational>> toProductGen(dpfac, c);
1576        //System.out.println("cp = " + cp);
1577        assertTrue("isZERO( cp )", cp.isONE());
1578
1579        c = dfac.random(kl, ll, el, q);
1580        //System.out.println("c = " + c);
1581
1582        cp = PolyUtil.<AlgebraicNumber<BigRational>> toProductGen(dpfac, c);
1583        //System.out.println("cp = " + cp);
1584        assertTrue("!isONE( cp )", !cp.isONE());
1585    }
1586
1587
1588    /**
1589     * Test remove unused upper variables.
1590     */
1591    public void testRemoveUnusedUpper() {
1592        //System.out.println("dfac = " + dfac);
1593        a = dfac.univariate(3, 2);
1594        b = a.subtract(dfac.univariate(1, 1));
1595        //System.out.println("a = " + a);
1596        //System.out.println("b = " + b);
1597
1598        c = PolyUtil.<BigInteger> removeUnusedUpperVariables(b);
1599        //System.out.println("c = " + c + ", fac = " + c.ring);
1600        assertTrue("#var == 4: " + c.ring.nvar, c.ring.nvar == 4);
1601
1602        a = dfac.univariate(3, 2);
1603        //System.out.println("a = " + a);
1604
1605        c = PolyUtil.<BigInteger> removeUnusedUpperVariables(a);
1606        //System.out.println("c = " + c + ", fac = " + c.ring);
1607        assertTrue("#var == 2: " + c.ring.nvar, c.ring.nvar == 2);
1608
1609        a = dfac.univariate(1, 2);
1610        //System.out.println("a = " + a);
1611
1612        c = PolyUtil.<BigInteger> removeUnusedUpperVariables(a);
1613        //System.out.println("c = " + c + ", fac = " + c.ring);
1614        assertTrue("#var == 4: " + c.ring.nvar, c.ring.nvar == 4);
1615    }
1616
1617
1618    /**
1619     * Test remove unused lower variables.
1620     */
1621    public void testRemoveUnusedLower() {
1622        //System.out.println("dfac = " + dfac);
1623        a = dfac.univariate(3, 2);
1624        b = a.subtract(dfac.univariate(1, 1));
1625        //System.out.println("a = " + a);
1626        //System.out.println("b = " + b);
1627
1628        c = PolyUtil.<BigInteger> removeUnusedLowerVariables(b);
1629        //System.out.println("c = " + c + ", fac = " + c.ring);
1630        assertTrue("#var == 4: " + c.ring.nvar, c.ring.nvar == 4);
1631
1632        a = dfac.univariate(3, 2);
1633        //System.out.println("a = " + a);
1634
1635        c = PolyUtil.<BigInteger> removeUnusedLowerVariables(a);
1636        //System.out.println("c = " + c + ", fac = " + c.ring);
1637        assertTrue("#var == 4: " + c.ring.nvar, c.ring.nvar == 4);
1638
1639        a = dfac.univariate(1, 2);
1640        //System.out.println("a = " + a);
1641
1642        c = PolyUtil.<BigInteger> removeUnusedLowerVariables(a);
1643        //System.out.println("c = " + c + ", fac = " + c.ring);
1644        assertTrue("#var == 2: " + c.ring.nvar, c.ring.nvar == 2);
1645    }
1646
1647
1648    /**
1649     * Test remove unused middle variables.
1650     */
1651    public void testRemoveUnusedMiddle() {
1652        //System.out.println("dfac = " + dfac);
1653        a = dfac.univariate(4, 2);
1654        b = a.subtract(dfac.univariate(0, 1));
1655        //System.out.println("a = " + a);
1656        //System.out.println("b = " + b);
1657
1658        c = PolyUtil.<BigInteger> removeUnusedLowerVariables(b);
1659        //System.out.println("c = " + c + ", fac = " + c.ring);
1660        assertTrue("#var == 5: " + c.ring.nvar, c.ring.nvar == 5);
1661        c = PolyUtil.<BigInteger> removeUnusedUpperVariables(c);
1662        //System.out.println("c = " + c + ", fac = " + c.ring);
1663        assertTrue("#var == 5: " + c.ring.nvar, c.ring.nvar == 5);
1664
1665        c = PolyUtil.<BigInteger> removeUnusedMiddleVariables(c);
1666        //System.out.println("c = " + c + ", fac = " + c.ring);
1667        assertTrue("#var == 2: " + c.ring.nvar, c.ring.nvar == 2);
1668
1669        a = dfac.univariate(3, 2);
1670        b = a.subtract(dfac.univariate(1, 1));
1671        //System.out.println("a = " + a);
1672        //System.out.println("b = " + b);
1673
1674        try {
1675            c = PolyUtil.<BigInteger> removeUnusedMiddleVariables(b);
1676            fail("c = " + c + ", fac = " + c.ring);
1677        } catch (RuntimeException e) {
1678            // success
1679        }
1680
1681        c = PolyUtil.<BigInteger> removeUnusedLowerVariables(b);
1682        //System.out.println("c = " + c + ", fac = " + c.ring);
1683        assertTrue("#var == 4: " + c.ring.nvar, c.ring.nvar == 4);
1684        c = PolyUtil.<BigInteger> removeUnusedUpperVariables(c);
1685        //System.out.println("c = " + c + ", fac = " + c.ring);
1686        assertTrue("#var == 3: " + c.ring.nvar, c.ring.nvar == 3);
1687
1688        c = PolyUtil.<BigInteger> removeUnusedMiddleVariables(c);
1689        //System.out.println("c = " + c + ", fac = " + c.ring);
1690        assertTrue("#var == 2: " + c.ring.nvar, c.ring.nvar == 2);
1691    }
1692
1693
1694    /**
1695     * Test transformation.
1696     */
1697    public void testTransformation() {
1698        //dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
1699        //System.out.println("ring = " + dfac.toScript());
1700        c = dfac.getONE();
1701        //System.out.println("c = " + c);
1702        a = PolyUtil.reciprocalTransformation(c);
1703        //System.out.println("a = " + a);
1704
1705        d = dfac.getZERO();
1706        //System.out.println("d = " + d);
1707        b = PolyUtil.reciprocalTransformation(d);
1708        //System.out.println("b = " + b);
1709
1710        c = dfac.random(kl * 2, ll + 2, el * 2, q + q);
1711        //System.out.println("c = " + c);
1712        a = PolyUtil.reciprocalTransformation(c);
1713        //System.out.println("a = " + a);
1714        b = PolyUtil.reciprocalTransformation(a);
1715        //System.out.println("b = " + b);
1716        assertEquals("recip(recip(c)) == c: ", c, b);
1717
1718        for (int i = 0; i < rl; i++) {
1719            //System.out.println("i = " + i + ", deg(c,i) = " + c.degree(i));
1720            a = PolyUtil.reciprocalTransformation(c, i);
1721            //System.out.println("a = " + a);
1722            b = PolyUtil.reciprocalTransformation(a, i);
1723            //System.out.println("b = " + b);
1724            assertEquals("recip(recip(c)) == c: ", c, b);
1725            //break;
1726        }
1727    }
1728
1729
1730    /**
1731     * Test translation.
1732     */
1733    public void testTranslation() {
1734        //dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), 1, to);
1735        //System.out.println("ring = " + rfac.toScript());
1736        ai = new BigInteger(5);
1737        //System.out.println("ai = " + ai);
1738
1739        cr = rfac.getONE();
1740        //System.out.println("cr = " + cr);
1741        ar = PolyUtil.translationMainRecursive(cr, ai);
1742        //System.out.println("ar = " + ar);
1743        br = PolyUtil.translationMainRecursive(ar, ai.negate());
1744        //System.out.println("br = " + br);
1745        assertEquals("translat(translat(cr)) == cr: ", cr, br);
1746
1747        dr = rfac.getZERO();
1748        //System.out.println("dr = " + dr);
1749        ar = PolyUtil.translationMainRecursive(dr, ai);
1750        //System.out.println("ar = " + ar);
1751        br = PolyUtil.translationMainRecursive(ar, ai.negate());
1752        //System.out.println("br = " + br);
1753        assertEquals("translat(translat(dr)) == dr: ", dr, br);
1754
1755        cr = rfac.univariate(0).power(3);
1756        cr = cr.sum(cr.power(5));
1757        //System.out.println("cr = " + cr);
1758        ar = PolyUtil.translationMainRecursive(cr, ai);
1759        //System.out.println("ar = " + ar);
1760        br = PolyUtil.translationMainRecursive(ar, ai.negate());
1761        //System.out.println("br = " + br);
1762        assertEquals("translat(translat(cr)) == cr: ", cr, br);
1763
1764
1765        //System.out.println("ring = " + dfac.toScript());
1766        c = dfac.getONE();
1767        //System.out.println("c = " + c);
1768        a = PolyUtil.translationMain(c, ai);
1769        //System.out.println("a = " + a);
1770        b = PolyUtil.translationMain(a, ai.negate());
1771        //System.out.println("b = " + b);
1772        assertEquals("translat(translat(c)) == c: ", c, b);
1773
1774        c = dfac.univariate(0).power(2);
1775        c = c.sum(c.power(6));
1776        //System.out.println("c = " + c);
1777        a = PolyUtil.translationMain(c, ai);
1778        //System.out.println("a = " + a);
1779        b = PolyUtil.translationMain(a, ai.negate());
1780        //System.out.println("b = " + b);
1781        assertEquals("translat(translat(c)) == c: ", c, b);
1782
1783        List<BigInteger> H = new ArrayList<BigInteger>(rl);
1784        List<BigInteger> Hm = new ArrayList<BigInteger>(rl);
1785        for (int i = 1; i <= rl; i++) {
1786            H.add(new BigInteger(i));
1787            Hm.add(new BigInteger(-i));
1788        }
1789        //System.out.println("H = " + H + ", Hm = " + Hm);
1790
1791        c = dfac.univariate(0).power(2);
1792        c = c.sum(c.power(5));
1793        c = c.multiply(dfac.univariate(1).power(3));
1794        c = c.multiply(dfac.univariate(2).power(4));
1795        c = c.sum(dfac.univariate(3).power(7));
1796        c = c.sum(dfac.univariate(4).power(11));
1797        //System.out.println("c = " + c);
1798        a = PolyUtil.translation(c, H);
1799        //System.out.println("a = " + a);
1800        b = PolyUtil.translation(a, Hm);
1801        //System.out.println("b = " + b);
1802        assertEquals("translat(translat(c)) == c: ", c, b);
1803
1804        c = dfac.random(kl * 2, ll + 2, el * 2, q + q);
1805        //System.out.println("c = " + c);
1806        a = PolyUtil.translation(c, H);
1807        //System.out.println("a = " + a);
1808        b = PolyUtil.translation(a, Hm);
1809        //System.out.println("b = " + b);
1810        assertEquals("translat(translat(c)) == c: ", c, b);
1811    }
1812
1813}