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