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}