Source code

001/*
002 * $Id: GFGenPolynomialTest.java 4071 2012-07-27 19:59:38Z kredel $
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    //private final static int bitlen = 100;
051
052    GenPolynomialRing<AlgebraicNumber<ModInteger>> fac;
053
054
055    AlgebraicNumberRing<ModInteger> cfac;
056
057
058    GenPolynomial<AlgebraicNumber<ModInteger>> a;
059
060
061    GenPolynomial<AlgebraicNumber<ModInteger>> b;
062
063
064    GenPolynomial<AlgebraicNumber<ModInteger>> c;
065
066
067    GenPolynomial<AlgebraicNumber<ModInteger>> d;
068
069
070    GenPolynomial<AlgebraicNumber<ModInteger>> e;
071
072
073    int rl = 7;
074
075
076    int kl = 10;
077
078
079    int ll = 8;
080
081
082    int el = 5;
083
084
085    float q = 0.5f;
086
087
088    protected long getPrime() {
089        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
090        for (int i = 1; i < 60; i++) {
091            prime *= 2;
092        }
093        prime -= 93;
094        //System.out.println("prime = " + prime);
095        return prime;
096    }
097
098
099    @Override
100    protected void setUp() {
101        a = b = c = d = e = null;
102        long prime = getPrime();
103        ModIntegerRing r = new ModIntegerRing(prime);
104        // univariate minimal polynomial
105        GenPolynomialRing<ModInteger> mfac = new GenPolynomialRing<ModInteger>(r, 1);
106        GenPolynomial<ModInteger> modul = mfac.random(5);
107        while (modul.isZERO() || modul.isUnit() || modul.isConstant()) {
108            modul = mfac.random(5);
109        }
110        cfac = new AlgebraicNumberRing<ModInteger>(modul.monic());
111        fac = new GenPolynomialRing<AlgebraicNumber<ModInteger>>(cfac, rl);
112    }
113
114
115    @Override
116    protected void tearDown() {
117        a = b = c = d = e = null;
118        fac = null;
119    }
120
121
122    /**
123     * Test constructor and toString.
124     * 
125     */
126    public void testConstruction() {
127        c = fac.getONE();
128        //System.out.println("c = " + c);
129        assertTrue("length( c ) = 1", c.length() == 1);
130        assertTrue("isZERO( c )c" + c, !c.isZERO());
131        assertTrue("isONE( c ) " + c, c.isONE());
132
133        d = fac.getZERO();
134        //System.out.println("d = " + d);
135        assertTrue("length( d ) = 0", d.length() == 0);
136        assertTrue("isZERO( d )", d.isZERO());
137        assertTrue("isONE( d )", !d.isONE());
138    }
139
140
141    /**
142     * Test random polynomial.
143     * 
144     */
145    public void testRandom() {
146        for (int i = 0; i < 7; i++) {
147            a = fac.random(ll + i);
148            //System.out.println("a = " + a);
149
150            // fac.random(rl+i, kl*(i+1), ll+2*i, el+i, q );
151            assertTrue("length( a" + i + " ) <> 0", a.length() >= 0);
152            assertTrue(" not isZERO( a" + i + " )", !a.isZERO());
153            assertTrue(" not isONE( a" + i + " )", !a.isONE());
154        }
155    }
156
157
158    /**
159     * Test addition.
160     * 
161     */
162    public void testAddition() {
163
164        a = fac.random(ll);
165        b = fac.random(ll);
166
167        c = a.sum(b);
168        d = c.subtract(b);
169        assertEquals("a+b-b = a", a, d);
170
171        c = fac.random(ll);
172
173        ExpVector u = ExpVector.EVRAND(rl, el, q);
174        AlgebraicNumber<ModInteger> x = cfac.random(kl);
175
176        b = new GenPolynomial<AlgebraicNumber<ModInteger>>(fac, x, u);
177        c = a.sum(b);
178        d = a.sum(x, u);
179        assertEquals("a+p(x,u) = a+(x,u)", c, d);
180
181        c = a.subtract(b);
182        d = a.subtract(x, u);
183        assertEquals("a-p(x,u) = a-(x,u)", c, d);
184
185        a = new GenPolynomial<AlgebraicNumber<ModInteger>>(fac);
186        b = new GenPolynomial<AlgebraicNumber<ModInteger>>(fac, x, u);
187        c = b.sum(a);
188        d = a.sum(x, u);
189        assertEquals("a+p(x,u) = a+(x,u)", c, d);
190
191        c = a.subtract(b);
192        d = a.subtract(x, u);
193        assertEquals("a-p(x,u) = a-(x,u)", c, d);
194
195
196        c = fac.random(ll);
197        d = c.sum(a.sum(b));
198        e = c.sum(a).sum(b);
199        assertEquals("c+(a+b) = (c+a)+b", d, e);
200
201        c = a.sum(fac.getZERO());
202        d = a.subtract(fac.getZERO());
203        assertEquals("a+0 = a-0", c, d);
204
205        c = fac.getZERO().sum(a);
206        d = fac.getZERO().subtract(a.negate());
207        assertEquals("0+a = 0+(-a)", c, d);
208    }
209
210
211    /**
212     * Test object multiplication.
213     * 
214     */
215
216    public void testMultiplication() {
217
218        a = fac.random(ll);
219        assertTrue("not isZERO( a )", !a.isZERO());
220
221        b = fac.random(ll);
222        assertTrue("not isZERO( b )", !b.isZERO());
223
224        c = b.multiply(a);
225        d = a.multiply(b);
226        assertTrue("not isZERO( c )", !c.isZERO());
227        assertTrue("not isZERO( d )", !d.isZERO());
228
229        //System.out.println("a = " + a);
230        //System.out.println("b = " + b);
231        e = d.subtract(c);
232        assertTrue("isZERO( a*b-b*a ) " + e, e.isZERO());
233
234        assertTrue("a*b = b*a", c.equals(d));
235        assertEquals("a*b = b*a", c, d);
236
237        c = fac.random(ll);
238        //System.out.println("c = " + c);
239        d = a.multiply(b.multiply(c));
240        e = (a.multiply(b)).multiply(c);
241
242        //System.out.println("d = " + d);
243        //System.out.println("e = " + e);
244
245        //System.out.println("d-e = " + d.subtract(c) );
246
247        assertEquals("a(bc) = (ab)c", d, e);
248        assertTrue("a(bc) = (ab)c", d.equals(e));
249
250        AlgebraicNumber<ModInteger> z = a.leadingBaseCoefficient();
251        //System.out.println("z = " + z);
252        if (z.isUnit()) {
253            AlgebraicNumber<ModInteger> x = z.inverse();
254            //System.out.println("x = " + x);
255            //System.out.println("a = " + a);
256            c = a.monic();
257            //System.out.println("c = " + c);
258            d = a.multiply(x);
259            //System.out.println("d = " + d);
260            assertEquals("a.monic() = a(1/ldcf(a))", c, d);
261        }
262
263        AlgebraicNumber<ModInteger> y = b.leadingBaseCoefficient();
264        if (y.isUnit()) {
265            y = y.inverse();
266            c = b.monic();
267            d = b.multiply(y);
268            assertEquals("b.monic() = b(1/ldcf(b))", c, d);
269
270            e = new GenPolynomial<AlgebraicNumber<ModInteger>>(fac, y);
271            d = b.multiply(e);
272            assertEquals("b.monic() = b(1/ldcf(b))", c, d);
273
274            d = e.multiply(b);
275            assertEquals("b.monic() = (1/ldcf(b))*b", c, d);
276        }
277    }
278
279
280    /**
281     * Test distributive law.
282     * 
283     */
284    public void testDistributive() {
285        a = fac.random(ll);
286        b = fac.random(ll);
287        c = fac.random(ll);
288
289        d = a.multiply(b.sum(c));
290        e = a.multiply(b).sum(a.multiply(c));
291
292        assertEquals("a(b+c) = ab+ac", d, e);
293    }
294
295
296    /**
297     * Test object quotient and remainder.
298     * 
299     */
300
301    public void testQuotRem1() {
302
303        fac = new GenPolynomialRing<AlgebraicNumber<ModInteger>>(cfac, 1);
304
305        a = fac.random(ll).monic();
306        assertTrue("not isZERO( a )", !a.isZERO());
307
308        b = fac.random(ll).monic();
309        assertTrue("not isZERO( b )", !b.isZERO());
310
311        GenPolynomial<AlgebraicNumber<ModInteger>> g = fac.random(ll).monic();
312        assertTrue("not isZERO( g )", !g.isZERO());
313        g = fac.getONE();
314        a = a.multiply(g);
315        b = b.multiply(g);
316        //System.out.println("a = " + a);
317        //System.out.println("b = " + b);
318        //System.out.println("g = " + g);
319
320        GenPolynomial<AlgebraicNumber<ModInteger>>[] qr;
321        qr = b.divideAndRemainder(a);
322        c = qr[0];
323        d = qr[1];
324        //System.out.println("q = " + c);
325        //System.out.println("r = " + d);
326        e = c.multiply(a).sum(d);
327        assertEquals("b = q a + r", b, e);
328
329        qr = a.divideAndRemainder(b);
330        c = qr[0];
331        d = qr[1];
332        //System.out.println("q = " + c);
333        //System.out.println("r = " + d);
334        e = c.multiply(b).sum(d);
335        assertEquals("a = q b + r", a, e);
336
337
338        // gcd tests -------------------------------
339        c = a.gcd(b);
340        //System.out.println("gcd = " + c);
341        assertTrue("a mod gcd(a,b) = 0", a.remainder(c).isZERO());
342        assertTrue("b mod gcd(a,b) = 0", b.remainder(c).isZERO());
343        assertEquals("g = gcd(a,b)", c, g);
344
345
346        GenPolynomial<AlgebraicNumber<ModInteger>>[] gst;
347        gst = a.egcd(b);
348        //System.out.println("egcd = " + gst[0]);
349        //System.out.println(", s = " + gst[1] + ", t = " + gst[2]);
350        c = gst[0];
351        d = gst[1];
352        e = gst[2];
353        assertEquals("g = gcd(a,b)", c, g);
354
355        GenPolynomial<AlgebraicNumber<ModInteger>> x;
356        x = a.multiply(d).sum(b.multiply(e)).monic();
357        //System.out.println("x = " + x);
358        assertEquals("gcd(a,b) = a s + b t", c, x);
359
360
361        //System.out.println("g = " + g);
362        //System.out.println("h = " + h);
363        if (a.isZERO() || b.isZERO()) {
364            return;
365        }
366        try {
367            c = a.modInverse(b);
368            //System.out.println("c = " + c);
369            x = c.multiply(a).remainder(b).monic();
370            //System.out.println("x = " + x);
371            assertTrue("a invertible mod b", x.isUnit());
372        } catch (RuntimeException e) {
373            // dann halt nicht
374        }
375
376    }
377
378}