Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.List;
009import java.util.SortedMap;
010
011import edu.jas.arith.ModInt;
012import edu.jas.arith.ModIntRing;
013import edu.jas.arith.ModInteger;
014import edu.jas.arith.ModIntegerRing;
015import edu.jas.arith.PrimeList;
016import edu.jas.kern.ComputerThreads;
017import edu.jas.poly.AlgebraicNumber;
018import edu.jas.poly.AlgebraicNumberRing;
019import edu.jas.poly.GenPolynomial;
020import edu.jas.poly.GenPolynomialRing;
021import edu.jas.poly.TermOrder;
022
023import junit.framework.Test;
024import junit.framework.TestCase;
025import junit.framework.TestSuite;
026
027
028/**
029 * Factor modular tests with JUnit.
030 * @author Heinz Kredel
031 */
032
033public class FactorModularTest extends TestCase {
034
035
036    /**
037     * main.
038     */
039    public static void main(String[] args) {
040        junit.textui.TestRunner.run(suite());
041    }
042
043
044    /**
045     * Constructs a <CODE>FactorModularTest</CODE> object.
046     * @param name String.
047     */
048    public FactorModularTest(String name) {
049        super(name);
050    }
051
052
053    /**
054     */
055    public static Test suite() {
056        TestSuite suite = new TestSuite(FactorModularTest.class);
057        return suite;
058    }
059
060
061    int rl = 3;
062
063
064    int kl = 5;
065
066
067    int ll = 5;
068
069
070    int el = 3;
071
072
073    float q = 0.3f;
074
075
076    @Override
077    protected void setUp() {
078    }
079
080
081    @Override
082    protected void tearDown() {
083        ComputerThreads.terminate();
084    }
085
086
087    /**
088     * Test dummy for Junit.
089     * 
090     */
091    public void testDummy() {
092    }
093
094
095    /**
096     * Test modular factorization.
097     */
098    public void testModularFactorization() {
099        PrimeList pl = new PrimeList(PrimeList.Range.medium);
100        TermOrder to = new TermOrder(TermOrder.INVLEX);
101        ModIntegerRing cfac = new ModIntegerRing(pl.get(3));
102        //System.out.println("cfac = " + cfac);
103        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to);
104        FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac);
105        for (int i = 1; i < 4; i++) {
106            int facs = 0;
107            GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el*(i+1),q);
108            GenPolynomial<ModInteger> b = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
109            GenPolynomial<ModInteger> c = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
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            a = c.multiply(b);
120            if (a.isConstant()) {
121                continue;
122            }
123            a = a.monic();
124            //System.out.println("\na = " + a);
125            //System.out.println("b = " + b);
126            //System.out.println("c = " + c);
127
128            SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.baseFactors(a);
129            //System.out.println("sm = " + sm);
130
131            if (sm.size() >= facs) {
132                assertTrue("#facs < " + facs, sm.size() >= facs);
133            } else {
134                long sf = 0;
135                for (Long e : sm.values()) {
136                    sf += e;
137                }
138                assertTrue("#facs < " + facs, sf >= facs);
139            }
140
141            boolean t = fac.isFactorization(a, sm);
142            //System.out.println("t        = " + t);
143            assertTrue("prod(factor(a)) = a", t);
144        }
145    }
146
147
148    /**
149     * Test modular factorization example.
150     */
151    public void testModularFactorizationExam() {
152        TermOrder to = new TermOrder(TermOrder.INVLEX);
153        ModIntegerRing cfac = new ModIntegerRing(7);
154        //System.out.println("cfac = " + cfac);
155        String[] vars = new String[] { "x" };
156        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to, vars);
157        FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac);
158
159        int facs = 3;
160        GenPolynomial<ModInteger> a = pfac.parse("(x^12+5)");
161        a = a.monic();
162        //System.out.println("\na = " + a);
163
164        SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.baseFactors(a);
165        //System.out.println("sm = " + sm);
166
167        if (sm.size() >= facs) {
168            assertTrue("#facs < " + facs, sm.size() >= facs);
169        } else {
170            long sf = 0;
171            for (Long e : sm.values()) {
172                sf += e;
173            }
174            assertTrue("#facs < " + facs, sf >= facs);
175        }
176
177        boolean t = fac.isFactorization(a, sm);
178        //System.out.println("t        = " + t);
179        assertTrue("prod(factor(a)) = a", t);
180    }
181
182
183    /**
184     * Test modular factorization, case p = 2.
185     */
186    public void testModular2Factorization() {
187        TermOrder to = new TermOrder(TermOrder.INVLEX);
188        ModIntegerRing cfac = new ModIntegerRing(2L);
189        //System.out.println("cfac = " + cfac);
190        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, new String[] { "x" },
191                        to);
192        FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac);
193        for (int i = 1; i < 4; i++) {
194            int facs = 0;
195            GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el*(i+1),q);
196            GenPolynomial<ModInteger> b = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
197            GenPolynomial<ModInteger> c = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
198            if (b.isZERO() || c.isZERO()) {
199                continue;
200            }
201            if (c.degree() > 0) {
202                facs++;
203            }
204            if (b.degree() > 0) {
205                facs++;
206            }
207            a = c.multiply(b);
208            if (a.isConstant()) {
209                continue;
210            }
211            //a = pfac.parse(" x**13 + x**11 + x**7 + x**3 + x ");
212            a = a.monic();
213            //System.out.println("\na = " + a);
214            //System.out.println("b = " + b);
215            //System.out.println("c = " + c);
216
217            SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.baseFactors(a);
218            //System.out.println("sm = " + sm);
219
220            if (sm.size() >= facs) {
221                assertTrue("#facs < " + facs, sm.size() >= facs);
222            } else {
223                long sf = 0;
224                for (Long e : sm.values()) {
225                    sf += e;
226                }
227                assertTrue("#facs < " + facs, sf >= facs);
228            }
229
230            boolean t = fac.isFactorization(a, sm);
231            //System.out.println("t        = " + t);
232            assertTrue("prod(factor(a)) = a", t);
233        }
234    }
235
236
237    /**
238     * Test multivariate modular factorization.
239     */
240    public void testMultivariateModularFactorization() {
241        //PrimeList pl = new PrimeList(PrimeList.Range.small);
242        TermOrder to = new TermOrder(TermOrder.INVLEX);
243        ModIntegerRing cfac = new ModIntegerRing(13); // pl.get(3), 7, 11, 13
244        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, rl, to);
245        FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac);
246        for (int i = 1; i < 2; i++) {
247            int facs = 0;
248            GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el,q);
249            GenPolynomial<ModInteger> b = pfac.random(kl, 2, el, q);
250            GenPolynomial<ModInteger> c = pfac.random(kl, 2, el, q);
251            if (b.isZERO() || c.isZERO()) {
252                continue;
253            }
254            if (c.degree() > 0) {
255                facs++;
256            }
257            if (b.degree() > 0) {
258                facs++;
259            }
260            a = c.multiply(b);
261            if (a.isConstant()) {
262                continue;
263            }
264            //a = a.monic();
265            //System.out.println("\na = " + a);
266            //System.out.println("b = " + b);
267            //System.out.println("c = " + c);
268
269            SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.factors(a);
270            //System.out.println("sm = " + sm);
271
272            if (sm.size() >= facs) {
273                assertTrue("#facs < " + facs, sm.size() >= facs);
274            } else {
275                long sf = 0;
276                for (Long e : sm.values()) {
277                    sf += e;
278                }
279                assertTrue("#facs < " + facs, sf >= facs);
280            }
281
282            boolean t = fac.isFactorization(a, sm);
283            //System.out.println("t        = " + t);
284            assertTrue("prod(factor(a)) = a", t);
285        }
286    }
287
288
289    /**
290     * Test modular absolute factorization.
291     */
292    public void testBaseModularAbsoluteFactorization() {
293        TermOrder to = new TermOrder(TermOrder.INVLEX);
294        ModIntegerRing cfac = new ModIntegerRing(17);
295        String[] alpha = new String[] { "alpha" };
296        //String[] vars = new String[] { "z" };
297        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to, alpha);
298        GenPolynomial<ModInteger> agen = pfac.univariate(0, 4);
299        agen = agen.sum(pfac.fromInteger(1)); // x^4 + 1
300
301        FactorModular<ModInteger> engine = new FactorModular<ModInteger>(cfac);
302
303        FactorsMap<ModInteger> F
304        //= engine.baseFactorsAbsoluteSquarefree(agen);
305        //= engine.baseFactorsAbsoluteIrreducible(agen);
306                        = engine.baseFactorsAbsolute(agen);
307        //System.out.println("agen        = " + agen);
308        //System.out.println("F           = " + F);
309
310        boolean t = engine.isAbsoluteFactorization(F);
311        //System.out.println("t        = " + t);
312        assertTrue("prod(factor(a)) = a", t);
313    }
314
315
316    /**
317     * Berlekamp small odd prime factorization test.
318     */
319    public void testFactorBerlekampSmallOdd() {
320        int q = 11; //32003; //11;
321        ModIntRing mi = new ModIntRing(q);
322        //System.out.println("mi = " + mi.toScript());
323        GenPolynomialRing<ModInt> pfac = new GenPolynomialRing<ModInt>(mi, new String[] { "x" });
324        //System.out.println("SmallOdd pfac = " + pfac.toScript());
325        GenPolynomial<ModInt> A = pfac.parse("x^6 - 3 x^5 + x^4 - 3 x^3 - x^2 -3 x + 1");
326        //System.out.println("A = " + A.toScript());
327
328        FactorAbstract<ModInt> bf = new FactorModularBerlekamp<ModInt>(pfac.coFac);
329        List<GenPolynomial<ModInt>> factors = bf.baseFactorsSquarefree(A);
330        //System.out.println("factors = " + factors + "\n");
331        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
332        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
333
334        GenPolynomial<ModInt> B = pfac.random(5).monic();
335        GenPolynomial<ModInt> C = pfac.random(5).monic();
336        A = B.multiply(C);
337        //System.out.println("A = " + A.toScript());
338        //System.out.println("B = " + B.toScript());
339        //System.out.println("C = " + C.toScript());
340
341        factors = bf.baseFactorsSquarefree(A);
342        //System.out.println("factors = " + factors + "\n");
343        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
344        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
345    }
346
347
348    /**
349     * Berlekamp big odd prime factorization test.
350     */
351    public void testFactorBerlekampBigOdd() {
352        int q = 32003; //11;
353        ModIntRing mi = new ModIntRing(q);
354        //System.out.println("mi = " + mi.toScript());
355        GenPolynomialRing<ModInt> pfac = new GenPolynomialRing<ModInt>(mi, new String[] { "x" });
356        //System.out.println("BigOdd pfac = " + pfac.toScript());
357        GenPolynomial<ModInt> A = pfac.parse("x^6 - 3 x^5 + x^4 - 3 x^3 - x^2 -3 x + 1");
358        //System.out.println("A = " + A.toScript());
359
360        //FactorAbstract<ModInt> bf = new FactorModularBerlekamp<ModInt>(pfac.coFac);
361        FactorModularBerlekamp<ModInt> bf = new FactorModularBerlekamp<ModInt>(pfac.coFac);
362        List<GenPolynomial<ModInt>> factors = bf.baseFactorsSquarefreeBigPrime(A);
363        //System.out.println("factors = " + factors + "\n");
364        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
365        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
366
367        GenPolynomial<ModInt> B = pfac.random(5).monic();
368        GenPolynomial<ModInt> C = pfac.random(5).monic();
369        A = B.multiply(C);
370        //System.out.println("A = " + A.toScript());
371        //System.out.println("B = " + B.toScript());
372        //System.out.println("C = " + C.toScript());
373
374        factors = bf.baseFactorsSquarefreeBigPrime(A);
375        //System.out.println("factors = " + factors + "\n");
376        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
377        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
378    }
379
380
381    /**
382     * Berlekamp big even prime factorization test.
383     */
384    public void testFactorBerlekampBigEven() {
385        int q = 2;
386        ModIntRing mi = new ModIntRing(q);
387        //System.out.println("mi = " + mi.toScript());
388        GenPolynomialRing<ModInt> pfac = new GenPolynomialRing<ModInt>(mi, new String[] { "x" });
389        //System.out.println("BigEven pfac = " + pfac.toScript());
390        GenPolynomial<ModInt> A = pfac.parse("x^6 - 3 x^5 + x^4 - 3 x^3 - x^2 -3 x + 1");
391        //GenPolynomial<ModInt> A = pfac.parse(" x**13 + x**11 + x**7 + x**3 + x "); //sm = {x=1, x^2 + x + 1 =6}
392
393        //System.out.println("A = " + A.toScript());
394
395        //FactorAbstract<ModInt> bf = new FactorModularBerlekamp<ModInt>(pfac.coFac);
396        FactorModularBerlekamp<ModInt> bf = new FactorModularBerlekamp<ModInt>(pfac.coFac);
397        List<GenPolynomial<ModInt>> factors = bf.baseFactorsSquarefreeBigPrime(A);
398        //System.out.println("factors = " + factors + "\n");
399        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
400        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
401
402        GenPolynomial<ModInt> B = pfac.random(10).monic();
403        GenPolynomial<ModInt> C = pfac.random(10).monic();
404        A = B.multiply(C);
405        //System.out.println("A = " + A.toScript());
406        //System.out.println("B = " + B.toScript());
407        //System.out.println("C = " + C.toScript());
408
409        factors = bf.baseFactorsSquarefreeBigPrime(A);
410        //System.out.println("factors = " + factors + "\n");
411        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
412        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
413    }
414
415
416    /**
417     * Berlekamp small even prime factorization test.
418     */
419    public void testFactorBerlekampSmallEven() {
420        int q = 2;
421        ModIntRing mi = new ModIntRing(q);
422        //System.out.println("mi = " + mi.toScript());
423        GenPolynomialRing<ModInt> pfac = new GenPolynomialRing<ModInt>(mi, new String[] { "x" });
424        //System.out.println("SmallEven pfac = " + pfac.toScript());
425        GenPolynomial<ModInt> A = pfac.parse("x^6 - 3 x^5 + x^4 - 3 x^3 - x^2 -3 x + 1");
426        //GenPolynomial<ModInt> A = pfac.parse(" x**13 + x**11 + x**7 + x**3 + x "); //sm = {x=1, x^2 + x + 1 =6}
427        //System.out.println("A = " + A.toScript());
428
429        //FactorAbstract<ModInt> bf = new FactorModularBerlekamp<ModInt>(pfac.coFac);
430        FactorModularBerlekamp<ModInt> bf = new FactorModularBerlekamp<ModInt>(pfac.coFac);
431        List<GenPolynomial<ModInt>> factors = bf.baseFactorsSquarefreeSmallPrime(A);
432        //System.out.println("factors = " + factors + "\n");
433        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
434        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
435
436        GenPolynomial<ModInt> B = pfac.random(10).monic();
437        GenPolynomial<ModInt> C = pfac.random(10).monic();
438        A = B.multiply(C);
439        //System.out.println("A = " + A.toScript());
440        //System.out.println("B = " + B.toScript());
441        //System.out.println("C = " + C.toScript());
442
443        factors = bf.baseFactorsSquarefreeSmallPrime(A);
444        //System.out.println("factors = " + factors + "\n");
445        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
446        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
447    }
448
449
450    /**
451     * Berlekamp big even prime power factorization test.
452     */
453    public void testFactorBerlekampBigEvenPower() {
454        int q = 2;
455        //int qp = 4;
456        ModIntRing mi = new ModIntRing(q);
457        //System.out.println("mi = " + mi.toScript());
458        GenPolynomialRing<ModInt> mfac = new GenPolynomialRing<ModInt>(mi, new String[] { "a" });
459        GenPolynomial<ModInt> amod = mfac.parse("a^4 + a + 1");
460        //AlgebraicNumberRing<ModInt> gf = PolyUfdUtil.algebraicNumberField(mi, qp);
461        AlgebraicNumberRing<ModInt> gf = new AlgebraicNumberRing<ModInt>(amod, true);
462        //System.out.println("gf(2^4) = " + gf.toScript());
463        GenPolynomialRing<AlgebraicNumber<ModInt>> pfac = new GenPolynomialRing<AlgebraicNumber<ModInt>>(gf,
464                        new String[] { "x" });
465        //System.out.println("BigEvenPower pfac = " + pfac.toScript());
466        //GenPolynomial<AlgebraicNumber<ModInt>> A = pfac.parse("x^6 - 3 x^5 + x^4 - 3 x^3 - x^2 -3 x + 1");
467        GenPolynomial<AlgebraicNumber<ModInt>> A = pfac
468                        .parse("x^5 + (a^3 + a + 1) x^4 + (a^3 + a^2 + 1) x^3 + ( a ) x + (a^3 + a + 1)");
469        //System.out.println("A = " + A.toScript());
470
471        //FactorAbstract<AlgebraicNumber<ModInt>> bf = new FactorModularBerlekamp<AlgebraicNumber<ModInt>>(pfac.coFac);
472        FactorModularBerlekamp<AlgebraicNumber<ModInt>> bf = new FactorModularBerlekamp<AlgebraicNumber<ModInt>>(
473                        pfac.coFac);
474        List<GenPolynomial<AlgebraicNumber<ModInt>>> factors = bf.baseFactorsSquarefreeBigPrime(A);
475        //System.out.println("factors = " + factors + "\n");
476        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
477        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
478
479        GenPolynomial<AlgebraicNumber<ModInt>> B = pfac.random(5).monic();
480        GenPolynomial<AlgebraicNumber<ModInt>> C = pfac.random(7).monic();
481        A = B.multiply(C);
482        //System.out.println("A = " + A.toScript());
483        //System.out.println("B = " + B.toScript());
484        //System.out.println("C = " + C.toScript());
485
486        factors = bf.baseFactorsSquarefreeBigPrime(A);
487        //System.out.println("factors = " + factors + "\n");
488        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
489        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
490    }
491
492
493    /**
494     * Berlekamp small even prime power factorization test.
495     */
496    public void testFactorBerlekampSmallEvenPower() {
497        int q = 2;
498        //int qp = 4;
499        ModIntRing mi = new ModIntRing(q);
500        //System.out.println("mi = " + mi.toScript());
501        GenPolynomialRing<ModInt> mfac = new GenPolynomialRing<ModInt>(mi, new String[] { "a" });
502        GenPolynomial<ModInt> amod = mfac.parse("a^4 + a + 1");
503        //AlgebraicNumberRing<ModInt> gf = PolyUfdUtil.algebraicNumberField(mi, qp);
504        AlgebraicNumberRing<ModInt> gf = new AlgebraicNumberRing<ModInt>(amod, true);
505        //System.out.println("gf(2^4) = " + gf.toScript());
506        GenPolynomialRing<AlgebraicNumber<ModInt>> pfac = new GenPolynomialRing<AlgebraicNumber<ModInt>>(gf,
507                        new String[] { "x" });
508        //System.out.println("SmallEvenPower pfac = " + pfac.toScript());
509        //GenPolynomial<AlgebraicNumber<ModInt>> A = pfac.parse("x^6 - 3 x^5 + x^4 - 3 x^3 - x^2 -3 x + 1");
510        GenPolynomial<AlgebraicNumber<ModInt>> A = pfac
511                        .parse("x^5 + (a^3 + a + 1) x^4 + (a^3 + a^2 + 1) x^3 + ( a ) x + (a^3 + a + 1)");
512        //System.out.println("A = " + A.toScript());
513
514        //FactorAbstract<AlgebraicNumber<ModInt>> bf = new FactorModularBerlekamp<AlgebraicNumber<ModInt>>(pfac.coFac);
515        FactorModularBerlekamp<AlgebraicNumber<ModInt>> bf = new FactorModularBerlekamp<AlgebraicNumber<ModInt>>(
516                        pfac.coFac);
517        List<GenPolynomial<AlgebraicNumber<ModInt>>> factors = bf.baseFactorsSquarefreeSmallPrime(A);
518        //System.out.println("factors = " + factors + "\n");
519        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
520        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
521
522        GenPolynomial<AlgebraicNumber<ModInt>> B = pfac.random(5).monic();
523        GenPolynomial<AlgebraicNumber<ModInt>> C = pfac.random(7).monic();
524        A = B.multiply(C);
525        //System.out.println("A = " + A.toScript());
526        //System.out.println("B = " + B.toScript());
527        //System.out.println("C = " + C.toScript());
528
529        factors = bf.baseFactorsSquarefreeSmallPrime(A);
530        //System.out.println("factors = " + factors + "\n");
531        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
532        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
533    }
534
535
536    /**
537     * Berlekamp small odd prime power factorization test.
538     */
539    public void testFactorBerlekampSmallOddPower() {
540        int q = 3;
541        int qp = 4;
542        ModIntRing mi = new ModIntRing(q);
543        //System.out.println("mi = " + mi.toScript());
544        GenPolynomialRing<ModInt> mfac = new GenPolynomialRing<ModInt>(mi, new String[] { "a" });
545        //GenPolynomial<ModInt> amod = mfac.parse("a^4 + a + 1");
546        //AlgebraicNumberRing<ModInt> gf = new AlgebraicNumberRing<ModInt>(amod, true);
547        AlgebraicNumberRing<ModInt> gf = PolyUfdUtil.algebraicNumberField(mfac, qp);
548        //System.out.println("gf(2^4) = " + gf.toScript());
549        GenPolynomialRing<AlgebraicNumber<ModInt>> pfac = new GenPolynomialRing<AlgebraicNumber<ModInt>>(gf,
550                        new String[] { "x" });
551        //System.out.println("SmallOddPower pfac = " + pfac.toScript());
552        //GenPolynomial<AlgebraicNumber<ModInt>> A = pfac.parse("x^6 - 3 x^5 + x^4 - 3 x^3 - x^2 -3 x + 1");
553        GenPolynomial<AlgebraicNumber<ModInt>> A = pfac
554                        .parse("x^5 + (a^3 + a + 1) x^4 + (a^3 + a^2 + 1) x^3 + ( a ) x + (a^3 + a + 1)");
555        //System.out.println("A = " + A.toScript());
556
557        //FactorAbstract<AlgebraicNumber<ModInt>> bf = new FactorModularBerlekamp<AlgebraicNumber<ModInt>>(pfac.coFac);
558        FactorModularBerlekamp<AlgebraicNumber<ModInt>> bf = new FactorModularBerlekamp<AlgebraicNumber<ModInt>>(
559                        pfac.coFac);
560        List<GenPolynomial<AlgebraicNumber<ModInt>>> factors = bf.baseFactorsSquarefreeSmallPrime(A);
561        //System.out.println("factors = " + factors + "\n");
562        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
563        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
564
565        GenPolynomial<AlgebraicNumber<ModInt>> B = pfac.random(5).monic();
566        GenPolynomial<AlgebraicNumber<ModInt>> C = pfac.random(7).monic();
567        A = B.multiply(C);
568        //System.out.println("A = " + A.toScript());
569        //System.out.println("B = " + B.toScript());
570        //System.out.println("C = " + C.toScript());
571
572        factors = bf.baseFactorsSquarefreeSmallPrime(A);
573        //System.out.println("factors = " + factors + "\n");
574        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
575        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
576    }
577
578
579    /**
580     * Berlekamp big odd prime power factorization test.
581     */
582    public void testFactorBerlekampBigOddPower() {
583        int q = 3;
584        int qp = 4;
585        ModIntRing mi = new ModIntRing(q);
586        //System.out.println("mi = " + mi.toScript());
587        GenPolynomialRing<ModInt> mfac = new GenPolynomialRing<ModInt>(mi, new String[] { "a" });
588        //GenPolynomial<ModInt> amod = mfac.parse("a^4 + a + 1");
589        //AlgebraicNumberRing<ModInt> gf = new AlgebraicNumberRing<ModInt>(amod, true);
590        AlgebraicNumberRing<ModInt> gf = PolyUfdUtil.algebraicNumberField(mfac, qp);
591        //System.out.println("gf(2^4) = " + gf.toScript());
592        GenPolynomialRing<AlgebraicNumber<ModInt>> pfac = new GenPolynomialRing<AlgebraicNumber<ModInt>>(gf,
593                        new String[] { "x" });
594        //System.out.println("BigOddPower pfac = " + pfac.toScript());
595        //GenPolynomial<AlgebraicNumber<ModInt>> A = pfac.parse("x^6 - 3 x^5 + x^4 - 3 x^3 - x^2 -3 x + 1");
596        GenPolynomial<AlgebraicNumber<ModInt>> A = pfac
597                        .parse("x^5 + (a^3 + a + 1) x^4 + (a^3 + a^2 + 1) x^3 + ( a ) x + (a^3 + a + 1)");
598        //System.out.println("A = " + A.toScript());
599
600        //FactorAbstract<AlgebraicNumber<ModInt>> bf = new FactorModularBerlekamp<AlgebraicNumber<ModInt>>(pfac.coFac);
601        FactorModularBerlekamp<AlgebraicNumber<ModInt>> bf = new FactorModularBerlekamp<AlgebraicNumber<ModInt>>(
602                        pfac.coFac);
603        List<GenPolynomial<AlgebraicNumber<ModInt>>> factors = bf.baseFactorsSquarefreeBigPrime(A);
604        //System.out.println("factors = " + factors + "\n");
605        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
606        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
607
608        GenPolynomial<AlgebraicNumber<ModInt>> B = pfac.random(5).monic();
609        GenPolynomial<AlgebraicNumber<ModInt>> C = pfac.random(7).monic();
610        A = B.multiply(C);
611        //System.out.println("A = " + A.toScript());
612        //System.out.println("B = " + B.toScript());
613        //System.out.println("C = " + C.toScript());
614
615        factors = bf.baseFactorsSquarefreeBigPrime(A);
616        //System.out.println("factors = " + factors + "\n");
617        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
618        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
619    }
620
621
622    /**
623     * Compare Berlekamp with other factorization test.
624     */
625    public void testCompareFactorBerlekamp() {
626        int q = 32003; //11; 29; 
627        ModIntRing mi = new ModIntRing(q);
628        //System.out.println("mi = " + mi.toScript());
629        GenPolynomialRing<ModInt> pfac = new GenPolynomialRing<ModInt>(mi, new String[] { "x" });
630        //System.out.println("time pfac = " + pfac.toScript());
631        GenPolynomial<ModInt> A = pfac.parse("x^6 - 3 x^5 + x^4 - 3 x^3 - x^2 -3 x + 1");
632        //System.out.println("A = " + A.toScript());
633
634        FactorAbstract<ModInt> df = new FactorModular<ModInt>(pfac.coFac);
635        FactorModularBerlekamp<ModInt> bf = new FactorModularBerlekamp<ModInt>(pfac.coFac);
636        SortedMap<GenPolynomial<ModInt>, Long> factors, f2;
637
638        GenPolynomial<ModInt> B = pfac.random(kl, ll * ll + 20, el * el + 10, q + q).monic();
639        GenPolynomial<ModInt> C = pfac.random(kl, ll * ll + 20, el * el + 10, q + q).monic();
640        A = B.multiply(C);
641        //System.out.println("A = " + A.toScript());
642        //System.out.println("B = " + B.toScript());
643        //System.out.println("C = " + C.toScript());
644
645        long tb = System.currentTimeMillis();
646        factors = bf.baseFactors(A);
647        tb = System.currentTimeMillis() - tb;
648        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
649        //System.out.println("factors = " + factors + "\n");
650
651        long td = System.currentTimeMillis();
652        f2 = df.baseFactors(A);
653        td = System.currentTimeMillis() - td;
654        //System.out.println("tberle = " + tb + ", tdd = " + td + "\n");
655        assertEquals("factors == f2: ", factors, f2);
656        //System.out.println("isFactorization = " + bf.isFactorization(A,factors));
657        assertTrue("A == prod(factors): " + factors, bf.isFactorization(A, factors));
658        assertTrue("t >= 0: " + tb + ", " + td, tb >= 0 && td >= 0);
659    }
660
661}