001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.List; 009import java.util.SortedMap; 010 011import junit.framework.Test; 012import junit.framework.TestCase; 013import junit.framework.TestSuite; 014 015 016import edu.jas.arith.BigInteger; 017import edu.jas.arith.ModInteger; 018import edu.jas.kern.ComputerThreads; 019import edu.jas.poly.ExpVector; 020import edu.jas.poly.GenPolynomial; 021import edu.jas.poly.GenPolynomialRing; 022import edu.jas.poly.TermOrder; 023import edu.jas.poly.TermOrderByName; 024 025 026/** 027 * Factor tests with JUnit. 028 * @author Heinz Kredel 029 */ 030 031public class FactorIntegerTest extends TestCase { 032 033 034 /** 035 * main. 036 */ 037 public static void main(String[] args) { 038 junit.textui.TestRunner.run(suite()); 039 } 040 041 042 /** 043 * Constructs a <CODE>FactorIntegerTest</CODE> object. 044 * @param name String. 045 */ 046 public FactorIntegerTest(String name) { 047 super(name); 048 } 049 050 051 /** 052 */ 053 public static Test suite() { 054 TestSuite suite = new TestSuite(FactorIntegerTest.class); 055 return suite; 056 } 057 058 059 int rl = 3; 060 061 062 int kl = 5; 063 064 065 int ll = 5; 066 067 068 int el = 5; 069 070 071 float q = 0.3f; 072 073 074 @Override 075 protected void setUp() { 076 } 077 078 079 @Override 080 protected void tearDown() { 081 ComputerThreads.terminate(); 082 } 083 084 085 /** 086 * Test dummy for Junit. 087 */ 088 public void testDummy() { 089 } 090 091 092 /** 093 * Test integer monic factorization. 094 */ 095 public void testIntegerMonicFactorization() { 096 TermOrder to = new TermOrder(TermOrder.INVLEX); 097 BigInteger cfac = new BigInteger(4); 098 BigInteger one = cfac.getONE(); 099 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, 1, to, 100 new String[] { "x" }); 101 FactorAbstract<BigInteger> fac = new FactorInteger<ModInteger>(); 102 103 for (int i = 1; i < 3; i++) { 104 int facs = 0; 105 GenPolynomial<BigInteger> a = null; //pfac.random(kl,ll*(i+1),el*(i+1),q); 106 GenPolynomial<BigInteger> b = pfac.random(kl * 2, ll * (i), el * (i + 1), q); 107 GenPolynomial<BigInteger> c = pfac.random(kl, ll * (i), el * (i + 2), q); 108 //b = pfac.parse("((x^2 + 1)*(x^2 - 111111111))"); 109 //c = pfac.parse("(x^3 - 222222)"); 110 if (b.isZERO() || c.isZERO()) { 111 continue; 112 } 113 if (c.degree() > 0) { 114 facs++; 115 } 116 if (b.degree() > 0) { 117 facs++; 118 } 119 if (!c.leadingBaseCoefficient().isUnit()) { 120 ExpVector e = c.leadingExpVector(); 121 c.doPutToMap(e, one); 122 } 123 if (!b.leadingBaseCoefficient().isUnit()) { 124 ExpVector e = b.leadingExpVector(); 125 b.doPutToMap(e, one); 126 } 127 a = c.multiply(b); 128 if (a.isConstant()) { 129 continue; 130 } 131 //GreatestCommonDivisorAbstract<BigInteger> engine = GCDFactory.getProxy(cfac); 132 //a = engine.basePrimitivePart(a); 133 // a = a.abs(); 134 //System.out.println("\na = " + a); 135 //System.out.println("b = " + b); 136 //System.out.println("c = " + c); 137 138 SortedMap<GenPolynomial<BigInteger>, Long> sm = fac.baseFactors(a); 139 //System.out.println("\na = " + a); 140 //System.out.println("b = " + b); 141 //System.out.println("c = " + c); 142 //System.out.println("sm = " + sm); 143 144 if (sm.size() >= facs) { 145 assertTrue("#facs < " + facs, sm.size() >= facs); 146 } else { 147 long sf = 0; 148 for (Long e : sm.values()) { 149 sf += e; 150 } 151 assertTrue("#facs < " + facs + ", " + b + " * " + c, sf >= facs); 152 } 153 154 boolean t = fac.isFactorization(a, sm); 155 //System.out.println("t = " + t); 156 assertTrue("prod(factor(a)) = a", t); 157 } 158 } 159 160 161 /** 162 * Test integer factorization. 163 */ 164 public void testIntegerFactorization() { 165 TermOrder to = new TermOrder(TermOrder.INVLEX); 166 BigInteger cfac = new BigInteger(4); 167 //BigInteger one = cfac.getONE(); 168 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, 1, to); 169 FactorAbstract<BigInteger> fac = new FactorInteger<ModInteger>(); 170 171 for (int i = 1; i < 2; i++) { 172 int facs = 0; 173 GenPolynomial<BigInteger> a = null; //pfac.random(kl,ll*(i+1),el*(i+1),q); 174 GenPolynomial<BigInteger> b = pfac.random(kl * 2, ll * (i), el * (i + 1), q); 175 GenPolynomial<BigInteger> c = pfac.random(kl, ll * (i), el * (i + 2), q); 176 if (b.isZERO() || c.isZERO()) { 177 continue; 178 } 179 if (c.degree() > 0) { 180 facs++; 181 } 182 if (b.degree() > 0) { 183 facs++; 184 } 185 a = c.multiply(b); 186 if (a.isConstant()) { 187 continue; 188 } 189 //GreatestCommonDivisorAbstract<BigInteger> engine = GCDFactory.getProxy(cfac); 190 //a = engine.basePrimitivePart(a); 191 // a = a.abs(); 192 //System.out.println("\na = " + a); 193 //System.out.println("b = " + b); 194 //System.out.println("c = " + c); 195 196 SortedMap<GenPolynomial<BigInteger>, Long> sm = fac.baseFactors(a); 197 //System.out.println("\na = " + a); 198 //System.out.println("b = " + b); 199 //System.out.println("c = " + c); 200 //System.out.println("sm = " + sm); 201 202 if (sm.size() >= facs) { 203 assertTrue("#facs < " + facs, sm.size() >= facs); 204 } else { 205 long sf = 0; 206 for (Long e : sm.values()) { 207 sf += e; 208 } 209 assertTrue("#facs < " + facs, sf >= facs); 210 } 211 212 boolean t = fac.isFactorization(a, sm); 213 //System.out.println("t = " + t); 214 assertTrue("prod(factor(a)) = a", t); 215 } 216 } 217 218 219 /** 220 * Test integer factorization irreducible polynomial. 221 */ 222 public void testIntegerFactorizationIrred() { 223 TermOrder to = new TermOrder(TermOrder.INVLEX); 224 BigInteger cfac = new BigInteger(4); 225 //BigInteger one = cfac.getONE(); 226 String[] vars = new String[] { "x" }; 227 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, 1, to, vars); 228 FactorAbstract<BigInteger> fac = new FactorInteger<ModInteger>(); 229 230 for (int i = 1; i < 2; i++) { 231 int facs = 0; 232 GenPolynomial<BigInteger> a = pfac.random(kl, ll * (i + 1), el * (i + 1), q); 233 a = pfac.parse("( x^8 - 40 x^6 + 352 x^4 - 960 x^2 + 576 )"); // Swinnerton-Dyer example 234 if (a.isConstant()) { 235 continue; 236 } 237 SortedMap<GenPolynomial<BigInteger>, Long> sm = fac.baseFactors(a); 238 //System.out.println("\na = " + a); 239 //System.out.println("sm = " + sm); 240 241 if (sm.size() >= 1) { 242 assertTrue("#facs < " + facs, sm.size() >= 1); 243 } 244 245 boolean t = fac.isFactorization(a, sm); 246 //System.out.println("t = " + t); 247 assertTrue("prod(factor(a)) = a", t); 248 } 249 } 250 251 252 /** 253 * Test bi-variate integer factorization. 254 */ 255 public void testBivariateIntegerFactorization() { 256 TermOrder to = new TermOrder(TermOrder.INVLEX); 257 BigInteger cfac = new BigInteger(1); 258 String[] vars = new String[] { "x", "y" }; 259 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, 2, to, vars); 260 //FactorAbstract<BigInteger> fac = new FactorInteger<ModInteger>(); 261 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 262 263 for (int i = 1; i < 2; i++) { 264 GenPolynomial<BigInteger> b = pfac.random(kl, 3, el, q / 2.0f); 265 GenPolynomial<BigInteger> c = pfac.random(kl, 2, el, q); 266 GenPolynomial<BigInteger> d = pfac.random(kl, 2, el, q); 267 b = pfac.parse(" ( x y^2 - 1 ) "); 268 c = pfac.parse(" ( 2 x y + 1 ) "); 269 d = pfac.parse(" ( y^4 + 3 x )"); 270 271 //b = pfac.parse(" ( y + x + 1 ) "); 272 //c = pfac.parse(" ( y ) "); 273 //d = pfac.parse(" ( 1 )"); 274 GenPolynomial<BigInteger> a; 275 a = b.multiply(c).multiply(d); 276 //System.out.println("a = " + a); 277 //System.out.println("b = " + b); 278 //System.out.println("c = " + c); 279 //System.out.println("d = " + d); 280 281 List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefreeHensel(a); 282 //System.out.println("sm = " + sm); 283 //sm = fac.factorsSquarefree(a); 284 //System.out.println("sm = " + sm); 285 286 boolean t = fac.isFactorization(a, sm); 287 //System.out.println("t = " + t); 288 assertTrue("prod(factor(a)) = a", t); 289 assertTrue("#facs < 3, sm = " + sm, sm.size() >= 3); 290 } 291 } 292 293 294 /** 295 * Test tri-variate integer factorization. 296 */ 297 public void ytestTrivariateIntegerFactorization() { 298 TermOrder to = new TermOrder(TermOrder.INVLEX); 299 BigInteger cfac = new BigInteger(1); 300 String[] vars = new String[] { "x", "y", "z" }; 301 //vars = new String[] { "x", "y"}; 302 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 303 //FactorAbstract<BigInteger> fac = new FactorInteger<ModInteger>(); 304 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 305 306 for (int i = 1; i < 2; i++) { 307 GenPolynomial<BigInteger> b = pfac.random(kl, 3, el, q / 2.0f); 308 GenPolynomial<BigInteger> c = pfac.random(kl, 2, el, q); 309 GenPolynomial<BigInteger> d = pfac.random(kl, 2, el, q); 310 b = pfac.parse(" ( 5 x y^2 - 1 ) "); 311 c = pfac.parse(" ( 2 x y z^2 + 1 ) "); 312 d = pfac.parse(" ( y^3 z + 3 x )"); 313 GenPolynomial<BigInteger> a; 314 a = b.multiply(c).multiply(d); 315 //System.out.println("a = " + a); 316 //System.out.println("b = " + b); 317 //System.out.println("c = " + c); 318 //System.out.println("d = " + d); 319 320 List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefreeHensel(a); 321 //System.out.println("sm = " + sm); 322 boolean t = fac.isFactorization(a, sm); 323 //System.out.println("t = " + t); 324 assertTrue("prod(factor(a)) = a", t); 325 assertTrue("#facs < 3, sm = " + sm, sm.size() >= 3); 326 327 //sm = fac.factorsSquarefree(a); 328 //System.out.println("sm = " + sm); 329 //t = fac.isFactorization(a, sm); 330 //System.out.println("t = " + t); 331 //assertTrue("prod(factor(a)) = a", t); 332 } 333 } 334 335 336 /** 337 * Test quad-variate integer factorization. 338 */ 339 public void ytestQuadvariateIntegerFactorization() { 340 TermOrder to = new TermOrder(TermOrder.INVLEX); 341 BigInteger cfac = new BigInteger(1); 342 String[] vars = new String[] { "x", "y", "z", "w" }; 343 //vars = new String[] { "x", "y", "z" }; 344 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 345 //FactorAbstract<BigInteger> fac = new FactorInteger<ModInteger>(); 346 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 347 348 for (int i = 1; i < 2; i++) { 349 GenPolynomial<BigInteger> b = pfac.random(kl, 3, el, q / 2.0f); 350 GenPolynomial<BigInteger> c = pfac.random(kl, 2, el, q); 351 GenPolynomial<BigInteger> d = pfac.random(kl, 2, el, q); 352 b = pfac.parse(" ( 5 x y^2 - 1 ) "); 353 c = pfac.parse(" ( 2 x z^2 + w^2 y ) "); 354 d = pfac.parse(" ( y^3 z + 7 x )"); 355 GenPolynomial<BigInteger> a; 356 a = b.multiply(c).multiply(d); 357 //System.out.println("a = " + a); 358 //System.out.println("b = " + b); 359 //System.out.println("c = " + c); 360 //System.out.println("d = " + d); 361 362 List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefreeHensel(a); 363 //System.out.println("sm = " + sm); 364 boolean t = fac.isFactorization(a, sm); 365 //System.out.println("t = " + t); 366 assertTrue("prod(factor(a)) = a", t); 367 assertTrue("#facs < 3, sm = " + sm, sm.size() >= 3); 368 369 //sm = fac.factorsSquarefree(a); 370 //System.out.println("sm = " + sm); 371 //t = fac.isFactorization(a, sm); 372 ////System.out.println("t = " + t); 373 //assertTrue("prod(factor(a)) = a", t); 374 } 375 } 376 377 378 /** 379 * Test multivariate integer factorization. 380 */ 381 public void testMultivariateIntegerFactorization() { 382 TermOrder to = new TermOrder(TermOrder.INVLEX); 383 BigInteger cfac = new BigInteger(1); 384 String[] vars = new String[] { "x", "y", "z" }; 385 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, to, vars); 386 FactorAbstract<BigInteger> fac = new FactorInteger<ModInteger>(); 387 388 for (int i = 1; i < 2; i++) { 389 GenPolynomial<BigInteger> b = pfac.random(kl, 3, el, q / 2.0f); 390 GenPolynomial<BigInteger> c = pfac.random(kl, 2, el, q); 391 b = pfac.parse("( z - y )"); 392 c = pfac.parse("( z + x )"); 393 GenPolynomial<BigInteger> a; 394 // if ( !a.leadingBaseCoefficient().isUnit()) { 395 // //continue; 396 // //ExpVector e = a.leadingExpVector(); 397 // //a.doPutToMap(e,cfac.getONE()); 398 // } 399 a = b.multiply(c); 400 //System.out.println("a = " + a); 401 //System.out.println("b = " + b); 402 //System.out.println("c = " + c); 403 404 SortedMap<GenPolynomial<BigInteger>, Long> sm = fac.factors(a); 405 //System.out.println("sm = " + sm); 406 boolean t = fac.isFactorization(a, sm); 407 //System.out.println("t = " + t); 408 assertTrue("prod(factor(a)) = a", t); 409 assertTrue("#facs < 2, sm = " + sm, sm.size() >= 2); 410 } 411 } 412 413 414 /** 415 * Test integer factorization, example 1 from Wang. 416 */ 417 public void testIntegerFactorizationEx1() { 418 TermOrder to = new TermOrder(TermOrder.INVLEX); 419 BigInteger cfac = new BigInteger(1); 420 String[] vars = new String[] { "x", "y", "z" }; 421 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 422 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 423 GenPolynomial<BigInteger> a, b, c, d; 424 425 // (z + xy + 10)(xz + y + 30)(yz + x + 20), 426 b = pfac.parse(" (z + x y + 10) "); 427 c = pfac.parse(" (x z + y + 30) "); 428 d = pfac.parse(" (y z + x + 20) "); 429 430 a = b.multiply(c).multiply(d); 431 //System.out.println("a = " + a); 432 //System.out.println("b = " + b); 433 //System.out.println("c = " + c); 434 //System.out.println("d = " + d); 435 436 //List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefreeHensel(a); 437 List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefree(a); 438 //System.out.println("sm = " + sm); 439 boolean t = fac.isFactorization(a, sm); 440 //System.out.println("t = " + t); 441 assertTrue("prod(factor(a)) = a", t); 442 assertTrue("#facs < 3, sm = " + sm, sm.size() >= 3); 443 } 444 445 446 /** 447 * Test integer factorization, example 2 from Wang. 448 */ 449 public void testIntegerFactorizationEx2() { 450 TermOrder to = new TermOrder(TermOrder.INVLEX); 451 BigInteger cfac = new BigInteger(1); 452 String[] vars = new String[] { "x", "y", "z" }; 453 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 454 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 455 GenPolynomial<BigInteger> a, b, c; 456 457 // (x^3(z + y) + z - 11) (x^(z^2 + y^2) + y + 90), 458 b = pfac.parse(" (x^3 (z + y) + z - 11) "); 459 c = pfac.parse(" (x^2 (z^2 + y^2) + y + 90) "); 460 461 a = b.multiply(c); 462 //System.out.println("a = " + a); 463 //System.out.println("b = " + b); 464 //System.out.println("c = " + c); 465 466 //List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefreeHensel(a); 467 List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefree(a); 468 //System.out.println("sm = " + sm); 469 boolean t = fac.isFactorization(a, sm); 470 //System.out.println("t = " + t); 471 assertTrue("prod(factor(a)) = a", t); 472 assertTrue("#facs < 2, sm = " + sm, sm.size() >= 2); 473 } 474 475 476 /** 477 * Test integer factorization, example 3 from Wang. 478 */ 479 public void testIntegerFactorizationEx3() { 480 TermOrder to = new TermOrder(TermOrder.INVLEX); 481 BigInteger cfac = new BigInteger(1); 482 String[] vars = new String[] { "x", "y", "z" }; 483 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 484 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 485 GenPolynomial<BigInteger> a, b, c; 486 487 // (y z^3 + x y z + y^2 + x^3) (x (z^4 + 1) + z + x^3 y^2) 488 489 b = pfac.parse(" (y z^3 + x y z + y^2 + x^3) "); 490 c = pfac.parse(" (x (z^4 + 1) + z + x^3 y^2) "); 491 492 a = b.multiply(c); 493 //System.out.println("a = " + a); 494 //System.out.println("b = " + b); 495 //System.out.println("c = " + c); 496 497 //List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefreeHensel(a); 498 List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefree(a); 499 //System.out.println("sm = " + sm); 500 boolean t = fac.isFactorization(a, sm); 501 //System.out.println("t = " + t); 502 assertTrue("prod(factor(a)) = a", t); 503 assertTrue("#facs < 2, sm = " + sm, sm.size() >= 2); 504 } 505 506 507 /** 508 * Test integer factorization, example 4 from Wang. 509 */ 510 public void testIntegerFactorizationEx4() { 511 TermOrder to = new TermOrder(TermOrder.INVLEX); 512 BigInteger cfac = new BigInteger(1); 513 String[] vars = new String[] { "x", "y", "z" }; 514 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 515 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 516 GenPolynomial<BigInteger> a, b, c, d, e; 517 518 // (z^2 - x^3 y + 3) (z^2 + x y^3) (z^2 + x^3 y^4) (y^4 z^2 + x^2 z + 5) 519 520 b = pfac.parse(" ( z^2 - x^3 y + 3 ) "); 521 c = pfac.parse(" (z^2 + x y^3) "); 522 d = pfac.parse(" (z^2 + x^3 y^4) "); 523 e = pfac.parse(" (y^4 z^2 + x^2 z + 5) "); 524 525 a = b.multiply(c).multiply(d).multiply(e); 526 //System.out.println("a = " + a); 527 //System.out.println("b = " + b); 528 //System.out.println("c = " + c); 529 //System.out.println("d = " + d); 530 //System.out.println("e = " + e); 531 532 //List<GenPolynomial<BigInteger>> sm = fac.factorsRadical(a); // will check squarefree 533 //List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefreeHensel(a); 534 List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefree(a); 535 //System.out.println("sm = " + sm); 536 boolean t = fac.isFactorization(a, sm); 537 //System.out.println("t = " + t); 538 assertTrue("prod(factor(a)) = a", t); 539 assertTrue("#facs < 4, sm = " + sm, sm.size() >= 4); 540 } 541 542 543 /** 544 * Test integer factorization, example 5 from Wang. 545 */ 546 public void testIntegerFactorizationEx5() { 547 TermOrder to = new TermOrder(TermOrder.INVLEX); 548 BigInteger cfac = new BigInteger(1); 549 String[] vars = new String[] { "x", "y", "z", "u" }; 550 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 551 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 552 GenPolynomial<BigInteger> a, b, c; 553 554 // (z^2 + x^3 y^4 + u^2) ( (y^2 + x) z^2 + 3 u^2 x^3 y^4 z + 19 y^2) (u^2 y^4 z^2 + x^2 z + 5), 555 b = pfac.parse(" (z^2 + x^3 y^4 + u^2) "); 556 c = pfac.parse(" ( (y^2 + x ) z^2 + 3 u^2 x^3 y^4 z + 19 y^2 )"); 557 //d = pfac.parse(" (u^2 y^4 z^2 + x^2 z + 5) "); 558 559 a = b.multiply(c); // .multiply(d); // all factors need 256 sec 560 //System.out.println("a = " + a); 561 //System.out.println("b = " + b); 562 //System.out.println("c = " + c); 563 //System.out.println("d = " + d); 564 565 //List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefreeHensel(a); 566 List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefree(a); 567 //System.out.println("sm = " + sm); 568 boolean t = fac.isFactorization(a, sm); 569 //System.out.println("t = " + t); 570 assertTrue("prod(factor(a)) = a", t); 571 assertTrue("#facs < 2, sm = " + sm, sm.size() >= 2); 572 } 573 574 575 /** 576 * Test integer factorization, example 6 from Wang. 577 */ 578 public void testIntegerFactorizationEx6() { 579 TermOrder to = new TermOrder(TermOrder.INVLEX); 580 BigInteger cfac = new BigInteger(1); 581 String[] vars = new String[] { "x", "y", "z", "w" }; 582 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 583 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 584 GenPolynomial<BigInteger> a, b, c; 585 586 // (w^4 z^3 -x y^2 z^2 - w^4 x^5 y^6 - w^2 x^3 y) (- x^5 z^3 + y z + x^2 y^3) 587 // . (w^4 z^6 + y^2 z^3 - w^2 x^2 y^2 z^2 + x^5 z - x^4 y^2 - w^3 x^3 y) 588 //b = pfac.parse(" (w^4 z^3 -x y^2 z^2 - w^4 x^5 y^6 - w^2 x^3 y) "); 589 //c = pfac.parse(" (- x^5 z^3 + y z + x^2 y^3) "); 590 //d = pfac.parse(" (w^4 z^6 + y^2 z^3 - w^2 x^2 y^2 z^2 + x^5 z - x^4 y^2 - w^3 x^3 y) "); 591 592 // with smaller degrees: 593 b = pfac.parse(" (w z^2 - x y^1 z^1 - w x^5 y^2 - w x^3 y) "); 594 c = pfac.parse(" (- x^5 z^2 + y z + x^2 y^1) "); 595 //d = pfac.parse(" (w z^3 + y^2 z^2 - w x^2 y^2 z^1 + x^5 - x^4 y^2 - w x^3 y) "); 596 597 a = b.multiply(c); //.multiply(d); // all factors with small degrees need 684 sec 598 //System.out.println("a = " + a); 599 //System.out.println("b = " + b); 600 //System.out.println("c = " + c); 601 //System.out.println("d = " + d); 602 603 //List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefreeHensel(a); 604 List<GenPolynomial<BigInteger>> sm = fac.factorsSquarefree(a); 605 //System.out.println("sm = " + sm); 606 boolean t = fac.isFactorization(a, sm); 607 //System.out.println("t = " + t); 608 assertTrue("prod(factor(a)) = a", t); 609 assertTrue("#facs < 2, sm = " + sm, sm.size() >= 2); 610 } 611 612 613 /** 614 * Test integer factorization, example 7 from Wang. 615 */ 616 public void testIntegerFactorizationEx7() { 617 TermOrder to = new TermOrder(TermOrder.INVLEX); 618 BigInteger cfac = new BigInteger(1); 619 String[] vars = new String[] { "x", "y", "z" }; 620 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 621 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 622 GenPolynomial<BigInteger> a, b, c; 623 624 // (z + y + x- 3)^3 (z + y + x-2)^2, 625 626 b = pfac.parse(" ( (z + y^2 + x - 3 )^3 ) "); 627 c = pfac.parse(" ( (z + y + x^2 - 2 )^2 ) "); 628 629 a = b.multiply(c); 630 //System.out.println("a = " + a); 631 //System.out.println("b = " + b); 632 //System.out.println("c = " + c); 633 634 SortedMap<GenPolynomial<BigInteger>, Long> sm = fac.factors(a); 635 //System.out.println("sm = " + sm); 636 boolean t = fac.isFactorization(a, sm); 637 //System.out.println("t = " + t); 638 assertTrue("prod(factor(a)) = a", t); 639 assertTrue("#facs < 2, sm = " + sm, sm.size() >= 2); 640 } 641 642 643 /** 644 * Test integer factorization. 645 */ 646 public void testIntegerFactorizationHk() { 647 TermOrder to = new TermOrder(TermOrder.INVLEX); 648 BigInteger cfac = new BigInteger(1); 649 String[] vars = new String[] { "t", "x" }; 650 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 651 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 652 GenPolynomial<BigInteger> a; 653 654 // 2 t * x^2 + 5 x^2 - 4 t * x - 4 x - 6 t - 9 655 // 2 t * x^2 - 5 x^2 + 8 t * x - 5 x + 6 t 656 // 7 t * x^3 + 7 x^3 + 7 t * x^2 + 7 x^2 + 8 x + 8 657 // = ( x + { 1 } ) ( { 7 t + 7 } x^2 + { 8 } ) 658 // 4 t * x^3 + 6 x^3 + 4 t * x^2 + 9 x^2 + 2 x - 1 659 // 2 t * x^2 - 7 x^2 + 2 t * x - 11 x - 4 // conter example to Wangs condition: [2 , x, x + 1 ] 660 // 3 x^4 - ( 7 t + 2 ) x^2 + ( 4 t^2 + 2 t ) 661 662 //a = pfac.parse(" ( 2 t * x^2 + 5 x^2 - 4 t * x - 4 x - 6 t - 9 ) "); 663 //a = pfac.parse(" ( 2 t * x^2 - 5 x^2 + 8 t * x - 5 x + 6 t ) "); 664 //a = pfac.parse(" ( 7 t * x^3 + 7 x^3 + 7 t * x^2 + 7 x^2 + 8 x + 8 ) "); 665 //a = pfac.parse(" ( 4 t * x^3 + 6 x^3 + 4 t * x^2 + 9 x^2 + 2 x - 1 ) "); 666 //a = pfac.parse(" ( 2 t * x^2 - 7 x^2 + 2 t * x - 11 x - 4 ) "); // example to parts of Wangs condition: [2 , x, x + 1 ] 667 a = pfac.parse(" ( 3 x^4 - ( 7 t + 2 ) x^2 + ( 4 t^2 + 2 t ) ) "); // was not applicable or failed for t < x 668 669 //System.out.println("a = " + a); 670 671 SortedMap<GenPolynomial<BigInteger>, Long> sm = fac.factors(a); 672 //System.out.println("sm = " + sm + ", a = " + a + ", pfac = " + pfac.toScript()); 673 boolean t = fac.isFactorization(a, sm); 674 //System.out.println("t = " + t); 675 assertTrue("prod(factor(a)) = a", t); 676 assertTrue("#facs < 2, sm = " + sm, sm.size() >= 2); 677 } 678 679 680 /** 681 * Test integer factorization. 682 */ 683 public void testBivarIntegerFactorization() { 684 TermOrder to = new TermOrder(TermOrder.INVLEX); 685 BigInteger cfac = new BigInteger(1); 686 String[] vars = new String[] { "x", "y" }; 687 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 688 FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 689 GenPolynomial<BigInteger> a; 690 a = pfac.parse(" ( (5*y+2*x)*(5*y-2*x) ) "); // binomial formula 691 692 //System.out.println("a = " + a); 693 694 SortedMap<GenPolynomial<BigInteger>, Long> sm = fac.factors(a); 695 //System.out.println("sm = " + sm + ", a = " + a + ", pfac = " + pfac.toScript()); 696 boolean t = fac.isFactorization(a, sm); 697 //System.out.println("t = " + t); 698 assertTrue("prod(factor(a)) = a", t); 699 assertTrue("#facs < 2, sm = " + sm, sm.size() >= 2); 700 701 a = pfac.parse(" ( (y-4*x)*(y-x) ) "); 702 //System.out.println("a = " + a); 703 sm = fac.factors(a); 704 //System.out.println("sm = " + sm + ", a = " + a + ", pfac = " + pfac.toScript()); 705 t = fac.isFactorization(a, sm); 706 //System.out.println("t = " + t); 707 assertTrue("prod(factor(a)) = a", t); 708 assertTrue("#facs < 2, sm = " + sm, sm.size() >= 2); 709 } 710 711 712 /** 713 * Test integer factorization. Example (a+b*x) (c+d*x). 714 */ 715 public void testIntegerFactorizationProd() { 716 //TermOrder to = TermOrderByName.GRLEX; //not working 717 TermOrder to = TermOrderByName.INVLEX; 718 BigInteger cfac = new BigInteger(1); 719 String[] vars = new String[] { "a", "b", "c", "d", "x" }; 720 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 721 //FactorInteger<ModInteger> fac = new FactorInteger<ModInteger>(); 722 FactorAbstract<BigInteger> fac = FactorFactory.getImplementation(cfac); 723 //System.out.println("fac = " + fac); 724 assertTrue("fac :: FactorInteger: " + fac, fac instanceof FactorInteger); 725 726 GenPolynomial<BigInteger> a, b, c; 727 a = pfac.parse("a+b*x"); 728 b = pfac.parse("c+d*x"); 729 c = a.multiply(b); 730 //System.out.println("c = " + c); 731 732 SortedMap<GenPolynomial<BigInteger>, Long> sm = fac.factors(c); 733 //System.out.println("sm = " + sm); 734 boolean t = fac.isFactorization(c, sm); 735 assertTrue("prod(factor(a)) = a", t); 736 assertTrue("#facs < 2, sm: " + sm, sm.size() >= 2); 737 } 738 739 740 /** 741 * Test integer factorization. Example (e x + d) (c d x + a e). 742 */ 743 public void testIntegerFactorizationLoop() { 744 TermOrder to = TermOrderByName.IGRLEX; 745 //TermOrder to = TermOrderByName.GRLEX; // infinite loop, wrong termorder 746 //TermOrder to = TermOrderByName.INVLEX; 747 BigInteger cfac = BigInteger.ONE; 748 String[] vars = new String[] { "a", "c", "d", "e", "x" }; 749 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, vars.length, to, vars); 750 FactorAbstract<BigInteger> fac = FactorFactory.getImplementation(cfac); 751 //System.out.println("fac = " + fac); 752 assertTrue("fac :: FactorInteger: " + fac, fac instanceof FactorInteger); 753 754 GenPolynomial<BigInteger> a, b, c; 755 a = pfac.parse("e * x + d"); 756 b = pfac.parse("c * d * x + a * e"); 757 c = a.multiply(b); 758 //System.out.println("c = " + c); 759 760 SortedMap<GenPolynomial<BigInteger>, Long> sm = fac.factors(c); 761 //System.out.println("sm = " + sm); 762 boolean t = fac.isFactorization(c, sm); 763 assertTrue("prod(factor(a)) = a", t); 764 assertTrue("#facs < 2, sm: " + sm, sm.size() >= 2); 765 } 766 767}