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}