001 /*
002 * $Id: GCDModLongTest.java 2958 2010-01-01 17:43:39Z 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.BigInteger;
016 import edu.jas.arith.ModLong;
017 import edu.jas.arith.ModLongRing;
018 import edu.jas.arith.PrimeList;
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 algorithm tests with JUnit.
027 * @author Heinz Kredel.
028 */
029
030 public class GCDModLongTest 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>GCDModularTest</CODE> object.
043 * @param name String.
044 */
045 public GCDModLongTest(String name) {
046 super(name);
047 }
048
049
050 /**
051 */
052 public static Test suite() {
053 TestSuite suite = new TestSuite(GCDModLongTest.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<ModLong> ac;
112
113
114 GenPolynomial<ModLong> bc;
115
116
117 GenPolynomial<GenPolynomial<ModLong>> ar;
118
119
120 GenPolynomial<GenPolynomial<ModLong>> br;
121
122
123 GenPolynomial<GenPolynomial<ModLong>> cr;
124
125
126 GenPolynomial<GenPolynomial<ModLong>> dr;
127
128
129 GenPolynomial<GenPolynomial<ModLong>> er;
130
131
132 GenPolynomial<GenPolynomial<ModLong>> arc;
133
134
135 GenPolynomial<GenPolynomial<ModLong>> brc;
136
137
138 int rl = 5;
139
140
141 int kl = 4;
142
143
144 int ll = 5;
145
146
147 int el = 3;
148
149
150 float q = 0.3f;
151
152
153 @Override
154 protected void setUp() {
155 a = b = c = d = e = null;
156 ai = bi = ci = di = ei = null;
157 ar = br = cr = dr = er = null;
158 //mi = new ModLongRing(primes.get(0), true);
159 mi = new ModLongRing(5L, true);
160 ufd = new GreatestCommonDivisorPrimitive<ModLong>();
161 dfac = new GenPolynomialRing<ModLong>(mi, rl, to);
162 cfac = new GenPolynomialRing<ModLong>(mi, rl - 1, to);
163 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
164 }
165
166
167 @Override
168 protected void tearDown() {
169 a = b = c = d = e = null;
170 ai = bi = ci = di = ei = null;
171 ar = br = cr = dr = er = null;
172 ufd = null;
173 dfac = null;
174 cfac = null;
175 rfac = null;
176 }
177
178
179 /**
180 * Test modular algorithm gcd with modular evaluation recursive algorithm.
181 *
182 */
183 public void testModularEvaluationGcd() {
184
185 GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular<ModLong>(); // dummy type
186
187 GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorPrimitive<BigInteger>();
188
189 GenPolynomial<BigInteger> a;
190 GenPolynomial<BigInteger> b;
191 GenPolynomial<BigInteger> c;
192 GenPolynomial<BigInteger> d;
193 GenPolynomial<BigInteger> e;
194
195 GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(), 3, to);
196
197 for (int i = 0; i < 2; i++) {
198 a = dfac.random(kl, ll + i, el + i, q);
199 b = dfac.random(kl, ll + i, el + i, q);
200 c = dfac.random(kl, ll + i, el + i, q);
201 c = c.multiply(dfac.univariate(0));
202 //a = ufd.basePrimitivePart(a);
203 //b = ufd.basePrimitivePart(b);
204
205 if (a.isZERO() || b.isZERO() || c.isZERO()) {
206 // skip for this turn
207 continue;
208 }
209 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
210 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
211 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
212
213 a = a.multiply(c);
214 b = b.multiply(c);
215
216 //System.out.println("a = " + a);
217 //System.out.println("b = " + b);
218
219 d = ufd_m.gcd(a, b);
220
221 c = ufd.basePrimitivePart(c).abs();
222 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
223 //System.out.println("c = " + c);
224 //System.out.println("d = " + d);
225
226 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
227
228 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
229 //System.out.println("e = " + e);
230 assertTrue("gcd(a,b) | a" + e, e.isZERO());
231
232 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
233 //System.out.println("e = " + e);
234 assertTrue("gcd(a,b) | b" + e, e.isZERO());
235 }
236 }
237
238
239 /**
240 * Test modular algorithm gcd with simple PRS recursive algorithm.
241 *
242 */
243 public void testModularSimpleGcd() {
244
245 GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular<ModLong>(true); // dummy type
246
247 GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorPrimitive<BigInteger>();
248
249 GenPolynomial<BigInteger> a;
250 GenPolynomial<BigInteger> b;
251 GenPolynomial<BigInteger> c;
252 GenPolynomial<BigInteger> d;
253 GenPolynomial<BigInteger> e;
254
255 GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(), 3, to);
256
257 for (int i = 0; i < 1; i++) {
258 a = dfac.random(kl, ll + i, el + i, q);
259 b = dfac.random(kl, ll + i, el + i, q);
260 c = dfac.random(kl, ll + i, el + i, q);
261 c = c.multiply(dfac.univariate(0));
262 //a = ufd.basePrimitivePart(a);
263 //b = ufd.basePrimitivePart(b);
264
265 if (a.isZERO() || b.isZERO() || c.isZERO()) {
266 // skip for this turn
267 continue;
268 }
269 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
270 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
271 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
272
273 a = a.multiply(c);
274 b = b.multiply(c);
275
276 //System.out.println("a = " + a);
277 //System.out.println("b = " + b);
278
279 d = ufd_m.gcd(a, b);
280
281 c = ufd.basePrimitivePart(c).abs();
282 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
283 //System.out.println("c = " + c);
284 //System.out.println("d = " + d);
285
286 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
287
288 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
289 //System.out.println("e = " + e);
290 assertTrue("gcd(a,b) | a" + e, e.isZERO());
291
292 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
293 //System.out.println("e = " + e);
294 assertTrue("gcd(a,b) | b" + e, e.isZERO());
295 }
296 }
297
298
299 /**
300 * Test recursive content and primitive part, modular coefficients.
301 *
302 */
303 public void testRecursiveContentPPmodular() {
304
305 dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
306 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
307 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
308
309 GreatestCommonDivisorAbstract<ModLong> ufd = new GreatestCommonDivisorPrimitive<ModLong>();
310
311 for (int i = 0; i < 1; i++) {
312 a = cfac.random(kl, ll + 2 * i, el + i, q).monic();
313 cr = rfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
314 cr = PolyUtil.<ModLong> monic(cr);
315 //System.out.println("a = " + a);
316 //System.out.println("cr = " + cr);
317 //a = ufd.basePrimitivePart(a);
318 //b = distribute(dfac,cr);
319 //b = ufd.basePrimitivePart(b);
320 //cr = recursive(rfac,b);
321 //System.out.println("a = " + a);
322 //System.out.println("cr = " + cr);
323
324 cr = cr.multiply(a);
325 //System.out.println("cr = " + cr);
326
327 if (cr.isZERO()) {
328 // skip for this turn
329 continue;
330 }
331 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
332 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
333 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
334
335 c = ufd.recursiveContent(cr).monic();
336 dr = ufd.recursivePrimitivePart(cr);
337 dr = PolyUtil.<ModLong> monic(dr);
338 //System.out.println("c = " + c);
339 //System.out.println("dr = " + dr);
340
341 //System.out.println("monic(a) = " + a.monic());
342 //System.out.println("monic(c) = " + c.monic());
343
344 ar = dr.multiply(c);
345 //System.out.println("ar = " + ar);
346 assertEquals("c == cont(c)pp(c)", cr, ar);
347 }
348 }
349
350
351 /**
352 * Test base gcd modular coefficients.
353 *
354 */
355 public void testGCDbaseModular() {
356
357 dfac = new GenPolynomialRing<ModLong>(mi, 1, to);
358
359 GreatestCommonDivisorAbstract<ModLong> ufd = new GreatestCommonDivisorPrimitive<ModLong>();
360
361 for (int i = 0; i < 1; i++) {
362 a = dfac.random(kl, ll, el + 3 + i, q).monic();
363 b = dfac.random(kl, ll, el + 3 + i, q).monic();
364 c = dfac.random(kl, ll, el + 3 + i, q).monic();
365 //System.out.println("a = " + a);
366 //System.out.println("b = " + b);
367 //System.out.println("c = " + c);
368
369 if (a.isZERO() || b.isZERO() || c.isZERO()) {
370 // skip for this turn
371 continue;
372 }
373 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
374 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
375 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
376
377 ac = a.multiply(c);
378 bc = b.multiply(c);
379 //System.out.println("ac = " + ac);
380 //System.out.println("bc = " + bc);
381
382 //e = PolyUtil.<ModLong>basePseudoRemainder(ac,c);
383 //System.out.println("ac/c a = 0 " + e);
384 //assertTrue("ac/c-a != 0 " + e, e.isZERO() );
385 //e = PolyUtil.<ModLong>basePseudoRemainder(bc,c);
386 //System.out.println("bc/c-b = 0 " + e);
387 //assertTrue("bc/c-b != 0 " + e, e.isZERO() );
388
389 d = ufd.baseGcd(ac, bc);
390 d = d.monic(); // not required
391 //System.out.println("d = " + d);
392
393 e = PolyUtil.<ModLong> basePseudoRemainder(d, c);
394 //System.out.println("e = " + e);
395
396 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
397 }
398 }
399
400
401 /**
402 * Test recursive gcd modular coefficients.
403 *
404 */
405 public void testRecursiveGCDModular() {
406
407 dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
408 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
409 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
410
411 // GreatestCommonDivisorAbstract<ModLong> ufd
412 // = new GreatestCommonDivisorPrimitive<ModLong>();
413
414 for (int i = 0; i < 1; i++) {
415 ar = rfac.random(kl, 2, el + 2, q);
416 br = rfac.random(kl, 2, el + 2, q);
417 cr = rfac.random(kl, 2, el + 2, q);
418 ar = PolyUtil.<ModLong> monic(ar);
419 br = PolyUtil.<ModLong> monic(br);
420 cr = PolyUtil.<ModLong> monic(cr);
421 //System.out.println("ar = " + ar);
422 //System.out.println("br = " + br);
423 //System.out.println("cr = " + cr);
424
425 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
426 // skip for this turn
427 continue;
428 }
429 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
430 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
431 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
432
433 arc = ar.multiply(cr);
434 brc = br.multiply(cr);
435 //System.out.println("arc = " + arc);
436 //System.out.println("brc = " + brc);
437
438 //er = PolyUtil.<ModLong>recursivePseudoRemainder(arc,cr);
439 //System.out.println("ac/c-a = 0 " + er);
440 //assertTrue("ac/c-a != 0 " + er, er.isZERO() );
441 //er = PolyUtil.<ModLong>recursivePseudoRemainder(brc,cr);
442 //System.out.println("bc/c-b = 0 " + er);
443 //assertTrue("bc/c-b != 0 " + er, er.isZERO() );
444
445 dr = ufd.recursiveUnivariateGcd(arc, brc);
446 dr = PolyUtil.<ModLong> monic(dr);
447 //System.out.println("cr = " + cr);
448 //System.out.println("dr = " + dr);
449
450 er = PolyUtil.<ModLong> recursivePseudoRemainder(dr, cr);
451 //System.out.println("er = " + er);
452
453 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
454 }
455 }
456
457
458 /**
459 * Test arbitrary recursive gcd modular coefficients.
460 *
461 */
462 public void testArbitraryRecursiveGCDModular() {
463
464 dfac = new GenPolynomialRing<ModLong>(mi, 2, to);
465 cfac = new GenPolynomialRing<ModLong>(mi, 2 - 1, to);
466 rfac = new GenPolynomialRing<GenPolynomial<ModLong>>(cfac, 1, to);
467
468 // GreatestCommonDivisorAbstract<ModLong> ufd
469 // = new GreatestCommonDivisorPrimitive<ModLong>();
470
471 for (int i = 0; i < 1; i++) {
472 ar = rfac.random(kl, 2, el + 2, q);
473 br = rfac.random(kl, 2, el + 2, q);
474 cr = rfac.random(kl, 2, el + 2, q);
475 ar = PolyUtil.<ModLong> monic(ar);
476 br = PolyUtil.<ModLong> monic(br);
477 cr = PolyUtil.<ModLong> monic(cr);
478 //System.out.println("ar = " + ar);
479 //System.out.println("br = " + br);
480 //System.out.println("cr = " + cr);
481
482 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
483 // skip for this turn
484 continue;
485 }
486 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
487 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
488 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
489
490 arc = ar.multiply(cr);
491 brc = br.multiply(cr);
492 //System.out.println("arc = " + arc);
493 //System.out.println("brc = " + brc);
494
495 //er = PolyUtil.<ModLong>recursivePseudoRemainder(arc,cr);
496 //System.out.println("ac/c-a = 0 " + er);
497 //assertTrue("ac/c-a != 0 " + er, er.isZERO() );
498 //er = PolyUtil.<ModLong>recursivePseudoRemainder(brc,cr);
499 //System.out.println("bc/c-b = 0 " + er);
500 //assertTrue("bc/c-b != 0 " + er, er.isZERO() );
501
502 dr = ufd.recursiveGcd(arc, brc);
503 dr = PolyUtil.<ModLong> monic(dr);
504 //System.out.println("cr = " + cr);
505 //System.out.println("dr = " + dr);
506
507 er = PolyUtil.<ModLong> recursivePseudoRemainder(dr, cr);
508 //System.out.println("er = " + er);
509
510 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
511 }
512 }
513
514
515 /**
516 * Test gcd modular coefficients.
517 *
518 */
519 public void testGcdModular() {
520
521 dfac = new GenPolynomialRing<ModLong>(mi, 4, to);
522
523 for (int i = 0; i < 1; i++) {
524 a = dfac.random(kl, ll, el + i, q).monic();
525 b = dfac.random(kl, ll, el + i, q).monic();
526 c = dfac.random(kl, ll, el + i, q).monic();
527 //System.out.println("a = " + a);
528 //System.out.println("b = " + b);
529 //System.out.println("c = " + c);
530
531 if (a.isZERO() || b.isZERO() || c.isZERO()) {
532 // skip for this turn
533 continue;
534 }
535 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
536 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
537 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
538
539 ac = a.multiply(c);
540 bc = b.multiply(c);
541 //System.out.println("ac = " + ac);
542 //System.out.println("bc = " + bc);
543
544 //e = PolyUtil.<ModLong>basePseudoRemainder(ac,c);
545 //System.out.println("ac/c-a = 0 " + e);
546 //assertTrue("ac/c-a != 0 " + e, e.isZERO() );
547 //e = PolyUtil.<ModLong>basePseudoRemainder(bc,c);
548 //System.out.println("bc/c-b = 0 " + e);
549 //assertTrue("bc/c-b != 0 " + e, e.isZERO() );
550
551 d = ufd.gcd(ac, bc);
552 //System.out.println("d = " + d);
553 e = PolyUtil.<ModLong> basePseudoRemainder(d, c);
554 //System.out.println("e = " + e);
555 //System.out.println("c = " + c);
556 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
557
558 e = PolyUtil.<ModLong> basePseudoRemainder(ac, d);
559 //System.out.println("gcd(ac,bc) | ac " + e);
560 assertTrue("gcd(ac,bc) | ac " + e, e.isZERO());
561 e = PolyUtil.<ModLong> basePseudoRemainder(bc, d);
562 //System.out.println("gcd(ac,bc) | bc " + e);
563 assertTrue("gcd(ac,bc) | bc " + e, e.isZERO());
564 }
565 }
566
567
568 /**
569 * Test co-prime factors.
570 *
571 */
572 public void testCoPrime() {
573
574 dfac = new GenPolynomialRing<ModLong>(mi, 3, to);
575
576 a = dfac.random(kl, 3, 2, q);
577 b = dfac.random(kl, 3, 2, q);
578 c = dfac.random(kl, 3, 2, q);
579 //System.out.println("a = " + a);
580 //System.out.println("b = " + b);
581 //System.out.println("c = " + c);
582
583 if (a.isZERO() || b.isZERO() || c.isZERO()) {
584 // skip for this turn
585 return;
586 }
587 assertTrue("length( a ) <> 0", a.length() > 0);
588
589 d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
590 e = a.multiply(b).multiply(c);
591 //System.out.println("d = " + d);
592 //System.out.println("c = " + c);
593
594 List<GenPolynomial<ModLong>> F = new ArrayList<GenPolynomial<ModLong>>(5);
595 F.add(a);
596 F.add(b);
597 F.add(c);
598 F.add(d);
599 F.add(e);
600
601 List<GenPolynomial<ModLong>> P = ufd.coPrime(F);
602 //System.out.println("F = " + F);
603 //System.out.println("P = " + P);
604
605 assertTrue("is co-prime ", ufd.isCoPrime(P));
606 assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
607
608 P = ufd.coPrimeRec(F);
609 //System.out.println("F = " + F);
610 //System.out.println("P = " + P);
611
612 assertTrue("is co-prime ", ufd.isCoPrime(P));
613 assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
614 }
615
616 }