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