001 /*
002 * $Id: GaloisFieldTest.java 1255 2007-07-29 10:16:33Z kredel $
003 */
004
005 package edu.jas.poly;
006
007 import junit.framework.Test;
008 import junit.framework.TestCase;
009 import junit.framework.TestSuite;
010
011 //import edu.jas.arith.BigRational;
012 import edu.jas.arith.ModInteger;
013 import edu.jas.arith.ModIntegerRing;
014
015 import 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 */
024 public 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 }