001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import edu.jas.arith.ModLong; 012import edu.jas.arith.ModLongRing; 013import edu.jas.arith.PrimeList; 014import edu.jas.poly.ExpVector; 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 Evaluation algorithm tests with JUnit. 027 * @author Heinz Kredel 028 */ 029 030public class GCDModLongEvalTest 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>GCDModLongEvalTest</CODE> object. 043 * @param name String. 044 */ 045 public GCDModLongEvalTest(String name) { 046 super(name); 047 } 048 049 050 /** 051 */ 052 public static Test suite() { 053 TestSuite suite = new TestSuite(GCDModLongEvalTest.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<GenPolynomial<ModLong>> ar, br, cr, dr, er; 086 087 088 int rl = 3; 089 090 091 int kl = 4; 092 093 094 int ll = 5; 095 096 097 int el = 3; 098 099 100 float q = 0.3f; 101 102 103 @Override 104 protected void setUp() { 105 a = b = c = d = e = null; 106 ai = bi = ci = di = ei = null; 107 ar = br = cr = dr = er = null; 108 //mi = new ModLongRing(primes.get(0),true); 109 mi = new ModLongRing(19, true); 110 //mi = new ModLongRing(19*17,true); // failing tests 111 //mi = new ModLongRing(primes.get(0).multiply(primes.get(1)),false); // failing tests 112 //ufd = new GreatestCommonDivisorPrimitive<ModLong>(); 113 ufd = new GreatestCommonDivisorModEval<ModLong>(); 114 String[] vars = ExpVector.STDVARS(rl); 115 String[] cvars = ExpVector.STDVARS(rl - 1); 116 String[] rvars = new String[] { vars[rl - 1] }; 117 dfac = new GenPolynomialRing<ModLong>(mi, rl, to, vars); 118 cfac = new GenPolynomialRing<ModLong>(mi, rl - 1, to, cvars); 119 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to, rvars); 120 //System.out.println("mi = " + mi); 121 } 122 123 124 @Override 125 protected void tearDown() { 126 a = b = c = d = e = null; 127 ai = bi = ci = di = ei = null; 128 ar = br = cr = dr = er = null; 129 mi = null; 130 ufd = null; 131 dfac = null; 132 cfac = null; 133 rfac = null; 134 } 135 136 137 /** 138 * Test modular evaluation gcd. 139 */ 140 public void testModEvalGcd() { 141 //GreatestCommonDivisorAbstract<ModLong> ufd_me 142 // = new GreatestCommonDivisorModEval(); 143 144 for (int i = 0; i < 1; i++) { 145 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q); 146 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q); 147 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q); 148 c = c.multiply(dfac.univariate(0)); 149 //a = ufd.basePrimitivePart(a); 150 //b = ufd.basePrimitivePart(b); 151 152 if (a.isZERO() || b.isZERO() || c.isZERO()) { 153 // skip for this turn 154 continue; 155 } 156 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 157 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 158 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 159 160 a = a.multiply(c); 161 b = b.multiply(c); 162 //System.out.println("a = " + a); 163 //System.out.println("b = " + b); 164 165 d = ufd.gcd(a, b); 166 167 c = ufd.basePrimitivePart(c).abs(); 168 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(d, c); 169 //System.out.println("c = " + c); 170 //System.out.println("d = " + d); 171 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 172 173 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(a, d); 174 //System.out.println("e = " + e); 175 assertTrue("gcd(a,b) | a" + e, e.isZERO()); 176 177 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(b, d); 178 //System.out.println("e = " + e); 179 assertTrue("gcd(a,b) | b" + e, e.isZERO()); 180 } 181 } 182 183 184 /** 185 * Test base quotioent and remainder. 186 */ 187 public void testBaseQR() { 188 dfac = new GenPolynomialRing<ModLong>(mi, 1, to); 189 190 for (int i = 0; i < 5; i++) { 191 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q); 192 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q); 193 //a = ufd.basePrimitivePart(a).abs(); 194 //c = ufd.basePrimitivePart(c); 195 do { 196 ci = mi.random(kl * (i + 2)); 197 ci = ci.sum(mi.getONE()); 198 } while (ci.isZERO()); 199 200 //System.out.println("a = " + a); 201 //System.out.println("c = " + c); 202 //System.out.println("ci = " + ci); 203 204 if (a.isZERO() || c.isZERO()) { 205 // skip for this turn 206 continue; 207 } 208 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 209 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 210 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 211 212 b = a.multiply(c); 213 //System.out.println("b = " + b); 214 d = PolyUtil.<ModLong> baseSparsePseudoRemainder(b, c); 215 //System.out.println("d = " + d); 216 217 assertTrue("rem(ac,c) == 0", d.isZERO()); 218 219 b = a.multiply(ci); 220 //System.out.println("b = " + b); 221 d = b.divide(ci); 222 //System.out.println("d = " + d); 223 224 assertEquals("a == ac/c", a, d); 225 226 b = a.multiply(c); 227 //System.out.println("b = " + b); 228 d = PolyUtil.<ModLong> basePseudoDivide(b, c); 229 //System.out.println("d = " + d); 230 231 assertEquals("a == ac/c", a, d); 232 } 233 } 234 235 236 /** 237 * Test base content and primitive part. 238 */ 239 public void testBaseContentPP() { 240 for (int i = 0; i < 13; i++) { 241 c = dfac.random(kl * (i + 2), ll + 2 * i, el + i, q); 242 c = c.multiply(mi.random(kl * (i + 2))); 243 244 if (c.isZERO()) { 245 // skip for this turn 246 continue; 247 } 248 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 249 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 250 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 251 252 ci = ufd.baseContent(c); 253 d = ufd.basePrimitivePart(c); 254 //System.out.println("c = " + c); 255 //System.out.println("ci = " + ci); 256 //System.out.println("d = " + d); 257 258 a = d.multiply(ci); 259 assertEquals("c == cont(c)pp(c)", c, a); 260 } 261 } 262 263 264 /** 265 * Test base gcd. 266 */ 267 public void testBaseGcd() { 268 dfac = new GenPolynomialRing<ModLong>(mi, 1, to); 269 270 for (int i = 0; i < 5; i++) { 271 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q); 272 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q); 273 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q); 274 //a = ufd.basePrimitivePart(a); 275 //b = ufd.basePrimitivePart(b); 276 //c = ufd.basePrimitivePart(c).abs(); 277 278 //System.out.println("a = " + a); 279 //System.out.println("b = " + b); 280 //System.out.println("c = " + c); 281 282 if (a.isZERO() || b.isZERO() || c.isZERO()) { 283 // skip for this turn 284 continue; 285 } 286 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 287 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 288 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 289 290 a = a.multiply(c); 291 b = b.multiply(c); 292 293 d = ufd.baseGcd(a, b); 294 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(d, c); 295 //System.out.println("d = " + d); 296 297 assertTrue("c | gcd(ac,bc) " + e, e.isZERO()); 298 } 299 } 300 301 302 /** 303 * Test recursive quotioent and remainder. 304 */ 305 public void testRecursiveQR() { 306 dfac = new GenPolynomialRing<ModLong>(mi, 2, to); 307 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to); 308 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to); 309 310 for (int i = 0; i < 5; i++) { 311 a = dfac.random(kl * (i + 1), ll + i, el + i, q); 312 a = ufd.basePrimitivePart(a).abs(); 313 314 c = dfac.random(kl * (i + 1), ll + i, el + i, q); 315 c = ufd.basePrimitivePart(a).abs(); 316 cr = PolyUtil.<ModLong> recursive(rfac, c); 317 318 c = cfac.random(kl * (i + 1), ll + 2 * i, el + 2 * i, q); 319 c = ufd.basePrimitivePart(c).abs(); 320 321 ar = PolyUtil.<ModLong> recursive(rfac, a); 322 //System.out.println("ar = " + ar); 323 //System.out.println("a = " + a); 324 //System.out.println("c = " + c); 325 //System.out.println("cr = " + cr); 326 327 if (cr.isZERO() || c.isZERO()) { 328 // skip for this turn 329 continue; 330 } 331 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 332 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 333 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 334 335 336 br = ar.multiply(cr); 337 //System.out.println("br = " + br); 338 dr = PolyUtil.<ModLong> recursiveSparsePseudoRemainder(br, cr); 339 //System.out.println("dr = " + dr); 340 d = PolyUtil.<ModLong> distribute(dfac, dr); 341 //System.out.println("d = " + d); 342 343 assertTrue("rem(ac,c) == 0", d.isZERO()); 344 345 br = ar.multiply(c); 346 //System.out.println("br = " + br); 347 dr = PolyUtil.<ModLong> recursiveDivide(br, c); 348 //System.out.println("dr = " + dr); 349 d = PolyUtil.<ModLong> distribute(dfac, dr); 350 //System.out.println("d = " + d); 351 352 assertEquals("a == ac/c", a, d); 353 } 354 } 355 356 357 /** 358 * Test recursive content and primitive part. 359 */ 360 public void testRecursiveContentPP() { 361 dfac = new GenPolynomialRing<ModLong>(mi, 2, to); 362 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to); 363 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to); 364 365 for (int i = 0; i < 3; i++) { 366 cr = rfac.random(kl * (i + 2), ll + 2 * i, el + i, q); 367 //System.out.println("cr = " + cr); 368 369 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 370 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 371 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 372 373 c = ufd.recursiveContent(cr); 374 dr = ufd.recursivePrimitivePart(cr); 375 //System.out.println("c = " + c); 376 //System.out.println("dr = " + dr); 377 378 ar = dr.multiply(c); 379 assertEquals("c == cont(c)pp(c)", cr, ar); 380 } 381 } 382 383 384 /** 385 * Test recursive gcd. 386 */ 387 public void testRecursiveGCD() { 388 dfac = new GenPolynomialRing<ModLong>(mi, 2, to); 389 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to); 390 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to); 391 392 for (int i = 0; i < 2; i++) { 393 ar = rfac.random(kl, ll, el + i, q); 394 br = rfac.random(kl, ll, el, q); 395 cr = rfac.random(kl, ll, el, q); 396 //System.out.println("ar = " + ar); 397 //System.out.println("br = " + br); 398 //System.out.println("cr = " + cr); 399 400 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 401 // skip for this turn 402 continue; 403 } 404 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 405 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 406 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 407 408 ar = ar.multiply(cr); 409 br = br.multiply(cr); 410 //System.out.println("ar = " + ar); 411 //System.out.println("br = " + br); 412 413 dr = ufd.recursiveUnivariateGcd(ar, br); 414 //System.out.println("dr = " + dr); 415 416 er = PolyUtil.<ModLong> recursiveSparsePseudoRemainder(dr, cr); 417 //System.out.println("er = " + er); 418 419 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 420 } 421 } 422 423 424 /** 425 * Test arbitrary recursive gcd. 426 */ 427 public void testArbitraryRecursiveGCD() { 428 dfac = new GenPolynomialRing<ModLong>(mi, 2, to); 429 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to); 430 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to); 431 432 for (int i = 0; i < 2; i++) { 433 ar = rfac.random(kl, ll, el + i, q); 434 br = rfac.random(kl, ll, el, q); 435 cr = rfac.random(kl, ll, el, q); 436 //System.out.println("ar = " + ar); 437 //System.out.println("br = " + br); 438 //System.out.println("cr = " + cr); 439 440 if (ar.isZERO() || br.isZERO() || cr.isZERO()) { 441 // skip for this turn 442 continue; 443 } 444 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0); 445 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 446 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 447 448 ar = ar.multiply(cr); 449 br = br.multiply(cr); 450 //System.out.println("ar = " + ar); 451 //System.out.println("br = " + br); 452 453 dr = ufd.recursiveGcd(ar, br); 454 //System.out.println("dr = " + dr); 455 456 er = PolyUtil.<ModLong> recursiveSparsePseudoRemainder(dr, cr); 457 //System.out.println("er = " + er); 458 459 assertTrue("c | gcd(ac,bc) " + er, er.isZERO()); 460 } 461 } 462 463 464 /** 465 * Test content and primitive part. 466 */ 467 public void testContentPP() { 468 dfac = new GenPolynomialRing<ModLong>(mi, 3, to); 469 470 for (int i = 0; i < 3; i++) { 471 c = dfac.random(kl * (i + 2), ll + 2 * i, el + i, q); 472 //System.out.println("cr = " + cr); 473 if (c.isZERO()) { 474 continue; 475 } 476 477 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 478 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 479 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 480 481 a = ufd.content(c); 482 e = a.extend(dfac, 0, 0L); 483 b = ufd.primitivePart(c); 484 //System.out.println("c = " + c); 485 //System.out.println("a = " + a); 486 //System.out.println("e = " + e); 487 //System.out.println("b = " + b); 488 489 d = e.multiply(b); 490 assertEquals("c == cont(c)pp(c)", d, c); 491 } 492 } 493 494 495 /** 496 * Test gcd 3 variables. 497 */ 498 public void testGCD3() { 499 dfac = new GenPolynomialRing<ModLong>(mi, 3, to); 500 501 for (int i = 0; i < 4; i++) { 502 a = dfac.random(kl, ll, el + i, q); 503 b = dfac.random(kl, ll, el, q); 504 c = dfac.random(kl, ll, el, q); 505 //System.out.println("a = " + a); 506 //System.out.println("b = " + b); 507 //System.out.println("c = " + c); 508 509 if (a.isZERO() || b.isZERO() || c.isZERO()) { 510 // skip for this turn 511 continue; 512 } 513 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 514 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 515 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 516 517 a = a.multiply(c); 518 b = b.multiply(c); 519 //System.out.println("a = " + a); 520 //System.out.println("b = " + b); 521 522 d = ufd.gcd(a, b); 523 //System.out.println("d = " + d); 524 525 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(d, c); 526 //System.out.println("e = " + e); 527 528 assertTrue("c | gcd(ac,bc): c = " + c + ", d = " + d + ", " + e, e.isZERO()); 529 } 530 } 531 532 533 /** 534 * Test gcd. 535 */ 536 public void testGCD() { 537 // dfac = new GenPolynomialRing<ModLong>(mi,3,to); 538 539 for (int i = 0; i < 1; i++) { 540 a = dfac.random(kl, ll, el, q); 541 b = dfac.random(kl, ll, el, q); 542 c = dfac.random(kl, ll, el, q); 543 //System.out.println("a = " + a); 544 //System.out.println("b = " + b); 545 //System.out.println("c = " + c); 546 547 if (a.isZERO() || b.isZERO() || c.isZERO()) { 548 // skip for this turn 549 continue; 550 } 551 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 552 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 553 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 554 555 a = a.multiply(c); 556 b = b.multiply(c); 557 //System.out.println("a = " + a); 558 //System.out.println("b = " + b); 559 560 d = ufd.gcd(a, b); 561 //System.out.println("d = " + d); 562 563 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(d, c); 564 //System.out.println("e = " + e); 565 assertTrue("c | gcd(ac,bc) " + e + ", " + c, e.isZERO()); 566 567 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(a, d); 568 //System.out.println("e = " + e); 569 assertTrue("gcd(a,b) | a " + e + ", " + d, e.isZERO()); 570 571 e = PolyUtil.<ModLong> baseSparsePseudoRemainder(b, d); 572 //System.out.println("e = " + e); 573 assertTrue("gcd(a,b) | b " + e + ", " + d, e.isZERO()); 574 } 575 } 576 577 578 /** 579 * Test lcm. 580 */ 581 public void testLCM() { 582 dfac = new GenPolynomialRing<ModLong>(mi, 3, to); 583 584 for (int i = 0; i < 1; i++) { 585 a = dfac.random(kl, ll, el, q); 586 b = dfac.random(kl, ll, el, q); 587 c = dfac.random(kl, 3, 2, q); 588 //System.out.println("a = " + a); 589 //System.out.println("b = " + b); 590 //System.out.println("c = " + c); 591 592 if (a.isZERO() || b.isZERO() || c.isZERO()) { 593 // skip for this turn 594 continue; 595 } 596 assertTrue("length( a" + i + " ) <> 0", a.length() > 0); 597 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() ); 598 //assertTrue(" not isONE( c"+i+" )", !c.isONE() ); 599 600 a = a.multiply(c); 601 b = b.multiply(c); 602 603 c = ufd.gcd(a, b); 604 //System.out.println("c = " + c); 605 606 d = ufd.lcm(a, b); 607 //System.out.println("d = " + d); 608 609 e = c.multiply(d); 610 //System.out.println("e = " + e); 611 c = a.multiply(b); 612 //System.out.println("c = " + c); 613 614 assertEquals("ab == gcd(a,b)lcm(ab)", c, e); 615 } 616 } 617 618 619 /** 620 * Test co-prime factors. 621 */ 622 public void testCoPrime() { 623 624 dfac = new GenPolynomialRing<ModLong>(mi, 3, to); 625 626 a = dfac.random(kl, 3, 2, q); 627 b = dfac.random(kl, 3, 2, q); 628 c = dfac.random(kl, 3, 2, q); 629 //System.out.println("a = " + a); 630 //System.out.println("b = " + b); 631 //System.out.println("c = " + c); 632 633 if (a.isZERO() || b.isZERO() || c.isZERO()) { 634 // skip for this turn 635 return; 636 } 637 assertTrue("length( a ) <> 0", a.length() > 0); 638 639 d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c); 640 e = a.multiply(b).multiply(c); 641 //System.out.println("d = " + d); 642 //System.out.println("c = " + c); 643 644 List<GenPolynomial<ModLong>> F = new ArrayList<GenPolynomial<ModLong>>(5); 645 F.add(d); 646 F.add(a); 647 F.add(b); 648 F.add(c); 649 F.add(e); 650 651 List<GenPolynomial<ModLong>> P = ufd.coPrime(F); 652 //System.out.println("F = " + F); 653 //System.out.println("P = " + P); 654 655 assertTrue("is co-prime ", ufd.isCoPrime(P)); 656 assertTrue("is co-prime of ", ufd.isCoPrime(P, F)); 657 658 659 //P = ufd.coPrimeSquarefree(F); 660 //System.out.println("F = " + F); 661 //System.out.println("P = " + P); 662 //assertTrue("is co-prime ", ufd.isCoPrime(P) ); 663 //assertTrue("is co-prime of ", ufd.isCoPrime(P,F) ); 664 665 666 P = ufd.coPrimeRec(F); 667 //System.out.println("F = " + F); 668 //System.out.println("P = " + P); 669 670 assertTrue("is co-prime ", ufd.isCoPrime(P)); 671 assertTrue("is co-prime of ", ufd.isCoPrime(P, F)); 672 } 673 674}