001 /*
002 * $Id: GCDModLongEvalTest.java 2931 2009-12-29 08:27:22Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010
011 import junit.framework.Test;
012 import junit.framework.TestCase;
013 import junit.framework.TestSuite;
014
015 import edu.jas.arith.ModLong;
016 import edu.jas.arith.ModLongRing;
017 import edu.jas.arith.PrimeList;
018 import edu.jas.poly.ExpVector;
019 import edu.jas.poly.GenPolynomial;
020 import edu.jas.poly.GenPolynomialRing;
021 import edu.jas.poly.PolyUtil;
022 import edu.jas.poly.TermOrder;
023
024
025 /**
026 * GCD Modular Evaluation algorithm tests with JUnit.
027 * @author Heinz Kredel.
028 */
029
030 public class GCDModLongEvalTest extends TestCase {
031
032
033 /**
034 * main.
035 */
036 public static void main(String[] args) {
037 junit.textui.TestRunner.run(suite());
038 }
039
040
041 /**
042 * Constructs a <CODE>GCDModLongEvalTest</CODE> object.
043 * @param name String.
044 */
045 public GCDModLongEvalTest(String name) {
046 super(name);
047 }
048
049
050 /**
051 */
052 public static Test suite() {
053 TestSuite suite = new TestSuite(GCDModLongEvalTest.class);
054 return suite;
055 }
056
057
058 //private final static int bitlen = 100;
059
060 GreatestCommonDivisorAbstract<ModLong> ufd;
061
062
063 TermOrder to = new TermOrder(TermOrder.INVLEX);
064
065
066 GenPolynomialRing<ModLong> dfac;
067
068
069 GenPolynomialRing<ModLong> cfac;
070
071
072 GenPolynomialRing<GenPolynomial<ModLong>> rfac;
073
074
075 PrimeList primes = new PrimeList();
076
077
078 ModLongRing mi;
079
080
081 ModLong ai;
082
083
084 ModLong bi;
085
086
087 ModLong ci;
088
089
090 ModLong di;
091
092
093 ModLong ei;
094
095
096 GenPolynomial<ModLong> a;
097
098
099 GenPolynomial<ModLong> b;
100
101
102 GenPolynomial<ModLong> c;
103
104
105 GenPolynomial<ModLong> d;
106
107
108 GenPolynomial<ModLong> e;
109
110
111 GenPolynomial<GenPolynomial<ModLong>> ar;
112
113
114 GenPolynomial<GenPolynomial<ModLong>> br;
115
116
117 GenPolynomial<GenPolynomial<ModLong>> cr;
118
119
120 GenPolynomial<GenPolynomial<ModLong>> dr;
121
122
123 GenPolynomial<GenPolynomial<ModLong>> er;
124
125
126 int rl = 3;
127
128
129 int kl = 4;
130
131
132 int ll = 5;
133
134
135 int el = 3;
136
137
138 float q = 0.3f;
139
140
141 @Override
142 protected void setUp() {
143 a = b = c = d = e = null;
144 ai = bi = ci = di = ei = null;
145 ar = br = cr = dr = er = null;
146 //mi = new ModLongRing(primes.get(0),true);
147 mi = new ModLongRing(19, true);
148 //mi = new ModLongRing(19*17,true); // failing tests
149 //mi = new ModLongRing(primes.get(0).multiply(primes.get(1)),false); // failing tests
150 //ufd = new GreatestCommonDivisorPrimitive<ModLong>();
151 ufd = new GreatestCommonDivisorModEval<ModLong>();
152 String[] vars = ExpVector.STDVARS(rl);
153 String[] cvars = ExpVector.STDVARS(rl - 1);
154 String[] rvars = new String[] { vars[rl - 1] };
155 dfac = new GenPolynomialRing<ModLong>(mi, rl, to, vars);
156 cfac = new GenPolynomialRing<ModLong>(mi, rl - 1, to, cvars);
157 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to, rvars);
158 //System.out.println("mi = " + mi);
159 }
160
161
162 @Override
163 protected void tearDown() {
164 a = b = c = d = e = null;
165 ai = bi = ci = di = ei = null;
166 ar = br = cr = dr = er = null;
167 mi = null;
168 ufd = null;
169 dfac = null;
170 cfac = null;
171 rfac = null;
172 }
173
174
175 /**
176 * Test modular evaluation gcd.
177 *
178 */
179 public void testModEvalGcd() {
180
181 //GreatestCommonDivisorAbstract<ModLong> ufd_me
182 // = new GreatestCommonDivisorModEval();
183
184 for (int i = 0; i < 1; i++) {
185 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q);
186 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q);
187 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 0 * i, q);
188 c = c.multiply(dfac.univariate(0));
189 //a = ufd.basePrimitivePart(a);
190 //b = ufd.basePrimitivePart(b);
191
192 if (a.isZERO() || b.isZERO() || c.isZERO()) {
193 // skip for this turn
194 continue;
195 }
196 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
197 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
198 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
199
200 a = a.multiply(c);
201 b = b.multiply(c);
202 //System.out.println("a = " + a);
203 //System.out.println("b = " + b);
204
205 d = ufd.gcd(a, b);
206
207 c = ufd.basePrimitivePart(c).abs();
208 e = PolyUtil.<ModLong> basePseudoRemainder(d, c);
209 //System.out.println("c = " + c);
210 //System.out.println("d = " + d);
211 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
212
213 e = PolyUtil.<ModLong> basePseudoRemainder(a, d);
214 //System.out.println("e = " + e);
215 assertTrue("gcd(a,b) | a" + e, e.isZERO());
216
217 e = PolyUtil.<ModLong> basePseudoRemainder(b, d);
218 //System.out.println("e = " + e);
219 assertTrue("gcd(a,b) | b" + e, e.isZERO());
220 }
221 }
222
223
224 /**
225 * Test base quotioent and remainder.
226 *
227 */
228 public void testBaseQR() {
229
230 dfac = new GenPolynomialRing<ModLong>(mi, 1, to);
231
232 for (int i = 0; i < 5; i++) {
233 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
234 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
235 //a = ufd.basePrimitivePart(a).abs();
236 //c = ufd.basePrimitivePart(c);
237 do {
238 ci = mi.random(kl * (i + 2));
239 ci = ci.sum(mi.getONE());
240 } while (ci.isZERO());
241
242 //System.out.println("a = " + a);
243 //System.out.println("c = " + c);
244 //System.out.println("ci = " + ci);
245
246 if (a.isZERO() || c.isZERO()) {
247 // skip for this turn
248 continue;
249 }
250 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
251 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
252 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
253
254 b = a.multiply(c);
255 //System.out.println("b = " + b);
256 d = PolyUtil.<ModLong> basePseudoRemainder(b, c);
257 //System.out.println("d = " + d);
258
259 assertTrue("rem(ac,c) == 0", d.isZERO());
260
261 b = a.multiply(ci);
262 //System.out.println("b = " + b);
263 d = b.divide(ci);
264 //System.out.println("d = " + d);
265
266 assertEquals("a == ac/c", a, d);
267
268 b = a.multiply(c);
269 //System.out.println("b = " + b);
270 d = PolyUtil.<ModLong> basePseudoDivide(b, c);
271 //System.out.println("d = " + d);
272
273 assertEquals("a == ac/c", a, d);
274 }
275 }
276
277
278 /**
279 * Test base content and primitive part.
280 *
281 */
282 public void testBaseContentPP() {
283
284 for (int i = 0; i < 13; i++) {
285 c = dfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
286 c = c.multiply(mi.random(kl * (i + 2)));
287
288 if (c.isZERO()) {
289 // skip for this turn
290 continue;
291 }
292 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
293 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
294 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
295
296 ci = ufd.baseContent(c);
297 d = ufd.basePrimitivePart(c);
298 //System.out.println("c = " + c);
299 //System.out.println("ci = " + ci);
300 //System.out.println("d = " + d);
301
302 a = d.multiply(ci);
303 assertEquals("c == cont(c)pp(c)", c, a);
304 }
305 }
306
307
308 /**
309 * Test base gcd.
310 *
311 */
312 public void testBaseGcd() {
313
314 dfac = new GenPolynomialRing<ModLong>(mi, 1, to);
315
316 for (int i = 0; i < 5; i++) {
317 a = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
318 b = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
319 c = dfac.random(kl * (i + 2), ll + 2 * i, el + 2 * i, q);
320 //a = ufd.basePrimitivePart(a);
321 //b = ufd.basePrimitivePart(b);
322 //c = ufd.basePrimitivePart(c).abs();
323
324 //System.out.println("a = " + a);
325 //System.out.println("b = " + b);
326 //System.out.println("c = " + c);
327
328 if (a.isZERO() || b.isZERO() || c.isZERO()) {
329 // skip for this turn
330 continue;
331 }
332 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
333 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
334 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
335
336 a = a.multiply(c);
337 b = b.multiply(c);
338
339 d = ufd.baseGcd(a, b);
340 e = PolyUtil.<ModLong> basePseudoRemainder(d, c);
341 //System.out.println("d = " + d);
342
343 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
344 }
345 }
346
347
348 /**
349 * Test recursive quotioent and remainder.
350 *
351 */
352 public void testRecursiveQR() {
353 dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
354 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
355 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
356
357 for (int i = 0; i < 5; i++) {
358 a = dfac.random(kl * (i + 1), ll + i, el + i, q);
359 a = ufd.basePrimitivePart(a).abs();
360
361 c = dfac.random(kl * (i + 1), ll + i, el + i, q);
362 c = ufd.basePrimitivePart(a).abs();
363 cr = PolyUtil.<ModLong> recursive(rfac, c);
364
365 c = cfac.random(kl * (i + 1), ll + 2 * i, el + 2 * i, q);
366 c = ufd.basePrimitivePart(c).abs();
367
368 ar = PolyUtil.<ModLong> recursive(rfac, a);
369 //System.out.println("ar = " + ar);
370 //System.out.println("a = " + a);
371 //System.out.println("c = " + c);
372 //System.out.println("cr = " + cr);
373
374 if (cr.isZERO() || c.isZERO()) {
375 // skip for this turn
376 continue;
377 }
378 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
379 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
380 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
381
382
383 br = ar.multiply(cr);
384 //System.out.println("br = " + br);
385 dr = PolyUtil.<ModLong> recursivePseudoRemainder(br, cr);
386 //System.out.println("dr = " + dr);
387 d = PolyUtil.<ModLong> distribute(dfac, dr);
388 //System.out.println("d = " + d);
389
390 assertTrue("rem(ac,c) == 0", d.isZERO());
391
392 br = ar.multiply(c);
393 //System.out.println("br = " + br);
394 dr = PolyUtil.<ModLong> recursiveDivide(br, c);
395 //System.out.println("dr = " + dr);
396 d = PolyUtil.<ModLong> distribute(dfac, dr);
397 //System.out.println("d = " + d);
398
399 assertEquals("a == ac/c", a, d);
400 }
401 }
402
403
404 /**
405 * Test recursive content and primitive part.
406 *
407 */
408 public void testRecursiveContentPP() {
409 dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
410 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
411 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
412
413 for (int i = 0; i < 3; i++) {
414 cr = rfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
415 //System.out.println("cr = " + cr);
416
417 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
418 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
419 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
420
421 c = ufd.recursiveContent(cr);
422 dr = ufd.recursivePrimitivePart(cr);
423 //System.out.println("c = " + c);
424 //System.out.println("dr = " + dr);
425
426 ar = dr.multiply(c);
427 assertEquals("c == cont(c)pp(c)", cr, ar);
428 }
429 }
430
431
432 /**
433 * Test recursive gcd.
434 *
435 */
436 public void testRecursiveGCD() {
437 dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
438 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
439 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
440
441 for (int i = 0; i < 2; i++) {
442 ar = rfac.random(kl, ll, el + i, q);
443 br = rfac.random(kl, ll, el, q);
444 cr = rfac.random(kl, ll, el, q);
445 //System.out.println("ar = " + ar);
446 //System.out.println("br = " + br);
447 //System.out.println("cr = " + cr);
448
449 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
450 // skip for this turn
451 continue;
452 }
453 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
454 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
455 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
456
457 ar = ar.multiply(cr);
458 br = br.multiply(cr);
459 //System.out.println("ar = " + ar);
460 //System.out.println("br = " + br);
461
462 dr = ufd.recursiveUnivariateGcd(ar, br);
463 //System.out.println("dr = " + dr);
464
465 er = PolyUtil.<ModLong> recursivePseudoRemainder(dr, cr);
466 //System.out.println("er = " + er);
467
468 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
469 }
470 }
471
472
473 /**
474 * Test arbitrary recursive gcd.
475 *
476 */
477 public void testArbitraryRecursiveGCD() {
478 dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
479 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
480 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
481
482 for (int i = 0; i < 2; i++) {
483 ar = rfac.random(kl, ll, el + i, q);
484 br = rfac.random(kl, ll, el, q);
485 cr = rfac.random(kl, ll, el, q);
486 //System.out.println("ar = " + ar);
487 //System.out.println("br = " + br);
488 //System.out.println("cr = " + cr);
489
490 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
491 // skip for this turn
492 continue;
493 }
494 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
495 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
496 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
497
498 ar = ar.multiply(cr);
499 br = br.multiply(cr);
500 //System.out.println("ar = " + ar);
501 //System.out.println("br = " + br);
502
503 dr = ufd.recursiveGcd(ar, br);
504 //System.out.println("dr = " + dr);
505
506 er = PolyUtil.<ModLong> recursivePseudoRemainder(dr, cr);
507 //System.out.println("er = " + er);
508
509 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
510 }
511 }
512
513
514 /**
515 * Test content and primitive part.
516 *
517 */
518 public void testContentPP() {
519 dfac = new GenPolynomialRing<ModLong>(mi, 3, to);
520
521 for (int i = 0; i < 3; i++) {
522 c = dfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
523 //System.out.println("cr = " + cr);
524 if (c.isZERO()) {
525 continue;
526 }
527
528 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
529 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
530 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
531
532 a = ufd.content(c);
533 e = a.extend(dfac, 0, 0L);
534 b = ufd.primitivePart(c);
535 //System.out.println("c = " + c);
536 //System.out.println("a = " + a);
537 //System.out.println("e = " + e);
538 //System.out.println("b = " + b);
539
540 d = e.multiply(b);
541 assertEquals("c == cont(c)pp(c)", d, c);
542 }
543 }
544
545
546 /**
547 * Test gcd 3 variables.
548 *
549 */
550 public void testGCD3() {
551 dfac = new GenPolynomialRing<ModLong>(mi, 3, to);
552
553 for (int i = 0; i < 4; i++) {
554 a = dfac.random(kl, ll, el + i, q);
555 b = dfac.random(kl, ll, el, q);
556 c = dfac.random(kl, ll, el, q);
557 //System.out.println("a = " + a);
558 //System.out.println("b = " + b);
559 //System.out.println("c = " + c);
560
561 if (a.isZERO() || b.isZERO() || c.isZERO()) {
562 // skip for this turn
563 continue;
564 }
565 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
566 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
567 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
568
569 a = a.multiply(c);
570 b = b.multiply(c);
571 //System.out.println("a = " + a);
572 //System.out.println("b = " + b);
573
574 d = ufd.gcd(a, b);
575 //System.out.println("d = " + d);
576
577 e = PolyUtil.<ModLong> basePseudoRemainder(d, c);
578 //System.out.println("e = " + e);
579
580 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
581 }
582 }
583
584
585 /**
586 * Test gcd.
587 *
588 */
589 public void testGCD() {
590 // dfac = new GenPolynomialRing<ModLong>(mi,3,to);
591
592 for (int i = 0; i < 1; i++) {
593 a = dfac.random(kl, ll, el, q);
594 b = dfac.random(kl, ll, el, q);
595 c = dfac.random(kl, ll, el, q);
596 //System.out.println("a = " + a);
597 //System.out.println("b = " + b);
598 //System.out.println("c = " + c);
599
600 if (a.isZERO() || b.isZERO() || c.isZERO()) {
601 // skip for this turn
602 continue;
603 }
604 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
605 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
606 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
607
608 a = a.multiply(c);
609 b = b.multiply(c);
610 //System.out.println("a = " + a);
611 //System.out.println("b = " + b);
612
613 d = ufd.gcd(a, b);
614 //System.out.println("d = " + d);
615
616 e = PolyUtil.<ModLong> basePseudoRemainder(d, c);
617 //System.out.println("e = " + e);
618 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
619
620 e = PolyUtil.<ModLong> basePseudoRemainder(a, d);
621 //System.out.println("e = " + e);
622 assertTrue("gcd(a,b) | a " + e, e.isZERO());
623
624 e = PolyUtil.<ModLong> basePseudoRemainder(b, d);
625 //System.out.println("e = " + e);
626 assertTrue("gcd(a,b) | b " + e, e.isZERO());
627 }
628 }
629
630
631 /**
632 * Test lcm.
633 *
634 */
635 public void testLCM() {
636 dfac = new GenPolynomialRing<ModLong>(mi, 3, to);
637
638 for (int i = 0; i < 1; i++) {
639 a = dfac.random(kl, ll, el, q);
640 b = dfac.random(kl, ll, el, q);
641 c = dfac.random(kl, 3, 2, q);
642 //System.out.println("a = " + a);
643 //System.out.println("b = " + b);
644 //System.out.println("c = " + c);
645
646 if (a.isZERO() || b.isZERO() || c.isZERO()) {
647 // skip for this turn
648 continue;
649 }
650 assertTrue("length( a" + i + " ) <> 0", a.length() > 0);
651 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
652 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
653
654 a = a.multiply(c);
655 b = b.multiply(c);
656
657 c = ufd.gcd(a, b);
658 //System.out.println("c = " + c);
659
660 d = ufd.lcm(a, b);
661 //System.out.println("d = " + d);
662
663 e = c.multiply(d);
664 //System.out.println("e = " + e);
665 c = a.multiply(b);
666 //System.out.println("c = " + c);
667
668 assertEquals("ab == gcd(a,b)lcm(ab)", c, e);
669 }
670 }
671
672
673 /**
674 * Test co-prime factors.
675 *
676 */
677 public void testCoPrime() {
678
679 dfac = new GenPolynomialRing<ModLong>(mi, 3, to);
680
681 a = dfac.random(kl, 3, 2, q);
682 b = dfac.random(kl, 3, 2, q);
683 c = dfac.random(kl, 3, 2, q);
684 //System.out.println("a = " + a);
685 //System.out.println("b = " + b);
686 //System.out.println("c = " + c);
687
688 if (a.isZERO() || b.isZERO() || c.isZERO()) {
689 // skip for this turn
690 return;
691 }
692 assertTrue("length( a ) <> 0", a.length() > 0);
693
694 d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
695 e = a.multiply(b).multiply(c);
696 //System.out.println("d = " + d);
697 //System.out.println("c = " + c);
698
699 List<GenPolynomial<ModLong>> F = new ArrayList<GenPolynomial<ModLong>>(5);
700 F.add(d);
701 F.add(a);
702 F.add(b);
703 F.add(c);
704 F.add(e);
705
706
707 List<GenPolynomial<ModLong>> P = ufd.coPrime(F);
708 //System.out.println("F = " + F);
709 //System.out.println("P = " + P);
710
711 assertTrue("is co-prime ", ufd.isCoPrime(P));
712 assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
713
714
715 //P = ufd.coPrimeSquarefree(F);
716 //System.out.println("F = " + F);
717 //System.out.println("P = " + P);
718 //assertTrue("is co-prime ", ufd.isCoPrime(P) );
719 //assertTrue("is co-prime of ", ufd.isCoPrime(P,F) );
720
721
722 P = ufd.coPrimeRec(F);
723 //System.out.println("F = " + F);
724 //System.out.println("P = " + P);
725
726 assertTrue("is co-prime ", ufd.isCoPrime(P));
727 assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
728 }
729
730 }