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