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