001 /*
002 * $Id: SquarefreeModTest.java 2728 2009-07-09 22:02:44Z 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.kern.ComputerThreads;
017 import edu.jas.poly.ExpVector;
018 import edu.jas.poly.GenPolynomial;
019 import edu.jas.poly.GenPolynomialRing;
020 import edu.jas.poly.PolyUtil;
021 import edu.jas.poly.TermOrder;
022 import edu.jas.structure.Power;
023
024
025 /**
026 * Squarefree factorization tests with JUnit.
027 * @author Heinz Kredel.
028 */
029
030 public class SquarefreeModTest extends TestCase {
031
032
033 /**
034 * main.
035 */
036 public static void main(String[] args) {
037 //BasicConfigurator.configure();
038 junit.textui.TestRunner.run(suite());
039 ComputerThreads.terminate();
040 }
041
042
043 /**
044 * Constructs a <CODE>SquarefreeModTest</CODE> object.
045 * @param name String.
046 */
047 public SquarefreeModTest(String name) {
048 super(name);
049 }
050
051
052 /**
053 */
054 public static Test suite() {
055 TestSuite suite = new TestSuite(SquarefreeModTest.class);
056 return suite;
057 }
058
059
060 TermOrder to = new TermOrder(TermOrder.INVLEX);
061
062
063 int rl = 3;
064
065
066 int kl = 3;
067
068
069 int ll = 4;
070
071
072 int el = 3;
073
074
075 float q = 0.25f;
076
077
078 String[] vars;
079
080
081 String[] cvars;
082
083
084 String[] c1vars;
085
086
087 String[] rvars;
088
089
090 ModIntegerRing fac;
091
092
093 GreatestCommonDivisorAbstract<ModInteger> ufd;
094
095
096 SquarefreeFiniteFieldCharP<ModInteger> sqf;
097
098
099 GenPolynomialRing<ModInteger> dfac;
100
101
102 GenPolynomial<ModInteger> a;
103
104
105 GenPolynomial<ModInteger> b;
106
107
108 GenPolynomial<ModInteger> c;
109
110
111 GenPolynomial<ModInteger> d;
112
113
114 GenPolynomial<ModInteger> e;
115
116
117 GenPolynomialRing<ModInteger> cfac;
118
119
120 GenPolynomialRing<GenPolynomial<ModInteger>> rfac;
121
122
123 GenPolynomial<GenPolynomial<ModInteger>> ar;
124
125
126 GenPolynomial<GenPolynomial<ModInteger>> br;
127
128
129 GenPolynomial<GenPolynomial<ModInteger>> cr;
130
131
132 GenPolynomial<GenPolynomial<ModInteger>> dr;
133
134
135 GenPolynomial<GenPolynomial<ModInteger>> er;
136
137
138 @Override
139 protected void setUp() {
140 vars = ExpVector.STDVARS(rl);
141 cvars = ExpVector.STDVARS(rl - 1);
142 c1vars = new String[] { cvars[0] };
143 rvars = new String[] { vars[rl - 1] };
144
145 fac = new ModIntegerRing(11);
146 //ufd = new GreatestCommonDivisorSubres<ModInteger>();
147 //ufd = GCDFactory.<ModInteger> getImplementation(fac);
148 ufd = GCDFactory.getProxy(fac);
149 sqf = new SquarefreeFiniteFieldCharP<ModInteger>(fac);
150
151 a = b = c = d = e = null;
152 ar = br = cr = dr = er = null;
153 }
154
155
156 @Override
157 protected void tearDown() {
158 a = b = c = d = e = null;
159 ar = br = cr = dr = er = null;
160 //ComputerThreads.terminate();
161 }
162
163
164 /**
165 * Test base squarefree.
166 *
167 */
168 public void testBaseSquarefree() {
169 //System.out.println("\nbase:");
170
171 dfac = new GenPolynomialRing<ModInteger>(fac, 1, to, rvars);
172
173 a = dfac.random(kl, ll, el + 2, q);
174 b = dfac.random(kl, ll, el + 2, q);
175 c = dfac.random(kl, ll, el, q);
176 //System.out.println("a = " + a);
177 //System.out.println("b = " + b);
178 //System.out.println("c = " + c);
179
180 if (a.isZERO() || b.isZERO() || c.isZERO()) {
181 // skip for this turn
182 return;
183 }
184
185 // a a b b b c
186 d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
187 c = a.multiply(b).multiply(c);
188 //System.out.println("c = " + c);
189 //System.out.println("d = " + d);
190
191 c = sqf.baseSquarefreePart(c);
192 d = sqf.baseSquarefreePart(d);
193 //System.out.println("c = " + c);
194 //System.out.println("d = " + d);
195 assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
196 assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
197
198 e = PolyUtil.<ModInteger> basePseudoRemainder(d, c);
199 //System.out.println("e = " + e);
200 assertTrue("squarefree(abc) | squarefree(aabbbc) " + e, e.isZERO());
201 }
202
203
204 /**
205 * Test base squarefree factors.
206 *
207 */
208 public void testBaseSquarefreeFactors() {
209
210 dfac = new GenPolynomialRing<ModInteger>(fac, 1, to, rvars);
211
212 a = dfac.random(kl, ll, el + 3, q);
213 b = dfac.random(kl, ll, el + 3, q);
214 c = dfac.random(kl, ll, el + 2, q);
215 //System.out.println("a = " + a);
216 //System.out.println("b = " + b);
217 //System.out.println("c = " + c);
218
219 if (a.isZERO() || b.isZERO() || c.isZERO()) {
220 // skip for this turn
221 return;
222 }
223
224 // a a b b b c
225 d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
226 //System.out.println("d = " + d);
227
228 SortedMap<GenPolynomial<ModInteger>, Long> sfactors;
229 sfactors = sqf.baseSquarefreeFactors(d);
230 //System.out.println("sfactors = " + sfactors);
231 assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
232 }
233
234
235 /**
236 * Test recursive squarefree.
237 *
238 */
239 public void testRecursiveSquarefree() {
240 //System.out.println("\nrecursive:");
241
242 cfac = new GenPolynomialRing<ModInteger>(fac, 2 - 1, to, c1vars);
243 rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to, rvars);
244
245 ar = rfac.random(kl, ll, el, q);
246 br = rfac.random(kl, ll, el, q);
247 cr = rfac.random(kl, ll, el, q);
248 //System.out.println("ar = " + ar);
249 //System.out.println("br = " + br);
250 //System.out.println("cr = " + cr);
251
252 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
253 // skip for this turn
254 return;
255 }
256
257 dr = ar.multiply(ar).multiply(br).multiply(br);
258 cr = ar.multiply(br);
259 //System.out.println("cr = " + cr);
260 //System.out.println("dr = " + dr);
261
262 cr = sqf.recursiveUnivariateSquarefreePart(cr);
263 dr = sqf.recursiveUnivariateSquarefreePart(dr);
264 //System.out.println("cr = " + cr);
265 //System.out.println("dr = " + dr);
266 assertTrue("isSquarefree(cr) " + cr, sqf.isRecursiveSquarefree(cr));
267 assertTrue("isSquarefree(dr) " + dr, sqf.isRecursiveSquarefree(dr));
268
269 er = PolyUtil.<ModInteger> recursivePseudoRemainder(dr, cr);
270 //System.out.println("er = " + er);
271 assertTrue("squarefree(abc) | squarefree(aabbc) " + er, er.isZERO());
272 }
273
274
275 /**
276 * Test recursive squarefree factors.
277 *
278 */
279 public void testRecursiveSquarefreeFactors() {
280
281 cfac = new GenPolynomialRing<ModInteger>(fac, 2 - 1, to, c1vars);
282 rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to, rvars);
283
284 ar = rfac.random(kl, 3, 2, q);
285 br = rfac.random(kl, 3, 2, q);
286 cr = rfac.random(kl, 3, 2, q);
287 //System.out.println("ar = " + ar);
288 //System.out.println("br = " + br);
289 //System.out.println("cr = " + cr);
290
291 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
292 // skip for this turn
293 return;
294 }
295
296 dr = ar.multiply(cr).multiply(br).multiply(br);
297 //System.out.println("dr = " + dr);
298
299 SortedMap<GenPolynomial<GenPolynomial<ModInteger>>, Long> sfactors;
300 sfactors = sqf.recursiveUnivariateSquarefreeFactors(dr);
301 //System.out.println("sfactors = " + sfactors);
302 assertTrue("isFactorization(d,sfactors) ", sqf.isRecursiveFactorization(dr, sfactors));
303 }
304
305
306 /**
307 * Test squarefree.
308 *
309 */
310 public void testSquarefree() {
311 //System.out.println("\nfull:");
312
313 dfac = new GenPolynomialRing<ModInteger>(fac, rl, to, vars);
314
315 a = dfac.random(kl, ll, 2, q);
316 b = dfac.random(kl, ll, 2, q);
317 c = dfac.random(kl, ll, 2, q);
318 //System.out.println("a = " + a);
319 //System.out.println("b = " + b);
320 //System.out.println("c = " + c);
321
322 if (a.isZERO() || b.isZERO() || c.isZERO()) {
323 // skip for this turn
324 return;
325 }
326
327 d = a.multiply(a).multiply(b).multiply(b).multiply(c);
328 c = a.multiply(b).multiply(c);
329 //System.out.println("c = " + c);
330 //System.out.println("d = " + d);
331
332 c = sqf.squarefreePart(c);
333 d = sqf.squarefreePart(d);
334 //System.out.println("c = " + c);
335 //System.out.println("d = " + d);
336 assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
337 assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
338
339 e = PolyUtil.<ModInteger> basePseudoRemainder(d, c);
340 //System.out.println("e = " + e);
341 assertTrue("squarefree(abc) | squarefree(aabbc) " + e, e.isZERO());
342 }
343
344
345 /**
346 * Test squarefree factors.
347 *
348 */
349 public void testSquarefreeFactors() {
350
351 dfac = new GenPolynomialRing<ModInteger>(fac, rl, to, vars);
352
353 a = dfac.random(kl, 3, 2, q);
354 b = dfac.random(kl, 3, 2, q);
355 c = dfac.random(kl, 3, 2, q);
356 //System.out.println("a = " + a);
357 //System.out.println("b = " + b);
358 //System.out.println("c = " + c);
359
360 if (a.isZERO() || b.isZERO() || c.isZERO()) {
361 // skip for this turn
362 return;
363 }
364
365 d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
366 //System.out.println("d = " + d);
367
368 SortedMap<GenPolynomial<ModInteger>, Long> sfactors;
369 sfactors = sqf.squarefreeFactors(d);
370 //System.out.println("sfactors = " + sfactors);
371 assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
372 }
373
374
375 /* ------------char-th root ------------------------- */
376
377 /**
378 * Test base squarefree with char-th root.
379 *
380 */
381 public void testBaseSquarefreeCharRoot() {
382 //System.out.println("\nbase CharRoot:");
383
384 long p = fac.characteristic().longValue();
385
386 dfac = new GenPolynomialRing<ModInteger>(fac, 1, to, rvars);
387
388 a = dfac.random(kl, ll + 2, el + 2, q);
389 b = dfac.random(kl, ll + 2, el + 2, q);
390 c = dfac.random(kl, ll, el, q);
391
392 if (a.isZERO() || b.isZERO() || c.isZERO() || a.isConstant() || b.isConstant()) {
393 // skip for this turn
394 return;
395 }
396 //System.out.println("a = " + a);
397 //System.out.println("b = " + b);
398 //System.out.println("c = " + c);
399
400 // a a b^p c
401 d = a.multiply(a).multiply(Power.<GenPolynomial<ModInteger>> positivePower(b, p)).multiply(c);
402 c = a.multiply(b).multiply(c);
403 //System.out.println("c = " + c);
404 //System.out.println("d = " + d);
405
406 c = sqf.baseSquarefreePart(c);
407 d = sqf.baseSquarefreePart(d);
408 //System.out.println("c = " + c);
409 //System.out.println("d = " + d);
410 assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
411 assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
412
413 e = PolyUtil.<ModInteger> basePseudoRemainder(d, c);
414 //System.out.println("e = " + e);
415 assertTrue("squarefree(abc) | squarefree(aab^pc) " + e, e.isZERO());
416 }
417
418
419 /**
420 * Test base squarefree factors with char-th root.
421 *
422 */
423 public void testBaseSquarefreeFactorsCharRoot() {
424
425 long p = fac.characteristic().longValue();
426
427 dfac = new GenPolynomialRing<ModInteger>(fac, 1, to, rvars);
428
429 a = dfac.random(kl, ll + 2, el + 3, q);
430 b = dfac.random(kl, ll + 2, el + 3, q);
431 c = dfac.random(kl, ll, el + 2, q);
432
433 if (a.isZERO() || b.isZERO() || c.isZERO() || a.isConstant() || b.isConstant()) {
434 // skip for this turn
435 return;
436 }
437 //System.out.println("a = " + a);
438 //System.out.println("b = " + b);
439 //System.out.println("c = " + c);
440
441 // a a b^p c
442 d = a.multiply(a).multiply(Power.<GenPolynomial<ModInteger>> positivePower(b, p)).multiply(c);
443 //System.out.println("d = " + d);
444
445 SortedMap<GenPolynomial<ModInteger>, Long> sfactors;
446 sfactors = sqf.baseSquarefreeFactors(d);
447 //System.out.println("sfactors = " + sfactors);
448 assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
449 }
450
451
452 /**
453 * Test recursive squarefree with char-th root.
454 *
455 */
456 public void testRecursiveSquarefreeCharRoot() {
457 //System.out.println("\nrecursive CharRoot:");
458
459 long p = fac.characteristic().longValue();
460
461 cfac = new GenPolynomialRing<ModInteger>(fac, 2 - 1, to, c1vars);
462 rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to, rvars);
463
464 ar = rfac.random(kl, ll, el + 1, q).monic();
465 br = rfac.random(kl, ll, el + 1, q).monic();
466 cr = rfac.random(kl, ll, el, q).monic();
467
468 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
469 // skip for this turn
470 return;
471 }
472 //System.out.println("ar = " + ar);
473 //System.out.println("br = " + br);
474 //System.out.println("cr = " + cr);
475
476 // a a b^p
477 dr = ar.multiply(ar).multiply(Power.<GenPolynomial<GenPolynomial<ModInteger>>> positivePower(br, p));
478 cr = ar.multiply(ar).multiply(br);
479 //System.out.println("cr = " + cr);
480 //System.out.println("dr = " + dr);
481
482 cr = sqf.recursiveUnivariateSquarefreePart(cr);
483 dr = sqf.recursiveUnivariateSquarefreePart(dr);
484 //System.out.println("cr = " + cr);
485 //System.out.println("dr = " + dr);
486 assertTrue("isSquarefree(cr) " + cr, sqf.isRecursiveSquarefree(cr));
487 assertTrue("isSquarefree(dr) " + dr, sqf.isRecursiveSquarefree(dr));
488
489 er = PolyUtil.<ModInteger> recursivePseudoRemainder(dr, cr);
490 //System.out.println("er = " + er);
491 assertTrue("squarefree(abc) | squarefree(aabbc) " + er, er.isZERO());
492 }
493
494
495 /**
496 * Test recursive squarefree factors with char-th root.
497 *
498 */
499 public void testRecursiveSquarefreeFactorsCharRoot() {
500
501 long p = fac.characteristic().longValue();
502
503 cfac = new GenPolynomialRing<ModInteger>(fac, 2 - 1, to, c1vars);
504 rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to, rvars);
505
506 ar = rfac.random(kl, 3, 2 + 1, q).monic();
507 br = rfac.random(kl, 3, 2 + 1, q).monic();
508 cr = rfac.random(kl, 3, 2, q).monic();
509
510 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
511 // skip for this turn
512 return;
513 }
514 //System.out.println("ar = " + ar);
515 //System.out.println("br = " + br);
516 //System.out.println("cr = " + cr);
517
518 // a a b^p c
519 dr = ar.multiply(ar).multiply(Power.<GenPolynomial<GenPolynomial<ModInteger>>> positivePower(br, p)).multiply(cr);
520 //System.out.println("dr = " + dr);
521
522 SortedMap<GenPolynomial<GenPolynomial<ModInteger>>, Long> sfactors;
523 sfactors = sqf.recursiveUnivariateSquarefreeFactors(dr);
524 //System.out.println("sfactors = " + sfactors);
525 assertTrue("isFactorization(d,sfactors) ", sqf.isRecursiveFactorization(dr, sfactors));
526 }
527
528
529 /**
530 * Test squarefree with char-th root.
531 *
532 */
533 public void testSquarefreeCharRoot() {
534 //System.out.println("\nfull CharRoot:");
535
536 long p = fac.characteristic().longValue();
537
538 dfac = new GenPolynomialRing<ModInteger>(fac, rl, to, vars);
539
540 a = dfac.random(kl, ll, 3, q).monic();
541 b = dfac.random(kl, ll, 3, q).monic();
542 c = dfac.random(kl, ll, 3, q).monic();
543
544 if (a.isZERO() || b.isZERO() || c.isZERO()) {
545 // skip for this turn
546 return;
547 }
548 //System.out.println("a = " + a);
549 //System.out.println("b = " + b);
550 //System.out.println("c = " + c);
551
552 // a a b^p c
553 d = a.multiply(a).multiply(Power.<GenPolynomial<ModInteger>> positivePower(b, p)).multiply(c);
554 c = a.multiply(b).multiply(c);
555 //System.out.println("c = " + c);
556 //System.out.println("d = " + d);
557
558 c = sqf.squarefreePart(c);
559 d = sqf.squarefreePart(d);
560 //System.out.println("c = " + c);
561 //System.out.println("d = " + d);
562 assertTrue("isSquarefree(d) " + d, sqf.isSquarefree(d));
563 assertTrue("isSquarefree(c) " + c, sqf.isSquarefree(c));
564
565 e = PolyUtil.<ModInteger> basePseudoRemainder(d, c);
566 //System.out.println("e = " + e);
567 assertTrue("squarefree(abc) | squarefree(aab^pc) " + e, e.isZERO());
568 }
569
570
571 /**
572 * Test squarefree factors with char-th root.
573 *
574 */
575 public void testSquarefreeFactorsCharRoot() {
576
577 long p = fac.characteristic().longValue();
578
579 dfac = new GenPolynomialRing<ModInteger>(fac, rl, to, vars);
580
581 a = dfac.random(kl, ll, 3, q).monic();
582 b = dfac.random(kl, ll, 3, q).monic();
583 c = dfac.random(kl, ll, 3, q).monic();
584
585 if (a.isZERO() || b.isZERO() || c.isZERO()) {
586 // skip for this turn
587 return;
588 }
589 //System.out.println("a = " + a);
590 //System.out.println("b = " + b);
591 //System.out.println("c = " + c);
592
593 // a a b^p c
594 d = a.multiply(a).multiply(Power.<GenPolynomial<ModInteger>> positivePower(b, p)).multiply(c);
595 //System.out.println("d = " + d);
596
597 SortedMap<GenPolynomial<ModInteger>, Long> sfactors;
598 sfactors = sqf.squarefreeFactors(d);
599 //System.out.println("sfactors = " + sfactors);
600 assertTrue("isFactorization(d,sfactors) ", sqf.isFactorization(d, sfactors));
601 }
602
603 }