Source code

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}