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}