Source code

001/*
002 * $Id: FactorIntegerTest.java 4019 2012-07-22 18:31:13Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.SortedMap;
009import java.util.List;
010
011import org.apache.log4j.BasicConfigurator;
012
013import junit.framework.Test;
014import junit.framework.TestCase;
015import junit.framework.TestSuite;
016
017import edu.jas.arith.BigInteger;
018import edu.jas.arith.ModInteger;
019import edu.jas.kern.ComputerThreads;
020import edu.jas.poly.ExpVector;
021import edu.jas.poly.GenPolynomial;
022import edu.jas.poly.GenPolynomialRing;
023import edu.jas.poly.TermOrder;
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        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 testIntegerFactorizationHk() {
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        //a = pfac.parse(" ( 2 t * x^2 + 5 x^2 - 4 t * x - 4 x - 6 t - 9 ) ");
659        //a = pfac.parse(" ( 2 t * x^2 - 5 x^2 + 8 t * x - 5 x + 6 t ) ");
660        //a = pfac.parse(" ( 7 t * x^3 + 7 x^3 + 7 t * x^2 + 7 x^2 + 8 x + 8 ) ");
661        //a = pfac.parse(" ( 4 t * x^3 + 6 x^3 + 4 t * x^2 + 9 x^2 + 2 x - 1 ) ");
662        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 ]
663        a = pfac.parse(" ( 3 x^4 - ( 7 t + 2  ) x^2 + ( 4 t^2 + 2 t ) ) "); // was not applicable or failed for t < x
664 
665        //System.out.println("a = " + a);
666
667        SortedMap<GenPolynomial<BigInteger>,Long> sm = fac.factors(a);
668        //System.out.println("sm = " + sm);
669        boolean t = fac.isFactorization(a, sm);
670        //System.out.println("t        = " + t);
671        assertTrue("prod(factor(a)) = a", t);
672        assertTrue("#facs < 2, sm = " + sm, sm.size() >= 2);
673    }
674
675}