001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import edu.jas.arith.BigInteger; 012import edu.jas.arith.ModLong; 013import edu.jas.arith.ModLongRing; 014import edu.jas.arith.PrimeList; 015import edu.jas.poly.GenPolynomial; 016import edu.jas.poly.GenPolynomialRing; 017import edu.jas.poly.PolyUtil; 018import edu.jas.poly.TermOrder; 019 020import junit.framework.Test; 021import junit.framework.TestCase; 022import junit.framework.TestSuite; 023 024 025/** 026 * GCD Modular algorithm tests with JUnit. 027 * @author Heinz Kredel 028 */ 029 030public class GCDModLongTest extends TestCase { 031 032 033 /** 034 * main. 035 */ 036 public static void main(String[] args) { 037 junit.textui.TestRunner.run(suite()); 038 } 039 040 041 /** 042 * Constructs a <CODE>GCDModularTest</CODE> object. 043 * @param name String. 044 */ 045 public GCDModLongTest(String name) { 046 super(name); 047 } 048 049 050 /** 051 */ 052 public static Test suite() { 053 TestSuite suite = new TestSuite(GCDModLongTest.class); 054 return suite; 055 } 056 057 058 GreatestCommonDivisorAbstract<ModLong> ufd; 059 060 061 TermOrder to = new TermOrder(TermOrder.INVLEX); 062 063 064 GenPolynomialRing<ModLong> dfac; 065 066 067 GenPolynomialRing<ModLong> cfac; 068 069 070 GenPolynomialRing<GenPolynomial<ModLong>> rfac; 071 072 073 PrimeList primes = new PrimeList(); 074 075 076 ModLongRing mi; 077 078 079 ModLong ai, bi, ci, di, ei; 080 081 082 GenPolynomial<ModLong> a, b, c, d, e; 083 084 085 GenPolynomial<ModLong> ac; 086 087 088 GenPolynomial<ModLong> bc; 089 090 091 GenPolynomial<GenPolynomial<ModLong>> ar, br, cr, dr, er; 092 093 094 GenPolynomial<GenPolynomial<ModLong>> arc; 095 096 097 GenPolynomial<GenPolynomial<ModLong>> brc; 098 099 100 int rl = 5; 101 102 103 int kl = 4; 104 105 106 int ll = 5; 107 108 109 int el = 3; 110 111 112 float q = 0.3f; 113 114 115 @Override 116 protected void setUp() { 117 a = b = c = d = e = null; 118 ai = bi = ci = di = ei = null; 119 ar = br = cr = dr = er = null; 120 //mi = new ModLongRing(primes.get(0), true); 121 mi = new ModLongRing(5L, true); 122 ufd = new GreatestCommonDivisorPrimitive<ModLong>(); 123 dfac = new GenPolynomialRing<ModLong>(mi, rl, to); 124 cfac = new GenPolynomialRing<ModLong>(mi, rl - 1, to); 125 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to); 126 } 127 128 129 @Override 130 protected void tearDown() { 131 a = b = c = d = e = null; 132 ai = bi = ci = di = ei = null; 133 ar = br = cr = dr = er = null; 134 ufd = null; 135 dfac = null; 136 cfac = null; 137 rfac = null; 138 } 139 140 141 /** 142 * Test modular algorithm gcd with modular evaluation recursive algorithm. 143 */ 144 public void testModularEvaluationGcd() { 145 GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular<ModLong>(); // dummy type 146 147 GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorPrimitive<BigInteger>(); 148 149 GenPolynomial<BigInteger> a; 150 GenPolynomial<BigInteger> b; 151 GenPolynomial<BigInteger> c; 152 GenPolynomial<BigInteger> d; 153 GenPolynomial<BigInteger> e; 154 155 GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(), 3, to); 156 157 for (int i = 0; i < 2; i++) { 158 a = dfac.random(kl, ll + i, el + i, q); 159 b = dfac.random(kl, ll + i, el + i, q); 160 c = dfac.random(kl, ll + i, el + i, q); 161 c = c.multiply(dfac.univariate(0)); 162 //a = ufd.basePrimitivePart(a); 163 //b = ufd.basePrimitivePart(b); 164 165 if (a.isZERO() || b.isZERO() || c.isZERO()) { 166 // skip for this turn 167 continue; 168 } 169 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 170 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 171 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 172 173 a = a.multiply(c); 174 b = b.multiply(c); 175 176 //System.out.println("a = " + a); 177 //System.out.println("b = " + b); 178 179 d = ufd_m.gcd(a, b); 180 181 c = ufd.basePrimitivePart(c).abs(); 182 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(d, c); 183 //System.out.println("c = " + c); 184 //System.out.println("d = " + d); 185 186 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 187 188 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, d); 189 //System.out.println("e = " + e); 190 assertTrue("gcd(a,b) | a" + e, e.isZERO()); 191 192 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(b, d); 193 //System.out.println("e = " + e); 194 assertTrue("gcd(a,b) | b" + e, e.isZERO()); 195 } 196 } 197 198 199 /** 200 * Test modular algorithm gcd with simple PRS recursive algorithm. 201 */ 202 public void testModularSimpleGcd() { 203 GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular<ModLong>(true); // dummy type 204 205 GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorPrimitive<BigInteger>(); 206 207 GenPolynomial<BigInteger> a; 208 GenPolynomial<BigInteger> b; 209 GenPolynomial<BigInteger> c; 210 GenPolynomial<BigInteger> d; 211 GenPolynomial<BigInteger> e; 212 213 GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(), 3, to); 214 215 for (int i = 0; i < 1; i++) { 216 a = dfac.random(kl, ll + i, el + i, q); 217 b = dfac.random(kl, ll + i, el + i, q); 218 c = dfac.random(kl, ll + i, el + i, q); 219 c = c.multiply(dfac.univariate(0)); 220 //a = ufd.basePrimitivePart(a); 221 //b = ufd.basePrimitivePart(b); 222 223 if (a.isZERO() || b.isZERO() || c.isZERO()) { 224 // skip for this turn 225 continue; 226 } 227 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 228 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 229 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 230 231 a = a.multiply(c); 232 b = b.multiply(c); 233 234 //System.out.println("a = " + a); 235 //System.out.println("b = " + b); 236 237 d = ufd_m.gcd(a, b); 238 239 c = ufd.basePrimitivePart(c).abs(); 240 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(d, c); 241 //System.out.println("c = " + c); 242 //System.out.println("d = " + d); 243 244 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 245 246 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, d); 247 //System.out.println("e = " + e); 248 assertTrue("gcd(a,b) | a" + e, e.isZERO()); 249 250 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(b, d); 251 //System.out.println("e = " + e); 252 assertTrue("gcd(a,b) | b" + e, e.isZERO()); 253 } 254 } 255 256 257 /** 258 * Test recursive content and primitive part, modular coefficients. 259 */ 260 public void testRecursiveContentPPmodular() { 261 dfac = new GenPolynomialRing<ModLong>(mi, 2, to); 262 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to); 263 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to); 264 265 GreatestCommonDivisorAbstract<ModLong> ufd = new GreatestCommonDivisorPrimitive<ModLong>(); 266 267 for (int i = 0; i < 1; i++) { 268 a = cfac.random(kl, ll + 2 * i, el + i, q).monic(); 269 cr = rfac.random(kl * (i + 2), ll + 2 * i, el + i, q); 270 cr = PolyUtil.<ModLong> monic(cr); 271 //System.out.println("a = " + a); 272 //System.out.println("cr = " + cr); 273 //a = ufd.basePrimitivePart(a); 274 //b = distribute(dfac,cr); 275 //b = ufd.basePrimitivePart(b); 276 //cr = recursive(rfac,b); 277 //System.out.println("a = " + a); 278 //System.out.println("cr = " + cr); 279 280 cr = cr.multiply(a); 281 //System.out.println("cr = " + cr); 282 283 if (cr.isZERO()) { 284 // skip for this turn 285 continue; 286 } 287 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 288 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 289 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 290 291 c = ufd.recursiveContent(cr).monic(); 292 dr = ufd.recursivePrimitivePart(cr); 293 dr = PolyUtil.<ModLong> monic(dr); 294 //System.out.println("c = " + c); 295 //System.out.println("dr = " + dr); 296 297 //System.out.println("monic(a) = " + a.monic()); 298 //System.out.println("monic(c) = " + c.monic()); 299 300 ar = dr.multiply(c); 301 //System.out.println("ar = " + ar); 302 assertEquals("c == cont(c)pp(c)", cr, ar); 303 } 304 } 305 306 307 /** 308 * Test base gcd modular coefficients. 309 */ 310 public void testGCDbaseModular() { 311 dfac = new GenPolynomialRing<ModLong>(mi, 1, to); 312 313 GreatestCommonDivisorAbstract<ModLong> ufd = new GreatestCommonDivisorPrimitive<ModLong>(); 314 315 for (int i = 0; i < 1; i++) { 316 a = dfac.random(kl, ll, el + 3 + i, q).monic(); 317 b = dfac.random(kl, ll, el + 3 + i, q).monic(); 318 c = dfac.random(kl, ll, el + 3 + i, q).monic(); 319 //System.out.println("a = " + a); 320 //System.out.println("b = " + b); 321 //System.out.println("c = " + c); 322 323 if (a.isZERO() || b.isZERO() || c.isZERO()) { 324 // skip for this turn 325 continue; 326 } 327 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 328 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 329 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 330 331 ac = a.multiply(c); 332 bc = b.multiply(c); 333 //System.out.println("ac = " + ac); 334 //System.out.println("bc = " + bc); 335 336 //e = PolyUtil.<ModLong>baseSparsePseudoRemainder(ac,c); 337 //System.out.println("ac/c a = 0 " + e); 338 //assertTrue("ac/c-a != 0 " + e, e.isZERO() ); 339 //e = PolyUtil.<ModLong>baseSparsePseudoRemainder(bc,c); 340 //System.out.println("bc/c-b = 0 " + e); 341 //assertTrue("bc/c-b != 0 " + e, e.isZERO() ); 342 343 d = ufd.baseGcd(ac, bc); 344 d = d.monic(); // not required 345 //System.out.println("d = " + d); 346 347 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(d, c); 348 //System.out.println("e = " + e); 349 350 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 351 } 352 } 353 354 355 /** 356 * Test recursive gcd modular coefficients. 357 */ 358 public void testRecursiveGCDModular() { 359 dfac = new GenPolynomialRing<ModLong>(mi, 2, to); 360 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to); 361 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to); 362 363 // GreatestCommonDivisorAbstract<ModLong> ufd 364 // = new GreatestCommonDivisorPrimitive<ModLong>(); 365 366 for (int i = 0; i < 1; i++) { 367 ar = rfac.random(kl, 2, el + 2, q); 368 br = rfac.random(kl, 2, el + 2, q); 369 cr = rfac.random(kl, 2, el + 2, q); 370 ar = PolyUtil.<ModLong> monic(ar); 371 br = PolyUtil.<ModLong> monic(br); 372 cr = PolyUtil.<ModLong> monic(cr); 373 //System.out.println("ar = " + ar); 374 //System.out.println("br = " + br); 375 //System.out.println("cr = " + cr); 376 377 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 378 // skip for this turn 379 continue; 380 } 381 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 382 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 383 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 384 385 arc = ar.multiply(cr); 386 brc = br.multiply(cr); 387 //System.out.println("arc = " + arc); 388 //System.out.println("brc = " + brc); 389 390 //er = PolyUtil.<ModLong>recursiveSparsePseudoRemainder(arc,cr); 391 //System.out.println("ac/c-a = 0 " + er); 392 //assertTrue("ac/c-a != 0 " + er, er.isZERO() ); 393 //er = PolyUtil.<ModLong>recursiveSparsePseudoRemainder(brc,cr); 394 //System.out.println("bc/c-b = 0 " + er); 395 //assertTrue("bc/c-b != 0 " + er, er.isZERO() ); 396 397 dr = ufd.recursiveUnivariateGcd(arc, brc); 398 dr = PolyUtil.<ModLong> monic(dr); 399 //System.out.println("cr = " + cr); 400 //System.out.println("dr = " + dr); 401 402 er = PolyUtil.<ModLong> recursiveSparsePseudoRemainder(dr, cr); 403 //System.out.println("er = " + er); 404 405 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 406 } 407 } 408 409 410 /** 411 * Test arbitrary recursive gcd modular coefficients. 412 */ 413 public void testArbitraryRecursiveGCDModular() { 414 dfac = new GenPolynomialRing<ModLong>(mi, 2, to); 415 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to); 416 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to); 417 418 // GreatestCommonDivisorAbstract<ModLong> ufd 419 // = new GreatestCommonDivisorPrimitive<ModLong>(); 420 421 for (int i = 0; i < 1; i++) { 422 ar = rfac.random(kl, 2, el + 2, q); 423 br = rfac.random(kl, 2, el + 2, q); 424 cr = rfac.random(kl, 2, el + 2, q); 425 ar = PolyUtil.<ModLong> monic(ar); 426 br = PolyUtil.<ModLong> monic(br); 427 cr = PolyUtil.<ModLong> monic(cr); 428 //System.out.println("ar = " + ar); 429 //System.out.println("br = " + br); 430 //System.out.println("cr = " + cr); 431 432 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 433 // skip for this turn 434 continue; 435 } 436 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 437 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 438 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 439 440 arc = ar.multiply(cr); 441 brc = br.multiply(cr); 442 //System.out.println("arc = " + arc); 443 //System.out.println("brc = " + brc); 444 445 //er = PolyUtil.<ModLong>recursiveSparsePseudoRemainder(arc,cr); 446 //System.out.println("ac/c-a = 0 " + er); 447 //assertTrue("ac/c-a != 0 " + er, er.isZERO() ); 448 //er = PolyUtil.<ModLong>recursiveSparsePseudoRemainder(brc,cr); 449 //System.out.println("bc/c-b = 0 " + er); 450 //assertTrue("bc/c-b != 0 " + er, er.isZERO() ); 451 452 dr = ufd.recursiveGcd(arc, brc); 453 dr = PolyUtil.<ModLong> monic(dr); 454 //System.out.println("cr = " + cr); 455 //System.out.println("dr = " + dr); 456 457 er = PolyUtil.<ModLong> recursiveSparsePseudoRemainder(dr, cr); 458 //System.out.println("er = " + er); 459 460 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 461 } 462 } 463 464 465 /** 466 * Test gcd modular coefficients. 467 */ 468 public void testGcdModular() { 469 dfac = new GenPolynomialRing<ModLong>(mi, 4, to); 470 471 for (int i = 0; i < 1; i++) { 472 a = dfac.random(kl, ll, el + i, q).monic(); 473 b = dfac.random(kl, ll, el + i, q).monic(); 474 c = dfac.random(kl, ll, el + i, q).monic(); 475 //System.out.println("a = " + a); 476 //System.out.println("b = " + b); 477 //System.out.println("c = " + c); 478 479 if (a.isZERO() || b.isZERO() || c.isZERO()) { 480 // skip for this turn 481 continue; 482 } 483 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 484 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 485 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 486 487 ac = a.multiply(c); 488 bc = b.multiply(c); 489 //System.out.println("ac = " + ac); 490 //System.out.println("bc = " + bc); 491 492 //e = PolyUtil.<ModLong>baseSparsePseudoRemainder(ac,c); 493 //System.out.println("ac/c-a = 0 " + e); 494 //assertTrue("ac/c-a != 0 " + e, e.isZERO() ); 495 //e = PolyUtil.<ModLong>baseSparsePseudoRemainder(bc,c); 496 //System.out.println("bc/c-b = 0 " + e); 497 //assertTrue("bc/c-b != 0 " + e, e.isZERO() ); 498 499 d = ufd.gcd(ac, bc); 500 //System.out.println("d = " + d); 501 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(d, c); 502 //System.out.println("e = " + e); 503 //System.out.println("c = " + c); 504 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 505 506 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(ac, d); 507 //System.out.println("gcd(ac,bc) | ac " + e); 508 assertTrue("gcd(ac,bc) | ac " + e, e.isZERO()); 509 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(bc, d); 510 //System.out.println("gcd(ac,bc) | bc " + e); 511 assertTrue("gcd(ac,bc) | bc " + e, e.isZERO()); 512 } 513 } 514 515 516 /** 517 * Test co-prime factors. 518 */ 519 public void testCoPrime() { 520 dfac = new GenPolynomialRing<ModLong>(mi, 3, to); 521 522 a = dfac.random(kl, 3, 2, q); 523 b = dfac.random(kl, 3, 2, q); 524 c = dfac.random(kl, 3, 2, q); 525 //System.out.println("a = " + a); 526 //System.out.println("b = " + b); 527 //System.out.println("c = " + c); 528 529 if (a.isZERO() || b.isZERO() || c.isZERO()) { 530 // skip for this turn 531 return; 532 } 533 assertTrue("length( a ) <> 0", a.length() > 0); 534 535 d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c); 536 e = a.multiply(b).multiply(c); 537 //System.out.println("d = " + d); 538 //System.out.println("c = " + c); 539 540 List<GenPolynomial<ModLong>> F = new ArrayList<GenPolynomial<ModLong>>(5); 541 F.add(a); 542 F.add(b); 543 F.add(c); 544 F.add(d); 545 F.add(e); 546 547 List<GenPolynomial<ModLong>> P = ufd.coPrime(F); 548 //System.out.println("F = " + F); 549 //System.out.println("P = " + P); 550 551 assertTrue("is co-prime ", ufd.isCoPrime(P)); 552 assertTrue("is co-prime of ", ufd.isCoPrime(P, F)); 553 554 P = ufd.coPrimeRec(F); 555 //System.out.println("F = " + F); 556 //System.out.println("P = " + P); 557 558 assertTrue("is co-prime ", ufd.isCoPrime(P)); 559 assertTrue("is co-prime of ", ufd.isCoPrime(P, F)); 560 } 561 562}