001 /*
002 * $Id: FactorModularTest.java 3295 2010-08-26 17:01:10Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.SortedMap;
009
010 import junit.framework.Test;
011 import junit.framework.TestCase;
012 import junit.framework.TestSuite;
013
014 import edu.jas.arith.ModInteger;
015 import edu.jas.arith.ModIntegerRing;
016 import edu.jas.arith.PrimeList;
017 import edu.jas.kern.ComputerThreads;
018 import edu.jas.poly.GenPolynomial;
019 import edu.jas.poly.GenPolynomialRing;
020 import edu.jas.poly.TermOrder;
021
022
023 /**
024 * Factor modular tests with JUnit.
025 * @author Heinz Kredel.
026 */
027
028 public 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 }