Source code

001/*
002 * $Id: FactorModularTest.java 5863 2018-07-20 11:13:34Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.SortedMap;
009
010import junit.framework.Test;
011import junit.framework.TestCase;
012import junit.framework.TestSuite;
013
014import edu.jas.arith.ModInteger;
015import edu.jas.arith.ModIntegerRing;
016import edu.jas.arith.PrimeList;
017import edu.jas.kern.ComputerThreads;
018import edu.jas.poly.GenPolynomial;
019import edu.jas.poly.GenPolynomialRing;
020import edu.jas.poly.TermOrder;
021
022
023/**
024 * Factor modular tests with JUnit.
025 * @author Heinz Kredel
026 */
027
028public class FactorModularTest extends TestCase {
029
030
031    /**
032     * main.
033     */
034    public static void main(String[] args) {
035        junit.textui.TestRunner.run(suite());
036    }
037
038
039    /**
040     * Constructs a <CODE>FactorModularTest</CODE> object.
041     * @param name String.
042     */
043    public FactorModularTest(String name) {
044        super(name);
045    }
046
047
048    /**
049     */
050    public static Test suite() {
051        TestSuite suite = new TestSuite(FactorModularTest.class);
052        return suite;
053    }
054
055
056    int rl = 3;
057
058
059    int kl = 5;
060
061
062    int ll = 5;
063
064
065    int el = 3;
066
067
068    float q = 0.3f;
069
070
071    @Override
072    protected void setUp() {
073    }
074
075
076    @Override
077    protected void tearDown() {
078        ComputerThreads.terminate();
079    }
080
081
082    /**
083     * Test dummy for Junit.
084     * 
085     */
086    public void testDummy() {
087    }
088
089
090    /**
091     * Test modular factorization.
092     * 
093     */
094    public void testModularFactorization() {
095
096        PrimeList pl = new PrimeList(PrimeList.Range.medium);
097        TermOrder to = new TermOrder(TermOrder.INVLEX);
098        ModIntegerRing cfac = new ModIntegerRing(pl.get(3));
099        //System.out.println("cfac = " + cfac);
100        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to);
101        FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac);
102
103        for (int i = 1; i < 4; i++) {
104            int facs = 0;
105            GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el*(i+1),q);
106            GenPolynomial<ModInteger> b = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
107            GenPolynomial<ModInteger> c = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
108            if (b.isZERO() || c.isZERO()) {
109                continue;
110            }
111            if (c.degree() > 0) {
112                facs++;
113            }
114            if (b.degree() > 0) {
115                facs++;
116            }
117            a = c.multiply(b);
118            if (a.isConstant()) {
119                continue;
120            }
121            a = a.monic();
122            //System.out.println("\na = " + a);
123            //System.out.println("b = " + b);
124            //System.out.println("c = " + c);
125
126            SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.baseFactors(a);
127            //System.out.println("sm = " + sm);
128
129            if (sm.size() >= facs) {
130                assertTrue("#facs < " + facs, sm.size() >= facs);
131            } else {
132                long sf = 0;
133                for (Long e : sm.values()) {
134                    sf += e;
135                }
136                assertTrue("#facs < " + facs, sf >= facs);
137            }
138
139            boolean t = fac.isFactorization(a, sm);
140            //System.out.println("t        = " + t);
141            assertTrue("prod(factor(a)) = a", t);
142        }
143    }
144
145
146    /**
147     * Test modular factorization example.
148     * 
149     */
150    public void testModularFactorizationExam() {
151
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     */
187    public void testModular2Factorization() {
188
189        TermOrder to = new TermOrder(TermOrder.INVLEX);
190        ModIntegerRing cfac = new ModIntegerRing(2L);
191        //System.out.println("cfac = " + cfac);
192        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to);
193        FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac);
194
195        for (int i = 1; i < 4; i++) {
196            int facs = 0;
197            GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el*(i+1),q);
198            GenPolynomial<ModInteger> b = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
199            GenPolynomial<ModInteger> c = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
200            if (b.isZERO() || c.isZERO()) {
201                continue;
202            }
203            if (c.degree() > 0) {
204                facs++;
205            }
206            if (b.degree() > 0) {
207                facs++;
208            }
209            a = c.multiply(b);
210            if (a.isConstant()) {
211                continue;
212            }
213            a = a.monic();
214            //System.out.println("\na = " + a);
215            //System.out.println("b = " + b);
216            //System.out.println("c = " + c);
217
218            SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.baseFactors(a);
219            //System.out.println("sm = " + sm);
220
221            if (sm.size() >= facs) {
222                assertTrue("#facs < " + facs, sm.size() >= facs);
223            } else {
224                long sf = 0;
225                for (Long e : sm.values()) {
226                    sf += e;
227                }
228                assertTrue("#facs < " + facs, sf >= facs);
229            }
230
231            boolean t = fac.isFactorization(a, sm);
232            //System.out.println("t        = " + t);
233            assertTrue("prod(factor(a)) = a", t);
234        }
235    }
236
237
238    /**
239     * Test multivariate modular factorization.
240     * 
241     */
242    public void testMultivariateModularFactorization() {
243
244        //PrimeList pl = new PrimeList(PrimeList.Range.small);
245        TermOrder to = new TermOrder(TermOrder.INVLEX);
246        ModIntegerRing cfac = new ModIntegerRing(13); // pl.get(3), 7, 11, 13
247        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, rl, to);
248        FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac);
249
250        for (int i = 1; i < 2; i++) {
251            int facs = 0;
252            GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el,q);
253            GenPolynomial<ModInteger> b = pfac.random(kl, 2, el, q);
254            GenPolynomial<ModInteger> c = pfac.random(kl, 2, el, q);
255            if (b.isZERO() || c.isZERO()) {
256                continue;
257            }
258            if (c.degree() > 0) {
259                facs++;
260            }
261            if (b.degree() > 0) {
262                facs++;
263            }
264            a = c.multiply(b);
265            if (a.isConstant()) {
266                continue;
267            }
268            //a = a.monic();
269            //System.out.println("\na = " + a);
270            //System.out.println("b = " + b);
271            //System.out.println("c = " + c);
272
273            SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.factors(a);
274            //System.out.println("sm = " + sm);
275
276            if (sm.size() >= facs) {
277                assertTrue("#facs < " + facs, sm.size() >= facs);
278            } else {
279                long sf = 0;
280                for (Long e : sm.values()) {
281                    sf += e;
282                }
283                assertTrue("#facs < " + facs, sf >= facs);
284            }
285
286            boolean t = fac.isFactorization(a, sm);
287            //System.out.println("t        = " + t);
288            assertTrue("prod(factor(a)) = a", t);
289        }
290    }
291
292
293    /**
294     * Test modular absolute factorization.
295     * 
296     */
297    public void testBaseModularAbsoluteFactorization() {
298
299        TermOrder to = new TermOrder(TermOrder.INVLEX);
300        ModIntegerRing cfac = new ModIntegerRing(17);
301        String[] alpha = new String[] { "alpha" };
302        //String[] vars = new String[] { "z" };
303        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to, alpha);
304        GenPolynomial<ModInteger> agen = pfac.univariate(0, 4);
305        agen = agen.sum(pfac.fromInteger(1)); // x^4 + 1
306
307        FactorModular<ModInteger> engine = new FactorModular<ModInteger>(cfac);
308
309        FactorsMap<ModInteger> F
310        //= engine.baseFactorsAbsoluteSquarefree(agen);
311        //= engine.baseFactorsAbsoluteIrreducible(agen);
312        = engine.baseFactorsAbsolute(agen);
313        //System.out.println("agen        = " + agen);
314        //System.out.println("F           = " + F);
315
316        boolean t = engine.isAbsoluteFactorization(F);
317        //System.out.println("t        = " + t);
318        assertTrue("prod(factor(a)) = a", t);
319    }
320
321}