Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007
008import junit.framework.Test;
009import junit.framework.TestCase;
010import junit.framework.TestSuite;
011
012import edu.jas.arith.ModInteger;
013import edu.jas.arith.ModIntegerRing;
014
015
016/**
017 * Galois field coefficients GenPolynomial tests with JUnit.
018 * @author Heinz Kredel
019 */
020
021public class GFGenPolynomialTest extends TestCase {
022
023
024    /**
025     * main.
026     */
027    public static void main(String[] args) {
028        junit.textui.TestRunner.run(suite());
029    }
030
031
032    /**
033     * Constructs a <CODE>GFGenPolynomialTest</CODE> object.
034     * @param name String.
035     */
036    public GFGenPolynomialTest(String name) {
037        super(name);
038    }
039
040
041    /**
042     * suite.
043     */
044    public static Test suite() {
045        TestSuite suite = new TestSuite(GFGenPolynomialTest.class);
046        return suite;
047    }
048
049
050    GenPolynomialRing<AlgebraicNumber<ModInteger>> fac;
051
052
053    AlgebraicNumberRing<ModInteger> cfac;
054
055
056    GenPolynomial<AlgebraicNumber<ModInteger>> a, b, c, d, e;
057
058
059    int rl = 7;
060
061
062    int kl = 10;
063
064
065    int ll = 8;
066
067
068    int el = 5;
069
070
071    float q = 0.5f;
072
073
074    protected long getPrime() {
075        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
076        for (int i = 1; i < 60; i++) {
077            prime *= 2;
078        }
079        prime -= 93;
080        //System.out.println("prime = " + prime);
081        return prime;
082    }
083
084
085    @Override
086    protected void setUp() {
087        a = b = c = d = e = null;
088        long prime = getPrime();
089        ModIntegerRing r = new ModIntegerRing(prime);
090        // univariate minimal polynomial
091        GenPolynomialRing<ModInteger> mfac = new GenPolynomialRing<ModInteger>(r, 1);
092        GenPolynomial<ModInteger> modul = mfac.random(5);
093        while (modul.isZERO() || modul.isUnit() || modul.isConstant()) {
094            modul = mfac.random(5);
095        }
096        cfac = new AlgebraicNumberRing<ModInteger>(modul.monic());
097        fac = new GenPolynomialRing<AlgebraicNumber<ModInteger>>(cfac, rl);
098    }
099
100
101    @Override
102    protected void tearDown() {
103        a = b = c = d = e = null;
104        fac = null;
105    }
106
107
108    /**
109     * Test constructor and toString.
110     */
111    public void testConstruction() {
112        c = fac.getONE();
113        //System.out.println("c = " + c);
114        assertTrue("length( c ) = 1", c.length() == 1);
115        assertTrue("isZERO( c )c" + c, !c.isZERO());
116        assertTrue("isONE( c ) " + c, c.isONE());
117
118        d = fac.getZERO();
119        //System.out.println("d = " + d);
120        assertTrue("length( d ) = 0", d.length() == 0);
121        assertTrue("isZERO( d )", d.isZERO());
122        assertTrue("isONE( d )", !d.isONE());
123    }
124
125
126    /**
127     * Test random polynomial.
128     */
129    public void testRandom() {
130        for (int i = 0; i < 7; i++) {
131            a = fac.random(ll + i);
132            //System.out.println("a = " + a);
133
134            // fac.random(kl*(i+1), ll+2*i, el+i, q );
135            assertTrue("length( a" + i + " ) <> 0", a.length() >= 0);
136            assertTrue(" not isZERO( a" + i + " )", !a.isZERO());
137            assertTrue(" not isONE( a" + i + " )", !a.isONE());
138        }
139    }
140
141
142    /**
143     * Test addition.
144     */
145    public void testAddition() {
146        a = fac.random(ll);
147        b = fac.random(ll);
148
149        c = a.sum(b);
150        d = c.subtract(b);
151        assertEquals("a+b-b = a", a, d);
152
153        c = fac.random(ll);
154
155        ExpVector u = ExpVector.random(rl, el, q);
156        AlgebraicNumber<ModInteger> x = cfac.random(kl);
157
158        b = new GenPolynomial<AlgebraicNumber<ModInteger>>(fac, x, u);
159        c = a.sum(b);
160        d = a.sum(x, u);
161        assertEquals("a+p(x,u) = a+(x,u)", c, d);
162
163        c = a.subtract(b);
164        d = a.subtract(x, u);
165        assertEquals("a-p(x,u) = a-(x,u)", c, d);
166
167        a = new GenPolynomial<AlgebraicNumber<ModInteger>>(fac);
168        b = new GenPolynomial<AlgebraicNumber<ModInteger>>(fac, x, u);
169        c = b.sum(a);
170        d = a.sum(x, u);
171        assertEquals("a+p(x,u) = a+(x,u)", c, d);
172
173        c = a.subtract(b);
174        d = a.subtract(x, u);
175        assertEquals("a-p(x,u) = a-(x,u)", c, d);
176
177
178        c = fac.random(ll);
179        d = c.sum(a.sum(b));
180        e = c.sum(a).sum(b);
181        assertEquals("c+(a+b) = (c+a)+b", d, e);
182
183        c = a.sum(fac.getZERO());
184        d = a.subtract(fac.getZERO());
185        assertEquals("a+0 = a-0", c, d);
186
187        c = fac.getZERO().sum(a);
188        d = fac.getZERO().subtract(a.negate());
189        assertEquals("0+a = 0+(-a)", c, d);
190    }
191
192
193    /**
194     * Test object multiplication.
195     */
196    public void testMultiplication() {
197        a = fac.random(ll);
198        assertTrue("not isZERO( a )", !a.isZERO());
199
200        b = fac.random(ll);
201        assertTrue("not isZERO( b )", !b.isZERO());
202
203        c = b.multiply(a);
204        d = a.multiply(b);
205        assertTrue("not isZERO( c )", !c.isZERO());
206        assertTrue("not isZERO( d )", !d.isZERO());
207
208        //System.out.println("a = " + a);
209        //System.out.println("b = " + b);
210        e = d.subtract(c);
211        assertTrue("isZERO( a*b-b*a ) " + e, e.isZERO());
212
213        assertTrue("a*b = b*a", c.equals(d));
214        assertEquals("a*b = b*a", c, d);
215
216        c = fac.random(ll);
217        //System.out.println("c = " + c);
218        d = a.multiply(b.multiply(c));
219        e = (a.multiply(b)).multiply(c);
220
221        //System.out.println("d = " + d);
222        //System.out.println("e = " + e);
223
224        //System.out.println("d-e = " + d.subtract(c) );
225
226        assertEquals("a(bc) = (ab)c", d, e);
227        assertTrue("a(bc) = (ab)c", d.equals(e));
228
229        AlgebraicNumber<ModInteger> z = a.leadingBaseCoefficient();
230        //System.out.println("z = " + z);
231        if (z.isUnit()) {
232            AlgebraicNumber<ModInteger> x = z.inverse();
233            //System.out.println("x = " + x);
234            //System.out.println("a = " + a);
235            c = a.monic();
236            //System.out.println("c = " + c);
237            d = a.multiply(x);
238            //System.out.println("d = " + d);
239            assertEquals("a.monic() = a(1/ldcf(a))", c, d);
240        }
241
242        AlgebraicNumber<ModInteger> y = b.leadingBaseCoefficient();
243        if (y.isUnit()) {
244            y = y.inverse();
245            c = b.monic();
246            d = b.multiply(y);
247            assertEquals("b.monic() = b(1/ldcf(b))", c, d);
248
249            e = new GenPolynomial<AlgebraicNumber<ModInteger>>(fac, y);
250            d = b.multiply(e);
251            assertEquals("b.monic() = b(1/ldcf(b))", c, d);
252
253            d = e.multiply(b);
254            assertEquals("b.monic() = (1/ldcf(b))*b", c, d);
255        }
256    }
257
258
259    /**
260     * Test distributive law.
261     */
262    public void testDistributive() {
263        a = fac.random(ll);
264        b = fac.random(ll);
265        c = fac.random(ll);
266
267        d = a.multiply(b.sum(c));
268        e = a.multiply(b).sum(a.multiply(c));
269
270        assertEquals("a(b+c) = ab+ac", d, e);
271    }
272
273
274    /**
275     * Test object quotient and remainder.
276     */
277    public void testQuotRem1() {
278        fac = new GenPolynomialRing<AlgebraicNumber<ModInteger>>(cfac, 1);
279
280        a = fac.random(ll).monic();
281        assertTrue("not isZERO( a )", !a.isZERO());
282
283        b = fac.random(ll).monic();
284        assertTrue("not isZERO( b )", !b.isZERO());
285
286        GenPolynomial<AlgebraicNumber<ModInteger>> g = fac.random(ll).monic();
287        assertTrue("not isZERO( g )", !g.isZERO());
288        g = fac.getONE();
289        a = a.multiply(g);
290        b = b.multiply(g);
291        //System.out.println("a = " + a);
292        //System.out.println("b = " + b);
293        //System.out.println("g = " + g);
294
295        GenPolynomial<AlgebraicNumber<ModInteger>>[] qr;
296        qr = b.quotientRemainder(a);
297        c = qr[0];
298        d = qr[1];
299        //System.out.println("q = " + c);
300        //System.out.println("r = " + d);
301        e = c.multiply(a).sum(d);
302        assertEquals("b = q a + r", b, e);
303
304        qr = a.quotientRemainder(b);
305        c = qr[0];
306        d = qr[1];
307        //System.out.println("q = " + c);
308        //System.out.println("r = " + d);
309        e = c.multiply(b).sum(d);
310        assertEquals("a = q b + r", a, e);
311
312
313        // gcd tests -------------------------------
314        c = a.gcd(b);
315        //System.out.println("gcd = " + c);
316        assertTrue("a mod gcd(a,b) = 0", a.remainder(c).isZERO());
317        assertTrue("b mod gcd(a,b) = 0", b.remainder(c).isZERO());
318        assertEquals("g = gcd(a,b)", c, g);
319
320
321        GenPolynomial<AlgebraicNumber<ModInteger>>[] gst;
322        gst = a.egcd(b);
323        //System.out.println("egcd = " + gst[0]);
324        //System.out.println(", s = " + gst[1] + ", t = " + gst[2]);
325        c = gst[0];
326        d = gst[1];
327        e = gst[2];
328        assertEquals("g = gcd(a,b)", c, g);
329
330        GenPolynomial<AlgebraicNumber<ModInteger>> x;
331        x = a.multiply(d).sum(b.multiply(e)).monic();
332        //System.out.println("x = " + x);
333        assertEquals("gcd(a,b) = a s + b t", c, x);
334
335
336        //System.out.println("g = " + g);
337        //System.out.println("h = " + h);
338        if (a.isZERO() || b.isZERO()) {
339            return;
340        }
341        try {
342            c = a.modInverse(b);
343            //System.out.println("c = " + c);
344            x = c.multiply(a).remainder(b).monic();
345            //System.out.println("x = " + x);
346            assertTrue("a invertible mod b", x.isUnit());
347        } catch (RuntimeException e) {
348            // dann halt nicht
349        }
350
351    }
352
353}