Source code

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