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