Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.poly;
006
007import junit.framework.Test;
008import junit.framework.TestCase;
009import junit.framework.TestSuite;
010
011//import edu.jas.arith.BigRational;
012import edu.jas.arith.ModInteger;
013import edu.jas.arith.ModIntegerRing;
014
015import edu.jas.poly.GenPolynomial;
016
017//import edu.jas.structure.RingElem;
018
019
020/**
021 * Galois field tests with JUnit.
022 * @author Heinz Kredel
023 */
024public class GaloisFieldTest extends TestCase {
025
026
027    /**
028     * main
029     */
030    public static void main (String[] args) {
031        junit.textui.TestRunner.run( suite() );
032    }
033
034
035    /**
036     * Constructs a <CODE>GaloisFieldTest</CODE> object.
037     * @param name String.
038     */
039    public GaloisFieldTest(String name) {
040        super(name);
041    }
042
043
044    /**
045     */ 
046    public static Test suite() {
047        TestSuite suite= new TestSuite(GaloisFieldTest.class);
048        return suite;
049    }
050
051    AlgebraicNumberRing<ModInteger> fac;
052    GenPolynomialRing<ModInteger> mfac;
053
054    AlgebraicNumber< ModInteger > a, b, c, d, e;
055
056    int rl = 1; 
057    int kl = 10;
058    int ll = 15;
059    int el = ll;
060    float q = 0.5f;
061
062
063    protected long getPrime() {
064        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
065        for ( int i = 1; i < 60; i++ ) {
066            prime *= 2;
067        }
068        prime -= 93;
069        //System.out.println("prime = " + prime);
070        return prime;
071    }
072
073    
074    protected void setUp() {
075        a = b = c = d = e = null;
076        long prime = getPrime();
077        mfac = new GenPolynomialRing<ModInteger>( new ModIntegerRing(prime), 1 );
078        //System.out.println("mfac = " + mfac);
079        GenPolynomial<ModInteger> mo = mfac.random(kl,ll,el,q);
080        while ( mo.isConstant() ) {
081            mo = mfac.random(kl,ll,el,q);
082        }
083        fac = new AlgebraicNumberRing<ModInteger>( mo );
084        //System.out.println("fac = " + fac);
085    }
086
087    
088    protected void tearDown() {
089        a = b = c = d = e = null;
090        fac = null;
091    }
092
093
094    /**
095     * Test constructor and toString.
096     */
097    public void testConstruction() {
098        c = fac.getONE();
099        //System.out.println("c = " + c);
100        //System.out.println("c.getVal() = " + c.getVal());
101        assertTrue("length( c ) = 1", c.getVal().length() == 1);
102        assertTrue("isZERO( c )", !c.getVal().isZERO() );
103        assertTrue("isONE( c )", c.getVal().isONE() );
104
105        d = fac.getZERO();
106        //System.out.println("d = " + d);
107        //System.out.println("d.getVal() = " + d.getVal());
108        assertTrue("length( d ) = 0", d.getVal().length() == 0);
109        assertTrue("isZERO( d )", d.getVal().isZERO() );
110        assertTrue("isONE( d )", !d.getVal().isONE() );
111    }
112
113
114    /**
115     * Test random polynomial
116     */
117    public void testRandom() {
118        for (int i = 0; i < 7; i++) {
119            a = fac.random(ll+i);
120            //System.out.println("a = " + a);
121
122            // fac.random(kl*(i+1), ll+2*i, el+i, q );
123            assertTrue("length( a"+i+" ) <> 0", a.getVal().length() >= 0);
124            assertTrue(" not isZERO( a"+i+" )", !a.getVal().isZERO() );
125            assertTrue(" not isONE( a"+i+" )", !a.getVal().isONE() );
126        }
127    }
128
129
130    /**
131     * Test addition.
132     */
133    public void testAddition() {
134        a = fac.random(ll);
135        b = fac.random(ll);
136
137        c = a.sum(b);
138        d = c.subtract(b);
139        assertEquals("a+b-b = a",a,d);
140
141        c = fac.random(ll);
142        d = c.sum( a.sum(b) );
143        e = c.sum( a ).sum(b);
144        assertEquals("c+(a+b) = (c+a)+b",d,e);
145
146
147        c = a.sum( fac.getZERO() );
148        d = a.subtract( fac.getZERO() );
149        assertEquals("a+0 = a-0",c,d);
150
151        c = fac.getZERO().sum( a );
152        d = fac.getZERO().subtract( a.negate() );
153        assertEquals("0+a = 0+(-a)",c,d);
154    }
155
156
157    /**
158     * Test object multiplication.
159     */
160    public void testMultiplication() {
161        a = fac.random(ll);
162        assertTrue("not isZERO( a )", !a.isZERO() );
163
164        b = fac.random(ll);
165        assertTrue("not isZERO( b )", !b.isZERO() );
166
167        c = b.multiply(a);
168        d = a.multiply(b);
169        assertTrue("not isZERO( c )", !c.isZERO() );
170        assertTrue("not isZERO( d )", !d.isZERO() );
171
172        //System.out.println("a = " + a);
173        //System.out.println("b = " + b);
174        e = d.subtract(c);
175        assertTrue("isZERO( a*b-b*a ) " + e, e.isZERO() );
176
177        assertTrue("a*b = b*a", c.equals(d) );
178        assertEquals("a*b = b*a",c,d);
179
180        c = fac.random(ll);
181        //System.out.println("c = " + c);
182        d = a.multiply( b.multiply(c) );
183        e = (a.multiply(b)).multiply(c);
184
185        //System.out.println("d = " + d);
186        //System.out.println("e = " + e);
187
188        //System.out.println("d-e = " + d.subtract(c) );
189
190        assertEquals("a(bc) = (ab)c",d,e);
191        assertTrue("a(bc) = (ab)c", d.equals(e) );
192
193        c = a.multiply( fac.getONE() );
194        d = fac.getONE().multiply( a );
195        assertEquals("a*1 = 1*a",c,d);
196
197
198        c = a.inverse();
199        d = c.multiply(a);
200        //System.out.println("a = " + a);
201        //System.out.println("c = " + c);
202        //System.out.println("d = " + d);
203        assertEquals("a*1/a = 1",fac.getONE(),d);
204    }
205
206
207    /**
208     * Test distributive law.
209     */
210    public void testDistributive() {
211        a = fac.random( ll );
212        b = fac.random( ll );
213        c = fac.random( ll );
214
215        d = a.multiply( b.sum(c) );
216        e = a.multiply( b ).sum( a.multiply(c) );
217
218        assertEquals("a(b+c) = ab+ac",d,e);
219    }
220
221
222    /**
223     * Test chinese remainder.
224     */
225    public void testChineseRemainder() {
226        ModIntegerRing cfac;
227        GenPolynomialRing<ModInteger> m0fac;
228        GenPolynomial<ModInteger> x0;
229        GenPolynomial<ModInteger> x;
230        GenPolynomial<ModInteger> m0;
231        GenPolynomial<ModInteger> m1;
232        GenPolynomial<ModInteger> m01;
233        AlgebraicNumberRing<ModInteger> fac0;
234        AlgebraicNumberRing<ModInteger> fac1;
235        AlgebraicNumberRing<ModInteger> fac01;
236
237        cfac = new ModIntegerRing(19);
238        //System.out.println("cfac = " + cfac.getModul());
239        m0fac = new GenPolynomialRing<ModInteger>( cfac, 0 );
240        //System.out.println("m0fac = " + m0fac);
241        mfac = new GenPolynomialRing<ModInteger>( cfac, 1 );
242        //System.out.println("mfac = " + mfac);
243
244        x0 = m0fac.getONE();
245        //System.out.println("x0 = " + x0);
246        x = x0.extend(mfac,0,1);
247        //System.out.println("x  = " + x);
248
249        m0 = mfac.fromInteger(2);
250        m1 = mfac.fromInteger(5);
251        //System.out.println("m0 = " + m0);
252        //System.out.println("m1 = " + m1);
253
254        m0 = x.subtract(m0);
255        m1 = x.subtract(m1);
256        //System.out.println("m0 = " + m0);
257        //System.out.println("m1 = " + m1);
258
259        m01 = m0.multiply(m1);
260        //System.out.println("m01 = " + m01);
261
262        fac0 = new AlgebraicNumberRing<ModInteger>( m0, true );
263        fac1 = new AlgebraicNumberRing<ModInteger>( m1, true );
264        fac01 = new AlgebraicNumberRing<ModInteger>( m01, false );
265        //System.out.println("fac0 = " + fac0);
266        //System.out.println("fac1 = " + fac1);
267        //System.out.println("fac01 = " + fac01);
268
269        a = fac01.random( 9 );
270        //System.out.println("a = " + a);
271        b = new AlgebraicNumber<ModInteger>(fac0,a.getVal());
272        //System.out.println("b = " + b);
273        c = new AlgebraicNumber<ModInteger>(fac1,a.getVal());
274        //System.out.println("c = " + c);
275
276        d = new AlgebraicNumber<ModInteger>(fac1,m0);
277        //System.out.println("d = " + d);
278        d = d.inverse();
279        //System.out.println("d = " + d);
280
281        e = fac01.chineseRemainder(b,d,c);
282        //System.out.println("e = " + e);
283
284        assertEquals("cra(a mod (x-m0),a mod (x-m1)) = a (mod 19)",a,e);
285
286
287        cfac = new ModIntegerRing(getPrime());
288        //System.out.println("cfac = " + cfac.getModul());
289        m0fac = new GenPolynomialRing<ModInteger>( cfac, 0 );
290        //System.out.println("m0fac = " + m0fac);
291        mfac = new GenPolynomialRing<ModInteger>( cfac, 1 );
292        //System.out.println("mfac = " + mfac);
293
294        x0 = m0fac.getONE();
295        //System.out.println("x0 = " + x0);
296        x = x0.extend(mfac,0,1);
297        //System.out.println("x  = " + x);
298
299        m0 = mfac.fromInteger(21);
300        m1 = mfac.fromInteger(57);
301        //System.out.println("m0 = " + m0);
302        //System.out.println("m1 = " + m1);
303
304        m0 = x.subtract(m0);
305        m1 = x.subtract(m1);
306        //System.out.println("m0 = " + m0);
307        //System.out.println("m1 = " + m1);
308
309        m01 = m0.multiply(m1);
310        //System.out.println("m01 = " + m01);
311
312        fac0 = new AlgebraicNumberRing<ModInteger>( m0, true );
313        fac1 = new AlgebraicNumberRing<ModInteger>( m1, true );
314        fac01 = new AlgebraicNumberRing<ModInteger>( m01, false );
315        //System.out.println("fac0 = " + fac0);
316        //System.out.println("fac1 = " + fac1);
317        //System.out.println("fac01 = " + fac01);
318
319        for ( int i = 0; i < 5; i++ ) {
320            a = fac01.random( 9 );
321            //System.out.println("a = " + a);
322            b = new AlgebraicNumber<ModInteger>(fac0,a.getVal());
323            //System.out.println("b = " + b);
324            c = new AlgebraicNumber<ModInteger>(fac1,a.getVal());
325            //System.out.println("c = " + c);
326
327            d = new AlgebraicNumber<ModInteger>(fac1,m0);
328            //System.out.println("d = " + d);
329            d = d.inverse();
330            //System.out.println("d = " + d);
331
332            e = fac01.chineseRemainder(b,d,c);
333            //System.out.println("e = " + e);
334
335            assertEquals("cra(a mod (x-m0),a mod (x-m1)) = a (mod 2^60-93)",a,e);
336        }
337    }
338
339    /**
340     * Test interpolate, is chinese remainder special case.
341     */
342    public void testInterpolate() {
343        ModIntegerRing cfac;
344        GenPolynomialRing<ModInteger> m0fac;
345        GenPolynomial<ModInteger> x0;
346        GenPolynomial<ModInteger> x;
347        GenPolynomial<ModInteger> m0;
348        GenPolynomial<ModInteger> m1;
349        GenPolynomial<ModInteger> m01;
350        AlgebraicNumberRing<ModInteger> fac0;
351        AlgebraicNumberRing<ModInteger> fac1;
352        AlgebraicNumberRing<ModInteger> fac01;
353
354        ModInteger cm;
355        ModInteger ci;
356        ModInteger di;
357
358        cfac = new ModIntegerRing(19);
359        //System.out.println("cfac = " + cfac.getModul());
360        m0fac = new GenPolynomialRing<ModInteger>( cfac, 0 );
361        //System.out.println("m0fac = " + m0fac);
362        mfac = new GenPolynomialRing<ModInteger>( cfac, 1 );
363        //System.out.println("mfac = " + mfac);
364
365        x0 = m0fac.getONE();
366        //System.out.println("x0 = " + x0);
367        x = x0.extend(mfac,0,1);
368        //System.out.println("x  = " + x);
369
370        m0 = mfac.fromInteger(2);
371        m1 = mfac.fromInteger(5);
372        //System.out.println("m0 = " + m0);
373        //System.out.println("m1 = " + m1);
374
375        m0 = x.subtract(m0);
376        m1 = x.subtract(m1);
377        //System.out.println("m0 = " + m0);
378        //System.out.println("m1 = " + m1);
379
380        m01 = m0.multiply(m1);
381        //System.out.println("m01 = " + m01);
382
383        fac0 = new AlgebraicNumberRing<ModInteger>( m0, true );
384        fac1 = new AlgebraicNumberRing<ModInteger>( m1, true );
385        fac01 = new AlgebraicNumberRing<ModInteger>( m01, false );
386        //System.out.println("fac0 = " + fac0);
387        //System.out.println("fac1 = " + fac1);
388        //System.out.println("fac01 = " + fac01);
389
390        a = fac01.random( 9 );
391        //System.out.println("a = " + a);
392        b = new AlgebraicNumber<ModInteger>(fac0,a.getVal());
393        //System.out.println("b = " + b);
394        c = new AlgebraicNumber<ModInteger>(fac1,a.getVal());
395        //System.out.println("c = " + c);
396        cm = fac1.modul.trailingBaseCoefficient();
397        //System.out.println("cm = " + cm);
398        ci = c.val.trailingBaseCoefficient();
399        //System.out.println("ci = " + ci);
400
401
402        d = new AlgebraicNumber<ModInteger>(fac1,m0);
403        //System.out.println("d = " + d);
404        d = d.inverse();
405        //System.out.println("d = " + d);
406        di = d.val.leadingBaseCoefficient();
407        //System.out.println("di = " + di);
408
409        e = fac01.interpolate(b,di,cm,ci);
410        //System.out.println("e = " + e);
411
412        assertEquals("cra(a mod (x-m0),a mod (x-m1)) = a (mod 19)",a,e);
413
414        cfac = new ModIntegerRing(getPrime());
415        //System.out.println("cfac = " + cfac.getModul());
416        m0fac = new GenPolynomialRing<ModInteger>( cfac, 0 );
417        //System.out.println("m0fac = " + m0fac);
418        mfac = new GenPolynomialRing<ModInteger>( cfac, 1 );
419        //System.out.println("mfac = " + mfac);
420
421        x0 = m0fac.getONE();
422        //System.out.println("x0 = " + x0);
423        x = x0.extend(mfac,0,1);
424        //System.out.println("x  = " + x);
425
426        m0 = mfac.fromInteger(21);
427        m1 = mfac.fromInteger(57);
428        //System.out.println("m0 = " + m0);
429        //System.out.println("m1 = " + m1);
430
431        m0 = x.subtract(m0);
432        m1 = x.subtract(m1);
433        //System.out.println("m0 = " + m0);
434        //System.out.println("m1 = " + m1);
435
436        m01 = m0.multiply(m1);
437        //System.out.println("m01 = " + m01);
438
439        fac0 = new AlgebraicNumberRing<ModInteger>( m0, true );
440        fac1 = new AlgebraicNumberRing<ModInteger>( m1, true );
441        fac01 = new AlgebraicNumberRing<ModInteger>( m01, false );
442        //System.out.println("fac0 = " + fac0);
443        //System.out.println("fac1 = " + fac1);
444        //System.out.println("fac01 = " + fac01);
445
446        for ( int i = 0; i < 5; i++ ) {
447            a = fac01.random( 9 );
448            //System.out.println("a = " + a);
449            b = new AlgebraicNumber<ModInteger>(fac0,a.getVal());
450            //System.out.println("b = " + b);
451            c = new AlgebraicNumber<ModInteger>(fac1,a.getVal());
452            //System.out.println("c = " + c);
453            cm = fac1.modul.trailingBaseCoefficient();
454            //System.out.println("cm = " + cm);
455            ci = c.val.trailingBaseCoefficient();
456            //System.out.println("ci = " + ci);
457
458            d = new AlgebraicNumber<ModInteger>(fac1,m0);
459            //System.out.println("d = " + d);
460            d = d.inverse();
461            //System.out.println("d = " + d);
462            di = d.val.leadingBaseCoefficient();
463            //System.out.println("di = " + di);
464
465            e = fac01.interpolate(b,di,cm,ci);
466            //System.out.println("e = " + e);
467
468            assertEquals("cra(a mod (x-m0),a mod (x-m1)) = a (mod 2^60-93)",a,e);
469        }
470
471    }
472
473}