001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.List; 009import java.util.SortedMap; 010 011import edu.jas.arith.BigInteger; 012import edu.jas.arith.BigRational; 013import edu.jas.arith.ModInteger; 014import edu.jas.arith.ModIntegerRing; 015import edu.jas.kern.ComputerThreads; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.poly.GenPolynomialRing; 018import edu.jas.poly.TermOrder; 019 020import junit.framework.Test; 021import junit.framework.TestCase; 022import junit.framework.TestSuite; 023 024 025/** 026 * Factor tests with JUnit. 027 * @author Heinz Kredel 028 * @author Axel Kramer 029 */ 030 031public class FactorMoreTest 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>FactorTest</CODE> object. 044 * @param name String. 045 */ 046 public FactorMoreTest(String name) { 047 super(name); 048 } 049 050 051 /** 052 */ 053 public static Test suite() { 054 TestSuite suite = new TestSuite(FactorMoreTest.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 = 3; 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 */ 089 public void testDummy() { 090 } 091 092 093 /** 094 * Test integral function factorization. 095 */ 096 public void testIntegralFunctionFactorization() { 097 TermOrder to = new TermOrder(TermOrder.INVLEX); 098 BigRational cfac = new BigRational(1); 099 String[] qvars = new String[] { "t" }; 100 GenPolynomialRing<BigRational> pfac = new GenPolynomialRing<BigRational>(cfac, 1, to, qvars); 101 GenPolynomial<BigRational> t = pfac.univariate(0); 102 103 FactorAbstract<BigRational> fac = new FactorRational(); 104 105 String[] vars = new String[] { "x" }; 106 GenPolynomialRing<GenPolynomial<BigRational>> pqfac = new GenPolynomialRing<GenPolynomial<BigRational>>( 107 pfac, 1, to, vars); 108 GenPolynomial<GenPolynomial<BigRational>> x = pqfac.univariate(0); 109 GenPolynomial<GenPolynomial<BigRational>> x2 = pqfac.univariate(0, 2); 110 111 for (int i = 1; i < 3; i++) { 112 int facs = 0; 113 GenPolynomial<GenPolynomial<BigRational>> a; 114 GenPolynomial<GenPolynomial<BigRational>> b = pqfac.random(2, 3, el, q); 115 //b = b.monic(); 116 //b = b.multiply(b); 117 GenPolynomial<GenPolynomial<BigRational>> c = pqfac.random(2, 3, el, q); 118 //c = c.monic(); 119 if (c.degree() < 1) { 120 c = x2.subtract(pqfac.getONE().multiply(t)); 121 } 122 if (b.degree() < 1) { 123 b = x.sum(pqfac.getONE()); 124 } 125 126 if (c.degree() > 0) { 127 facs++; 128 } 129 if (b.degree() > 0) { 130 facs++; 131 } 132 a = c.multiply(b); 133 //System.out.println("\na = " + a); 134 //System.out.println("b = " + b); 135 //System.out.println("c = " + c); 136 137 SortedMap<GenPolynomial<GenPolynomial<BigRational>>, Long> sm = fac.recursiveFactors(a); 138 //System.out.println("\na = " + a); 139 //System.out.println("sm = " + sm); 140 141 if (sm.size() >= facs) { 142 assertTrue("#facs < " + facs, sm.size() >= facs); 143 } else { 144 long sf = 0; 145 for (Long e : sm.values()) { 146 sf += e; 147 } 148 assertTrue("#facs < " + facs + ", sm = " + sm + ", c*b: " + c + " * " + b, sf >= facs); 149 } 150 151 boolean tt = fac.isRecursiveFactorization(a, sm); 152 //System.out.println("t = " + tt); 153 assertTrue("prod(factor(a)) = a", tt); 154 } 155 ComputerThreads.terminate(); 156 } 157 158 159 /** 160 * Test integer integral function factorization. 161 */ 162 public void testIntegerIntegralFunctionFactorization() { 163 164 TermOrder to = new TermOrder(TermOrder.INVLEX); 165 BigInteger cfac = new BigInteger(1); 166 String[] qvars = new String[] { "t" }; 167 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, 1, to, qvars); 168 GenPolynomial<BigInteger> t = pfac.univariate(0); 169 170 FactorAbstract<BigInteger> fac = new FactorInteger<ModInteger>(); 171 172 String[] vars = new String[] { "x" }; 173 GenPolynomialRing<GenPolynomial<BigInteger>> pqfac = new GenPolynomialRing<GenPolynomial<BigInteger>>( 174 pfac, 1, to, vars); 175 GenPolynomial<GenPolynomial<BigInteger>> x = pqfac.univariate(0); 176 GenPolynomial<GenPolynomial<BigInteger>> x2 = pqfac.univariate(0, 2); 177 178 for (int i = 1; i < 3; i++) { 179 int facs = 0; 180 GenPolynomial<GenPolynomial<BigInteger>> a; 181 GenPolynomial<GenPolynomial<BigInteger>> b = pqfac.random(2, 3, el, q); 182 //b = b.monic(); 183 //b = b.multiply(b); 184 GenPolynomial<GenPolynomial<BigInteger>> c = pqfac.random(2, 3, el, q); 185 //c = c.monic(); 186 if (c.degree() < 1) { 187 c = x2.subtract(pqfac.getONE().multiply(t)); 188 } 189 if (b.degree() < 1) { 190 b = x.sum(pqfac.getONE()); 191 } 192 193 if (c.degree() > 0) { 194 facs++; 195 } 196 if (b.degree() > 0) { 197 facs++; 198 } 199 a = c.multiply(b); 200 //a = pqfac.parse("( ( -26 t - 91 ) x^3 - ( 13 t + 26 ) x^2 + ( 6 t^2 + 21 t ) x + ( 3 t^2 + 6 t ) )"); 201 //a = pqfac.parse("( -3 x^3 + ( t - 1 ) x^2 + ( 3 t ) x - ( t^2 - t ) )"); 202 //System.out.println("\na = " + a); 203 //System.out.println("b = " + b); 204 //System.out.println("c = " + c); 205 206 SortedMap<GenPolynomial<GenPolynomial<BigInteger>>, Long> sm = fac.recursiveFactors(a); 207 //System.out.println("\na = " + a); 208 //System.out.println("sm = " + sm); 209 210 if (sm.size() >= facs) { 211 assertTrue("#facs < " + facs, sm.size() >= facs); 212 } else { 213 long sf = 0; 214 for (Long e : sm.values()) { 215 sf += e; 216 } 217 assertTrue("#facs < " + facs + ", sm = " + sm + ", c*b: " + c + " * " + b, sf >= facs); 218 } 219 220 boolean tt = fac.isRecursiveFactorization(a, sm); 221 //System.out.println("t = " + tt); 222 assertTrue("prod(factor(a)) = a", tt); 223 } 224 ComputerThreads.terminate(); 225 } 226 227 228 /** 229 * Test rational function factorization. 230 */ 231 public void testRationalFunctionFactorization() { 232 233 TermOrder to = new TermOrder(TermOrder.INVLEX); 234 BigRational cfac = new BigRational(1); 235 String[] qvars = new String[] { "t" }; 236 GenPolynomialRing<BigRational> pfac = new GenPolynomialRing<BigRational>(cfac, 1, to, qvars); 237 QuotientRing<BigRational> qfac = new QuotientRing<BigRational>(pfac); 238 Quotient<BigRational> t = qfac.generators().get(1); 239 240 FactorQuotient<BigRational> fac = new FactorQuotient<BigRational>(qfac); 241 242 String[] vars = new String[] { "x" }; 243 GenPolynomialRing<Quotient<BigRational>> pqfac = new GenPolynomialRing<Quotient<BigRational>>(qfac, 1, 244 to, vars); 245 GenPolynomial<Quotient<BigRational>> x = pqfac.univariate(0); 246 GenPolynomial<Quotient<BigRational>> x2 = pqfac.univariate(0, 2); 247 248 for (int i = 1; i < 3; i++) { 249 int facs = 0; 250 GenPolynomial<Quotient<BigRational>> a; 251 GenPolynomial<Quotient<BigRational>> b = pqfac.random(2, 3, el, q); 252 //b = b.monic(); 253 //b = b.multiply(b); 254 GenPolynomial<Quotient<BigRational>> c = pqfac.random(2, 3, el, q); 255 //c = c.monic(); 256 if (c.degree() < 1) { 257 c = x2.subtract(pqfac.getONE().multiply(t)); 258 } 259 if (b.degree() < 1) { 260 b = x.sum(pqfac.getONE()); 261 } 262 263 if (c.degree() > 0) { 264 facs++; 265 } 266 if (b.degree() > 0) { 267 facs++; 268 } 269 a = c.multiply(b); 270 //System.out.println("\na = " + a); 271 //System.out.println("b = " + b); 272 //System.out.println("c = " + c); 273 274 SortedMap<GenPolynomial<Quotient<BigRational>>, Long> sm = fac.factors(a); 275 //System.out.println("\na = " + a); 276 //System.out.println("sm = " + sm); 277 278 if (sm.size() >= facs) { 279 assertTrue("#facs < " + facs, sm.size() >= facs); 280 } else { 281 long sf = 0; 282 for (Long e : sm.values()) { 283 sf += e; 284 } 285 assertTrue("#facs < " + facs + ", sm = " + sm + ", c*b: " + c + " * " + b, sf >= facs); 286 } 287 288 boolean tt = fac.isFactorization(a, sm); 289 //System.out.println("t = " + tt); 290 assertTrue("prod(factor(a)) = a", tt); 291 } 292 ComputerThreads.terminate(); 293 } 294 295 296 /** 297 * Test modular rational function factorization. 298 */ 299 public void testModularRationalFunctionFactorization() { 300 301 TermOrder to = new TermOrder(TermOrder.INVLEX); 302 ModIntegerRing cfac = new ModIntegerRing(19, true); 303 String[] qvars = new String[] { "t" }; 304 GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to, qvars); 305 QuotientRing<ModInteger> qfac = new QuotientRing<ModInteger>(pfac); 306 Quotient<ModInteger> t = qfac.generators().get(1); 307 308 FactorQuotient<ModInteger> fac = new FactorQuotient<ModInteger>(qfac); 309 310 String[] vars = new String[] { "x" }; 311 GenPolynomialRing<Quotient<ModInteger>> pqfac = new GenPolynomialRing<Quotient<ModInteger>>(qfac, 1, 312 to, vars); 313 GenPolynomial<Quotient<ModInteger>> x = pqfac.univariate(0); 314 GenPolynomial<Quotient<ModInteger>> x2 = pqfac.univariate(0, 2); 315 316 for (int i = 1; i < 3; i++) { 317 int facs = 0; 318 GenPolynomial<Quotient<ModInteger>> a; 319 GenPolynomial<Quotient<ModInteger>> b = pqfac.random(2, 3, el, q); 320 //b = b.monic(); 321 //b = b.multiply(b); 322 GenPolynomial<Quotient<ModInteger>> c = pqfac.random(2, 3, el, q); 323 //c = c.monic(); 324 if (c.degree() < 1) { 325 c = x2.subtract(pqfac.getONE().multiply(t)); 326 } 327 if (b.degree() < 1) { 328 b = x.sum(pqfac.getONE()); 329 } 330 331 if (c.degree() > 0) { 332 facs++; 333 } 334 if (b.degree() > 0) { 335 facs++; 336 } 337 a = c.multiply(b); 338 //System.out.println("\na = " + a); 339 //System.out.println("b = " + b); 340 //System.out.println("c = " + c); 341 342 SortedMap<GenPolynomial<Quotient<ModInteger>>, Long> sm = fac.factors(a); 343 //System.out.println("\na = " + a); 344 //System.out.println("sm = " + sm); 345 346 if (sm.size() >= facs) { 347 assertTrue("#facs < " + facs, sm.size() >= facs); 348 } else { 349 long sf = 0; 350 for (Long e : sm.values()) { 351 sf += e; 352 } 353 assertTrue("#facs < " + facs + ", sm = " + sm + ", c*b: " + c + " * " + b, sf >= facs); 354 } 355 356 boolean tt = fac.isFactorization(a, sm); 357 //System.out.println("t = " + tt); 358 assertTrue("prod(factor(a)) = a", tt); 359 } 360 ComputerThreads.terminate(); 361 } 362 363 364 /** 365 * Test cyclotomic polynomial factorization. 366 */ 367 public void testCyclotomicPolynomialFactorization() { 368 TermOrder to = new TermOrder(TermOrder.INVLEX); 369 BigInteger cfac = new BigInteger(1); 370 String[] qvars = new String[] { "x" }; 371 GenPolynomialRing<BigInteger> pfac = new GenPolynomialRing<BigInteger>(cfac, 1, to, qvars); 372 //System.out.println("pfac = " + pfac.toScript()); 373 374 GenPolynomial<BigInteger> r = pfac.univariate(0, 2).subtract(pfac.getONE()); 375 //System.out.println("r = " + r); 376 377 GenPolynomial<BigInteger> q = r.inflate(3); 378 //System.out.println("q = " + q); 379 assertTrue("q != 0: ", !q.isZERO()); 380 381 GenPolynomial<BigInteger> h; 382 h = CycloUtil.cyclotomicPolynomial(pfac, 100L); 383 //System.out.println("h = " + h); 384 assertTrue("isCyclotomicPolynomial: " + h, CycloUtil.isCyclotomicPolynomial(h)); 385 386 h = CycloUtil.cyclotomicPolynomial(pfac, 258L); 387 //System.out.println("h = " + h); 388 assertTrue("isCyclotomicPolynomial: " + h, CycloUtil.isCyclotomicPolynomial(h)); 389 390 List<GenPolynomial<BigInteger>> H; 391 H = CycloUtil.cyclotomicDecompose(pfac, 100L); 392 //System.out.println("H = " + H); 393 for (GenPolynomial<BigInteger> hp : H) { 394 assertTrue("isCyclotomicPolynomial: " + hp, CycloUtil.isCyclotomicPolynomial(hp)); 395 } 396 397 H = CycloUtil.cyclotomicDecompose(pfac, 258L); 398 //System.out.println("H = " + H); 399 //System.out.println(""); 400 for (GenPolynomial<BigInteger> hp : H) { 401 assertTrue("isCyclotomicPolynomial: " + hp, CycloUtil.isCyclotomicPolynomial(hp)); 402 } 403 404 //FactorAbstract<BigInteger> fac = new FactorInteger(); 405 //Map<GenPolynomial<BigInteger>, Long> F; 406 407 h = pfac.univariate(0, 20).subtract(pfac.getONE()); 408 //System.out.println("hc = " + h); 409 assertTrue("isCyclotomicPolynomial: " + h, CycloUtil.isCyclotomicPolynomial(h)); 410 411 H = CycloUtil.cyclotomicFactors(h); 412 //System.out.println("H = " + H); 413 //System.out.println("factors = " + fac.factors(h)); 414 //System.out.println("H = " + H); 415 //System.out.println(""); 416 417 h = pfac.univariate(0, 20).sum(pfac.getONE()); 418 //System.out.println("hc = " + h); 419 assertTrue("isCyclotomicPolynomial: " + h, CycloUtil.isCyclotomicPolynomial(h)); 420 421 H = CycloUtil.cyclotomicFactors(h); 422 //System.out.println("H = " + H); 423 //System.out.println("factors = " + fac.factors(h)); 424 //System.out.println("H = " + H); 425 426 for (long n = 1L; n < 1L; n++) { 427 h = CycloUtil.cyclotomicPolynomial(pfac, n); 428 //F = fac.factors(h); 429 //System.out.println("factors = " + F.size()); 430 //System.out.println("h(" + n + ") = " + h); 431 assertTrue("isCyclotomicPolynomial: " + h, CycloUtil.isCyclotomicPolynomial(h)); 432 } 433 434 h = pfac.univariate(0, 258).subtract(pfac.getONE()); 435 //h = pfac.univariate(0, 2).sum(pfac.getONE()); 436 //h = pfac.parse("x**16 + x**14 - x**10 - x**8 - x**6 + x**2 + 1"); // yes 437 //h = pfac.parse("x**16 + x**14 - x**10 + x**8 - x**6 + x**2 + 1"); // no 438 //System.out.println("hc = " + h); 439 assertTrue("isCyclotomicPolynomial: " + h, CycloUtil.isCyclotomicPolynomial(h)); 440 } 441 442 443 /** 444 * Test factorization over integers. 445 */ 446 public void testFactorizationInteger() { 447 String str = "-2*m1*m2*u1*u2+m1*m2*u2^2-m2^2*u2^2+2*m1*m2*u1*v2+2*m2^2*u2*v2-m1*m2*v2^2-m2^2*v2^2"; 448 //"m2 * v2 + m1 * v2 - m2 * u2 + m1 * u2 - 2 m1 * u1"; 449 //"-2*m1*u1*u2+m1*u2^2-m2*u2^2+2*m1*u1*v2+2*m2*u2*v2-m1*v2^2-m2^2*v2^2"; 450 451 String[] vars = new String[] { "m1", "m2", "u1", "u2", "v2" }; 452 GenPolynomialRing<BigInteger> fac; 453 fac = new GenPolynomialRing<BigInteger>(BigInteger.ONE, vars.length, new TermOrder(TermOrder.INVLEX), 454 vars); 455 456 GenPolynomial<BigInteger> poly = fac.parse(str); 457 //GenPolynomial<BigInteger> p2 = fac.parse("m2"); 458 //GenPolynomial<BigInteger> p3 = fac.parse("v2-u2"); 459 //poly = poly.multiply(p3); 460 final int loops = 10; //0000; 461 //System.out.println("Run: " + loops + ": -" + poly.toString()); 462 for (int i = 0; i < loops; i++) { 463 FactorAbstract<BigInteger> factorAbstract = FactorFactory.getImplementation(BigInteger.ZERO); 464 SortedMap<GenPolynomial<BigInteger>, Long> map = factorAbstract.factors(poly); 465 //System.out.println("Factors: " + map.toString()); 466 //System.out.println("isFactorization = " + factorAbstract.isFactorization(poly,map)); 467 assertTrue("isFactorization: ", factorAbstract.isFactorization(poly, map)); 468 } 469 } 470 471}