Source code

001/*
002 * $Id: FactorModularTest.java 4019 2012-07-22 18:31:13Z 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        //BasicConfigurator.configure();
036        junit.textui.TestRunner.run(suite());
037    }
038
039
040    /**
041     * Constructs a <CODE>FactorModularTest</CODE> object.
042     * @param name String.
043     */
044    public FactorModularTest(String name) {
045        super(name);
046    }
047
048
049    /**
050     */
051    public static Test suite() {
052        TestSuite suite = new TestSuite(FactorModularTest.class);
053        return suite;
054    }
055
056
057    int rl = 3;
058
059
060    int kl = 5;
061
062
063    int ll = 5;
064
065
066    int el = 3;
067
068
069    float q = 0.3f;
070
071
072    @Override
073    protected void setUp() {
074    }
075
076
077    @Override
078    protected void tearDown() {
079        ComputerThreads.terminate();
080    }
081
082
083    /**
084     * Test dummy for Junit.
085     * 
086     */
087    public void testDummy() {
088    }
089
090
091    /**
092     * Test modular factorization.
093     * 
094     */
095    public void testModularFactorization() {
096
097        PrimeList pl = new PrimeList(PrimeList.Range.medium);
098        TermOrder to = new TermOrder(TermOrder.INVLEX);
099        ModIntegerRing cfac = new ModIntegerRing(pl.get(3));
100        //System.out.println("cfac = " + cfac);
101        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to);
102        FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac);
103
104        for (int i = 1; i < 4; i++) {
105            int facs = 0;
106            GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el*(i+1),q);
107            GenPolynomial<ModInteger> b = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
108            GenPolynomial<ModInteger> c = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
109            if (b.isZERO() || c.isZERO()) {
110                continue;
111            }
112            if (c.degree() > 0) {
113                facs++;
114            }
115            if (b.degree() > 0) {
116                facs++;
117            }
118            a = c.multiply(b);
119            if (a.isConstant()) {
120                continue;
121            }
122            a = a.monic();
123            //System.out.println("\na = " + a);
124            //System.out.println("b = " + b);
125            //System.out.println("c = " + c);
126
127            SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.baseFactors(a);
128            //System.out.println("sm = " + sm);
129
130            if (sm.size() >= facs) {
131                assertTrue("#facs < " + facs, sm.size() >= facs);
132            } else {
133                long sf = 0;
134                for (Long e : sm.values()) {
135                    sf += e;
136                }
137                assertTrue("#facs < " + facs, sf >= facs);
138            }
139
140            boolean t = fac.isFactorization(a, sm);
141            //System.out.println("t        = " + t);
142            assertTrue("prod(factor(a)) = a", t);
143        }
144    }
145
146
147    /**
148     * Test modular factorization example.
149     * 
150     */
151    public void testModularFactorizationExam() {
152
153        TermOrder to = new TermOrder(TermOrder.INVLEX);
154        ModIntegerRing cfac = new ModIntegerRing(7);
155        //System.out.println("cfac = " + cfac);
156        String[] vars = new String[] { "x" };
157        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to, vars);
158        FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac);
159
160        int facs = 3;
161        GenPolynomial<ModInteger> a = pfac.parse("(x^12+5)");
162        a = a.monic();
163        //System.out.println("\na = " + a);
164
165        SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.baseFactors(a);
166        //System.out.println("sm = " + sm);
167
168        if (sm.size() >= facs) {
169            assertTrue("#facs < " + facs, sm.size() >= facs);
170        } else {
171            long sf = 0;
172            for (Long e : sm.values()) {
173                sf += e;
174            }
175            assertTrue("#facs < " + facs, sf >= facs);
176        }
177
178        boolean t = fac.isFactorization(a, sm);
179        //System.out.println("t        = " + t);
180        assertTrue("prod(factor(a)) = a", t);
181    }
182
183
184    /**
185     * Test modular factorization, case p = 2.
186     * 
187     */
188    public void testModular2Factorization() {
189
190        TermOrder to = new TermOrder(TermOrder.INVLEX);
191        ModIntegerRing cfac = new ModIntegerRing(2L);
192        //System.out.println("cfac = " + cfac);
193        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to);
194        FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac);
195
196        for (int i = 1; i < 4; i++) {
197            int facs = 0;
198            GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el*(i+1),q);
199            GenPolynomial<ModInteger> b = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
200            GenPolynomial<ModInteger> c = pfac.random(kl, ll * (i + 1), el * (i + 1), q);
201            if (b.isZERO() || c.isZERO()) {
202                continue;
203            }
204            if (c.degree() > 0) {
205                facs++;
206            }
207            if (b.degree() > 0) {
208                facs++;
209            }
210            a = c.multiply(b);
211            if (a.isConstant()) {
212                continue;
213            }
214            a = a.monic();
215            //System.out.println("\na = " + a);
216            //System.out.println("b = " + b);
217            //System.out.println("c = " + c);
218
219            SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.baseFactors(a);
220            //System.out.println("sm = " + sm);
221
222            if (sm.size() >= facs) {
223                assertTrue("#facs < " + facs, sm.size() >= facs);
224            } else {
225                long sf = 0;
226                for (Long e : sm.values()) {
227                    sf += e;
228                }
229                assertTrue("#facs < " + facs, sf >= facs);
230            }
231
232            boolean t = fac.isFactorization(a, sm);
233            //System.out.println("t        = " + t);
234            assertTrue("prod(factor(a)) = a", t);
235        }
236    }
237
238
239    /**
240     * Test multivariate modular factorization.
241     * 
242     */
243    public void testMultivariateModularFactorization() {
244
245        //PrimeList pl = new PrimeList(PrimeList.Range.small);
246        TermOrder to = new TermOrder(TermOrder.INVLEX);
247        ModIntegerRing cfac = new ModIntegerRing(13); // pl.get(3), 7, 11, 13
248        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, rl, to);
249        FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac);
250
251        for (int i = 1; i < 2; i++) {
252            int facs = 0;
253            GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el,q);
254            GenPolynomial<ModInteger> b = pfac.random(kl, 2, el, q);
255            GenPolynomial<ModInteger> c = pfac.random(kl, 2, el, q);
256            if (b.isZERO() || c.isZERO()) {
257                continue;
258            }
259            if (c.degree() > 0) {
260                facs++;
261            }
262            if (b.degree() > 0) {
263                facs++;
264            }
265            a = c.multiply(b);
266            if (a.isConstant()) {
267                continue;
268            }
269            //a = a.monic();
270            //System.out.println("\na = " + a);
271            //System.out.println("b = " + b);
272            //System.out.println("c = " + c);
273
274            SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.factors(a);
275            //System.out.println("sm = " + sm);
276
277            if (sm.size() >= facs) {
278                assertTrue("#facs < " + facs, sm.size() >= facs);
279            } else {
280                long sf = 0;
281                for (Long e : sm.values()) {
282                    sf += e;
283                }
284                assertTrue("#facs < " + facs, sf >= facs);
285            }
286
287            boolean t = fac.isFactorization(a, sm);
288            //System.out.println("t        = " + t);
289            assertTrue("prod(factor(a)) = a", t);
290        }
291    }
292
293
294    /**
295     * Test modular absolute factorization.
296     * 
297     */
298    public void testBaseModularAbsoluteFactorization() {
299
300        TermOrder to = new TermOrder(TermOrder.INVLEX);
301        ModIntegerRing cfac = new ModIntegerRing(17);
302        String[] alpha = new String[] { "alpha" };
303        //String[] vars = new String[] { "z" };
304        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to, alpha);
305        GenPolynomial<ModInteger> agen = pfac.univariate(0, 4);
306        agen = agen.sum(pfac.fromInteger(1)); // x^4 + 1
307
308        FactorModular<ModInteger> engine = new FactorModular<ModInteger>(cfac);
309
310        FactorsMap<ModInteger> F
311        //= engine.baseFactorsAbsoluteSquarefree(agen);
312        //= engine.baseFactorsAbsoluteIrreducible(agen);
313        = engine.baseFactorsAbsolute(agen);
314        //System.out.println("agen        = " + agen);
315        //System.out.println("F           = " + F);
316
317        boolean t = engine.isAbsoluteFactorization(F);
318        //System.out.println("t        = " + t);
319        assertTrue("prod(factor(a)) = a", t);
320    }
321
322}